redis源码阅读笔记(3)——dict

opo

1.高层视角解读
字典， 又称符号表（symbol table）、关联数组（associative array）或者映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构。
请先看关于字典的一组文章
http://www.redisbook.com/en/latest/toc.html里面的第4章——字典。
字典的数据结构如图所示。


2.底层代码
代码在dict.h, dict.c这两个文件里。稍微多了一点，1600行代码。
如果读者读过java里的HashMap的源代码的话，可以发现两者的实现思路竟是惊人的相似。

2.1 hashFunction是一个可以由用户自己实现的函数，相当于java里的Object.hashCode方法。

2.2 redis自带一个哈希算法MurmurHash算法。目前的最新版本为 MurmurHash3 ， 而 Redis 使用的是 MurmurHash2 。
关于MurmurHash算法的更多信息可以参考该算法的主页： http://code.google.com/p/smhasher/
在java里有一个库guava也实现了MurmurHash算法
https://code.google.com/p/guava-libraries/wiki/HashingExplained

2.3 哈希冲突的处理和java一样，采用一个链表来解决冲突，将多个哈希值相同的节点串连在一起。
因为 dictEntry 节点组成的链表没有指向链表表尾的指针， 所以为了速度考虑， 程序总是将新节点添加到链表的表头位置（复杂度为 O(1)）， 排在其他已有节点的前面。
java里也是这样。

2.4 rehash和java也是惊人的相似。
负载因子（load factor）>=1时才rehash，这个似乎不太好，java里是>=0.75,因为负载因子达到某个值以后哈希冲突的概率就相当大了。

2.5 渐进式rehash是redis特有的特性，可以防止一次性rehash造成服务器停止工作。但是这个特性也使得代码到处都要考虑当前是否正在进行渐进式rehash，增加了复杂度。

2.6 字典的收缩也是redis特有的特性。
何时收缩？
t_hash.c文件中hashTypeDelete被执行时（HDEL命令）
先执行dictDelete
再执行htNeedsResize判断，如果负载因子小于10%，则调用dictResize缩小哈希表。

2.7 字典里有2个哈希表，使得rehash的时候如果遍历哈希表需要同时遍历2个哈希表。

3. 疑难点解惑
Q:dictEntry **table中**的含义？
A:**在C语言里含义是指向指针的指针，在这里的技巧含义是等价于定义了一个动态数组table中，这个数组里每个元素都是一个指针，每个指针指向一个dictEntry结构体。
table[1]的写法等价于*(table+1)，也就是访问数组中的第二个元素。