12.4.数据结构的最终实现

\(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.