冲突(collision)定义

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

redis的冲突解决方案

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

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

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

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

参考资料

参考内容

书籍 : 《Redis 设计与实现》

实体书 : 可在京东搜索购买

注意事项

《Redis 设计与实现》 本书讲解基于redis 3.x 版本, 本人整理基于redis 5.0.6,期间跨了两个大版本, 部分功能具体实现已发生变化, 如发现整理内容与 《Redis 设计与实现》 讲解不一致, 可加 QQ : 2215508028 沟通,或在相关章节评论留言，会自动同步至issue

整理内容时参考的redis源码

版本 : 5.0.6

官方git : redis官方GIT (commit :bb78454b0fef0dc5903328d037ac2520108e0044 (5.0.6版本,redis官方的commit))