1.绪论
字典是一个由两个hash表组成的数据结构,hash表其实就是类似java的hashTable,所以hashTable是由多个hash entry组成。为什么字典是由两个hash表组成呢,它的数据结构是怎样的呢?我们后面将会讨论。
2.hash表
2.1 hash表的组成
typedef struct dictht {
//是一个entry数组
dictEntry **table;
//hash表数组的大小,大小只能是2的n次方
unsigned long size;
//用来计算hash的槽位置的掩码,永远为size-1
unsigned long sizemask;
//总的hash entry大小
unsigned long used;
} dictht;
typedef struct dictEntry {
//entry的key
void *key;
//entry的value
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//为了解决hash冲突,所以会指向下一个节点,形成链表
struct dictEntry *next;
} dictEntry;
可以看出,hash表底层是一个entry数组,数组大小为size,而且大小永远为2的n次方,每次数据来过后,会进行hash运行然后对size求余,得到第几个hash槽(这步操作可以等价于hash&sizemask)。而为了解决hash冲突的问题,redis采用的是链地址法,会将元素插入到头部形成一个链表。所以其数据结构如下:
3.字典
3.1 字典的组成
//字典
typedef struct dict {
//用于创建不同类型的字典,指向的是dictType,里面包含了不同的hash操作的函数
dictType *type;
void *privdata;
//两个hash表,h[0]和h[1],其中h[1]用来进行rehash
dictht ht[2];
//当前rehash的地址,如果为-1表示当前未开始rehash
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
字典的主要组成是两个hash表,h[0]和h[1]。所以结构如下
3.2 渐进式rehash
3.2.1 什么时候进行rehash
当use/hash槽数量大于1并且没有开始进行save或者background save等持久化操作的时候,或者use/hash槽数量大于5的时候,会开始进行rehash。
3.2.2 rehash的步骤
1.先为h[1]申请一片空间,大小为大于当前use的最小的2的n次方。
2.rehashidx加1,并且将h[0]中索引为rehashidx上的链表搬至h[1]中。
3.如果rehashix已经等于数组大小,表示已经rehash完成,将让h[0]指向h[1],并且设置h[0]为null。