hash实现
redis的hash数据结构和java的HashMap虽然不同,但是有异曲同工之妙,value是键值对,相当于HashMap,对于hash碰撞也是采用的类似于HashMap的处理方式,数组+链表,更适合存储对象,将一个对象存储在hash类型中会占用更少的内存,且可以更方便的存取整个对象
编码格式
编码 | 对象 |
---|---|
OBJ_ENCODING_ZIPLIST | 使用ziplist |
OBJ_ENCODING_HT | 使用的hash table |
set有两种编码格式
- ziplist 一开始存储使用的ziplist,但是当满足一定条件时会转换为hash table
- hash table
1 | #根据该配置项来进行编码转换的 |
源码结构
1 | // 哈希表数据结构 |
redis哈希冲突将新节点添加在链表的表头
过程分析
添加元素
向字典中添加元素,将会为字典中的ht[0]分配空间,默认情况下table数组为4(DICT_HT_INITIAL_SIZE),新添加元素的键值会经过哈希算法确定哈希表数组的位置,进行添加,如果两个不同的键经过哈希算法产生相同的哈希值,就会发生哈希冲突,采用链表的方式,新元素会放到链表头节点(与java7类似,因为新增加的节点,大概率会被再次访问)
扩容
扩容的时候会将ht[0]的所有键值都迁移到h[1]中,当节点全部迁移完毕后,释放ht[0]的占用空间,并将ht[1]设置为ht[0],由于redis中可能存的数据量比较大,所以进行rehash的时间可能会很长,而rehash又是一个阻塞的操作,redis采用的是渐进式的迁移方式,rehashidx就是为这个操作而设置的属性,用来记录索引位置的,默认为-1,当进行迁移的时候设置为0,每次接收到增加,删除,查找,更新命令时,除了执行该命令外,还需要将rehashidx索引上的节点迁移到ht[1],迁移之后,rehashidx+1,当所有的数据都迁移到ht[1]中时,rehashidx会被重新设置为-1