\(12.4\)数据结构的最终实现

1.运行时间的优化

  假设我们存放索引的数组的大小为\(5\)，当我们插入\(100\)个元素时，最坏的情况是：所有元素的索引都是一致的。这样，我们就得到了一个长度为\(100\)的链表。

  这显然不是我们希望看到的情况。对此，我们有两种处理方法：

1. 动态地扩大我们的哈希表。
2. 改进我们的\(hashCode\)。

  \(a.\)动态扩容

  假设我们有\(M\)个筐和\(N\)个元素，我们定义负载系数(\(load\;factor\))为\(N\over M\)(这即是我们的最佳运行时间)。

  为了让我们的负载系数维持在一个较低的范围内，我们可以直接让\(M\)变为\(2M\)，并进行如下操作：

• 创建一个新的容量为\(2M\)的哈希表。

• 迭代遍历原有的哈希表，然后把原有的元素复制到新的哈希表中。

  • 我们需要一个一个复制元素，是因为哈希表的容量改变了，因此我们的模数也变了，从而需要用新的模数一个一个将元素复制到新哈希表对应的位置。

  这样，我们得到了一个运行时间\(\Theta(N\over M)\)的哈希表。由于我们限定\(N\over M\)必须小于一个常数，因此最优运行时间为\(\Theta(N\over M)=\Theta(1)\)。

  \(b.\)改进\(hashCode\)

• Use a 'base' strategy similar to the one we developed earlier.

• Use a 'base' that's a small prime.

  • Base 126 isn't actually very good, because using base 126 means that any string that ends in the same last 32 characters has the same hashcode.
  • This happens because of overflow.
  • Using prime numbers helps avoid overflow issues (i.e., collisions due to overflow).
  • Why a small prime? Because it's easier to compute.