Skip to content

4.5 渐进式 rehash

为了避免 rehash 对服务器性能造成影响, 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] , 而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1]

以下是哈希表渐进式 rehash 的详细步骤:

  1. ht[1] 分配空间, 让字典同时持有 ht[0]ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。

渐进式 rehash 执行期间的哈希表操作

在 rehash 阶段,一个字典会出现两个哈希表,对字典的增删查更操作都会在另个哈希表进行操作。

渐进式 rehash 的好处是可以逐步进行,避免了 rehash 哈希表过大导致服务不可用。