嵌牛导读：对于类似链表，队列，哈希表等这种集合结构，其构成方式一般比较统一。
嵌牛鼻子：哈希表
嵌牛提问：在rehashing期间，所有的删除查找和更新都会发生在俩个字典上。即使是添加，也会现在ht[0]上查找是否存在？
嵌牛正文：
1.1 哈希表节点
参数介绍：
简单介绍下union的作用，就是节省内存。可以假设如果没有union
64位编译器下面要占据24个字节。但使用union只占据最宽的字节大小——8个字节。
next主要用来解决key冲突的问题。
1.2 哈希表
1.3 字典
2. 一个普通状态下的字典
没有经过rehash状态下的字典。
图1
3. 字典的变化
3.1 创建一个字典
3.2 插入一个元素
函数调用图
图2
可以看到，插入一个元素的时候，首先需要判断是否在Rehashing，这里我们直接跳过，直接忽略掉。
首先对字典里面的ht[0]进行扩容
利用hash函数计算idx
然后判断是否哈希冲突
3.3 发生哈希冲突之后
3.4 哈希算法
对于哈希表dictht来说
size: 表示哈希表的大小
sizemask: size-1
used: 表示有多少个Entry被使用
利用hash函数计算得到值后再与sizemask相与，得到idx值。
3.5 rehash
对于扩展操作来说。哈希表的初始大小为DICT_HT_INITIAL_SIZE=4。
有以下几个条件会触发rehash
used == size
used / size > dict_force_resize_ratio
redis的rehash是这样做的。字典有俩张哈希表。当rehash条件被触发后，就会在第二张表上分配空间。大小为大于等于ht[0].used * 2的2的最小幂次方倍。然后将ht[0]的项搬到ht[1]上，再调换俩个表的位置即可。
渐进式rehash
当hash表很大时，会导致rehash的操作比较耗时。因此redis这样做。
以下摘自《redis的设计与实现》
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]俩个哈希表
在字典找那个维持一个索引计数器变量rehashidx，并设为0.
rehash期间，每次对字典添加、删除、查找或者更新时，程序还会将ht[0]->table[rehashidx]上的所有key,value对rehash到ht[1]上。然后让rehashidx++。
当rehashidx == ht[0].size的时候，rehash完毕，重新将rehashidx = -1。
网友评论