哈希分布不均匀该怎么办

希值来确定的。如果发生哈希碰撞（计算得到的哈希值一致），那么同一个下标就会有多个 dictEntry，从而形成一个链表（上图中最右边指向 NULL 的位置），不过需要注意的是最后插入元素的总是落在链表的最前面（即发生哈希冲突时，总是将节点往链表的头部放）。

当读取数据的时候遇到一个节点有多个元素，就需要遍历链表，故链表越长，性能越差。为了保证哈希表的性能，需要在满足以下两个条件中的一个时，对哈希表进行 rehash（重新散列）操作：

•  负载因子大于等于 1 且 dict_can_resize 为 1 时。
•  负载因子大于等于安全阈值（dict_force_resize_ratio=5）时。

PS：负载因子 = 哈希表已使用节点数 / 哈希表大小（即：h[0].used/h[0].size）。

rehash 步骤

扩展哈希和收缩哈希都是通过执行 rehash 来完成，这其中就涉及到了空间的分配和释放，主要经过以下五步：

 1.  为字典 dict 的 ht[1] 哈希表分配空间，其大小取决于当前哈希表已保存节点数（即：ht[0].used）：

•   如果是扩展操作则 ht[1] 的大小为 2 的n次方中第一个大于等于ht[0].used * 2属性的值（比如used=3，此时ht[0].used * 2=6，故2的3次方为8就是第一个大于used * 2的值（2 的 2 次方 < 6 且 2 的 3 次方 > 6））。
•  如果是收缩操作则 ht[1] 大小为 2 的 n 次方中第一个大于等于 ht[0].used 的值。

2.  将字典中的属性 rehashix 的值设置为 0，表示正在执行 rehash 操作。

3.  将 ht[0] 中所有的键值对依次重新计算哈希值，并放到 ht[1] 数组对应位置，每完成一个键值对的 rehash之后 rehashix 的值需要自增 1。

4.  当 ht[0] 中所有的键值对都迁移到 ht[1] 之后，释放 ht[0] ，并将 ht[1] 修改为 ht[0]，然后再创建一个新的 ht[1] 数组，为下一次 rehash 做准备。

5.  将字典中的属性 rehashix 设置为 -1，表示此次 rehash 操作结束，等待下一次 rehash。

渐进式 rehash

Redis 中的这种重新哈希的操作因为不是一次性全部 rehash，而是分多次来慢慢的将 ht[0] 中的键值对 rehash 到 ht[1]，故而这种操作也称之为渐进式 rehash。渐进式 rehash 可以避免集中式 rehash 带来的庞大计算量，是一种分而治之的思想。

在渐进式 rehash 过程中，因为还可能会有新的键值对存进来，此时** Redis 的做法是新添加的键值对统一放入 ht[1] 中，这样就确保了 ht[0] 键值对的数量只会减少**。

当正在执行 rehash操作时，如果服务器收到来自客户端的命令请求操作，则会先查询 ht[0]，查找不到结果再到ht[1] 中查询。

ziplist

（编辑：甘孜站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!