redis源码阅读--hashTable

公司有个项目用到hash，同事从redis的代码里抠了hashTable的源码出来，最近抽空看了一下，设计还是很精妙的。 现在把阅读的结果写写，以备后面复习可用（记得之前看过一次，后来长时间没看了就忘记了，这次再看基本要从头开始）

源码位置

• dict.h
• dict.c

图示

(摘自redis设计与实现) 参考这里

设计思路

• 这个hash(字典)他包含了两个table，为什么有两个呢？那是因为他要实现自动扩展，每次要add新元素的时候都要 判断一下是否需要扩展(expand)
• 两个table再挂上2的倍数(size) 的桶，每个桶都是一个链表。
• 当达到条件需要扩展的时候，一般是元素的个数和桶的比例差不多是1：1， 那就将第一个table生成第一个的size *2 为什么要是2的倍数呢？有几个好处：1.分布更均匀 2.碰撞几率更小 但是还有一个更重要的原因是： a%b可以替换成了a&(b-1) ，当hashtable的长度是2的幂的情况下。这样运算速度可以提高很多，具体可以参考这里
• 当新的table生成后，桶数扩大了一倍，这样就大大地减少了碰撞，但是就带来了一个原来的数据是rehash的问题
• 当rehash开始后，如果有增，删，查的操作，每次都搬一个桶到新的table上，如果已经开始rehash,那么，新增的元素就直接插到新的桶上
• 当rehash全部完成后，旧talbe释放掉，新table接替旧table成为主力工作。
• 还给hash设置了迭代器(iterators), 当有迭代器存在的时候，为了安全就不进行rehash的步骤。

参考资料

• 为啥要用位运算代替取模呢
• 图解redis之数据结构篇