Redis设计与实现之哈希冲突解决方案

冲突(collision)定义

当有 两个或以上 数量的键被分配到了哈希表数组的 同一个索引 上面时， 我们称这些键发生了冲突。

redis的冲突解决方案

链地址法（separate chaining） : 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

eg. 假设程序要将键值对 k2 和 v2 添加到下图所示的哈希表里面

计算得出 k2 的索引值为 2 ， 那么键 k1 和 k2 将产生冲突， 而解决冲突的办法就是使用 next 指针将键 k2 和 k1 所在的节点连接起来

【知识点】
因为 dictEntry 节点组成的链表 **没有指向链表表尾的指针**， 所以为了速度考虑， 程序总是将 **新节点添加到链表的表头位置**（复杂度为 O(1)）， 排在其他已有节点的前面。

参考资料

1. 《Redis设计与实现》 ↩