Redis技术实现详解--数据结构之Hash(字典)

Redis中的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了一个键值对，接下来分别介绍一下Hash存储结构相关的哈希表节点、哈希表以及字典数据结构。

typedef struct dictEntry {

// 键

void *key;

// 值

union {

void *val;

uint64_t u64;

int64_t s64;

} v;

// 指向下个哈希表节点，形成链表

struct dictEntry *next;

} dictEntry;

key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。举个例子， 下图就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起

上图中除了展示了哈希表节点的结构外，也已经展示了哈希表的结构(其中左边的dictht就是哈希表的结构)

typedef struct dictht {

// 哈希表数组

dictEntry **table;

// 哈希表大小

unsigned long size;

// 哈希表大小掩码，用于计算索引值

// 总是等于 size - 1

unsigned long sizemask;

// 该哈希表已有节点的数量

unsigned long used;

} dictht;

a.table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry 结构的指针，每个dictEntry结构保存着一个键值对。

b.size属性记录了哈希表的大小，也即是table数组的大小，而used属性则记录了哈希表目前已有节点(键值对)的数量。

c.sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。

Redis中的字典结构包含了两个哈希表，但是在实际使用的时候只会使用到其中一个dictht[0],dictht[1]只有在rehash的时候才会使用大，并行在rehash结束之后会将dictht[0],dictht[1]俩互换一下位置。

字典的数据结构如下所示：

typedef struct dict {

// 类型特定函数

dictType *type;

// 私有数据

void *privdata;

// 哈希表

dictht ht[2];

// rehash 索引

// 当 rehash 不在进行时，值为 -1

int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;