嵌牛导读:对于类似链表,队列,哈希表等这种集合结构,其构成方式一般比较统一。
嵌牛鼻子:哈希表
嵌牛提问:在rehashing期间,所有的删除查找和更新都会发生在俩个字典上。即使是添加,也会现在ht[0]上查找是否存在?
嵌牛正文:
1.1 哈希表节点
参数介绍:
简单介绍下union的作用,就是节省内存。可以假设如果没有union
64位编译器下面要占据24个字节。但使用union只占据最宽的字节大小——8个字节。
next主要用来解决key冲突的问题。
1.2 哈希表
1.3 字典
2. 一个普通状态下的字典
没有经过rehash状态下的字典。
图13. 字典的变化
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。
网友评论