一文详尽解析Redis的设计原理( 二 ) _Redis

privatadata属性：传给特定函数的可选参数。
ht属性：长度为2的dictht数组，一般情况下只使用ht[0]散列表，而ht[1]散列表只会在对ht[0]散列表进行rehash时使用
rehashidx属性：记录了rehash目前的进度，如果目前没有进行rehash那么值为-1
DictType的定义
typedef struct dictType{ //哈希函数 unsigned int (*hashFunction)(const void *key); //复制Key的函数 void *(*keyDup)(void *privatedata, const void *key); //复制Value的函数 void *(*valDup)(void *privatedata, const void *obj); //对比Key的函数 int (*keyCompare)(void *privatdata, const void *key1 , const void *key2); //销毁Key的函数 void (*keyDestructor)(void *privatedata, void *key); //销毁Value的函数 void (*valDestructor)(void *privatedata, void *obj);}dictType;3.1 在字典中进行查找、添加、更新、删除操作
在字典中进行查找
以客户端传递的Key作为关键字K，通过dict中的dictType的H(K)散列函数计算散列值，使用dictht[0]的sizemask属性和散列值计算索引，遍历索引对应的链表，判断是否存在Key相同的DictEntry，若存在则返回该DictEntry，否则返回NULL 。
在字典中进行添加和更新操作
以客户端传递的Key作为关键字K，通过dict中的dictType的H(K)散列函数计算散列值，使用dictht[0]的sizemask属性和散列值计算索引，遍历索引对应的链表，判断是否存在Key相同的DictEntry，若不存在Key相同的DictEntry，则创建代表Key的SDS对象和RedisObject以及代表Value的对象和RedisObject，然后创建一个DictEntry并分别指向Key和Value对应的RedisObject，最终将该DictEntry追加到链表的最后一个节点中，若存在Key相同的DictEntry，则判断当前的命令是否满足Value对应的类型，若满足则进行更新，否则报错。
创建和更新操作是相对的，当不存在则创建否则进行更新。
在字典中进行删除操作
以客户端传递的Key作为关键字K，通过dict中的dictType的H(K)散列函数计算散列值，使用dictht[0]的sizemask属性和散列值计算索引，遍历索引对应的链表，找到Key相同的DictEntry进行删除。
3.2 散列表的扩容和缩容
由于散列表的负载因子需要维持在一个合理的范围内，因此当散列表中的元素过多时会进行扩容，过少时会进行缩容。
一旦散列表的长度发生改变，那么就要进行rehash，即对原先散列表中的元素在新的散列表中重新进行hash 。
Redis中的rehash是渐进式的，并不是一次性完成，因为要考虑性能问题，如果散列表中包含上百万个节点，那么庞大的计算量可能会导致Redis在一段时间内无法对外提供服务。
在rehash进行期间，每次对字典执行查找、添加、更新、删除操作时，除了会执行指定的操作以外，还会顺带将ht[0]散列表在rehashidx索引上的所有节点rehash到ht[1]上，然后将rehashidx属性的值加1 。
渐进式Rehash的步骤
1.为字典的ht[1]散列表分配空间。

若执行的是扩容操作，那么ht[1]的长度为第一个大于等于ht[0].used*2的2? 。
若执行的是缩容操作，那么ht[1]的长度为第一个大于等于ht[0].used的2? 。

2.rehashidx属性设置为0，表示开始进行rehash 。
3.在rehash进行期间，每次对字典执行查找、添加、更新、删除操作时，除了会执行指定的操作以外，还会顺带将ht[0]散列表在rehashidx索引上的所有节点rehash到ht[1]上，然后将rehashidx属性的值加1 。
4.随着对字典不断的操作，最终在某个时间点上，ht[0]散列表中的所有dictEntry都会被rehash到ht[1]上，当rehash结束之后将rehashidx属性的值设为-1，表示rehash操作已完成。