ehash
在字典的底层实现中,value对象以每一个dictEntry的对象进行存储,当hash表中的存放的键值对不断的增加或者减少时,需要对hash表进行一个扩展或者收缩。
这里就会和HashMap一样也会就进行rehash操作,进行重新散列排布。从上图中可以看到有ht[0]和ht[1]两个对象,先来看看对象中的属性是干嘛用的。
在hash表结构定义中有四个属性分别是dictEntry **table、unsigned long size、unsigned long sizemask、unsigned long used,分别表示的含义就是「哈希表数组、hash表大小、用于计算索引值,总是等于size-1、hash表中已有的节点数」。
ht[0]是用来最开始存储数据的,当要进行扩展或者收缩时,ht[0]的大小就决定了ht[1]的大小,ht[0]中的所有的键值对就会重新散列到ht[1]中。
扩展操作:ht[1]扩展的大小是比当前 ht[0].used 值的二倍大的第一个 2 的整数幂;收缩操作:ht[0].used 的第一个大于等于的 2 的整数幂。
当ht[0]上的所有的键值对都rehash到ht[1]中,会重新计算所有的数组下标值,当数据迁移完后ht[0]就会被释放,然后将ht[1]改为ht[0],并新创建ht[1],为下一次的扩展和收缩做准备。
渐进式rehash
假如在rehash的过程中数据量非常大,Redis不是一次性把全部数据rehash成功,这样会导致Redis对外服务停止,Redis内部为了处理这种情况采用「渐进式的rehash」。
Redis将所有的rehash的操作分成多步进行,直到都rehash完成,具体的实现与对象中的rehashindex属性相关,「若是rehashindex 表示为-1表示没有rehash操作」。
当rehash操作开始时会将该值改成0,在渐进式rehash的过程「更新、删除、查询会在ht[0]和ht[1]中都进行」,比如更新一个值先更新ht[0],然后再更新ht[1]。
而新增操作直接就新增到ht[1]表中,ht[0]不会新增任何的数据,这样保证「ht[0]只减不增,直到最后的某一个时刻变成空表」,这样rehash操作完成。
上面就是字典的底层hashtable的实现原理,说完了hashtable的实现原理,我们再来看看Hash数据结构的两一种存储方式「ziplist(压缩列表)」
ziplist
压缩列表(ziplist)是一组连续内存块组成的顺序的数据结构,压缩列表能够节省空间,压缩列表中使用多个节点来存储数据。
压缩列表是列表键和哈希键底层实现的原理之一,「压缩列表并不是以某种压缩算法进行压缩存储数据,而是它表示一组连续的内存空间的使用,节省空间」,压缩列表的内存结构图如下:
