做搜狗网站优化快速排网页设计作业主题推荐

Rehash 执行过程

字典的 rehash 操作实际上就是执行以下任务：

• 创建一个比 ht[0]->table 更大的 ht[1]->table ；
• 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
• 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；
  经过以上步骤之后， 程序就在不改变原有键值对数据的基础上， 增大了哈希表的大小。

dict的rehash 本质就是扩容，就是将数组+链表结构中的数组扩容；
这个过程，需要开辟一个更大空间的数组，将老数组中每个非空索引的bucket，搬运到新数组；搬运完成后再释放老数组的空间。

作为例子， 以下四个小节展示了一次对哈希表进行 rehash 的完整过程。
1： 开始 rehash
这个阶段有两个事情要做：

• 设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；
• 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；

这时的字典是这个样子：

2： Rehash 进行中
在这个阶段， ht[0]->table 的节点会被逐渐迁移到 ht[1]->table ， 因为 rehash 是分多次进行