Redis源码学习之[哈希字典]
介绍
Redis的哈希字典通过key值来找对应的value。需要注意的是Redis的字典是如何进行rehash的。
源码
dict.h dict.c
数据结构
如上图所示，哈希字典用dict结构体表示，其中含有两个哈希表，主要用于进行rehash操作。同时哈希表使用量表的方式解决冲突。具体的数据结构如下：
[cpp]
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 链往后继节点
struct dictEntry *next;
} dictEntry;
/*
* 特定于类型的一簇处理函数
*/
typedef struct dictType {
// 计算键的哈希值函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);
// 对比两个键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 键的释构函数
void (*keyDestructor)(void *privdata, void *key);
// 值的释构函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
/*
* 哈希表
*/
typedef struct dictht {
// 哈希表节点指针数组（俗称桶，bucket）
dictEntry **table;
// 指针数组的大小
unsigned long size;
// 指针数组的长度掩码，用于计算索引值
unsigned long sizemask;
// 哈希表现有的节点数量
unsigned long used;
} dictht;
/*
* 字典
*
* 每个字典使用两个哈希表，用于实现渐进式 rehash
*/
typedef struct dict {
// 特定于类型的处理函数
dictType *type;
// 类型处理函数的私有数据
void *privdata;
// 哈希表（2个）
dictht ht[2];
// 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
int rehashidx;
// 当前正在运作的安全迭代器数量
int iterators;
} dict;
/*
* 字典迭代器
*
* 如果 safe 属性的值为 1 ，那么表示这个迭代器是一个安全迭代器。
* 当安全迭代器正在迭代一个字典时，该字典仍然可以调用 dictAdd 、 dictFind 和其他函数。
*
* 如果 safe 属性的值为 0 ，那么表示这不是一个安全迭代器。
* 如果正在运作的迭代器是不安全迭代器，那么它只可以对字典调用 dictNext 函数。
*/
typedef struct dictIterator {
// 正在迭代的字典
dict *d;
int table, // 正在迭代的哈希表的号码（0 或者 1）
index, // 正在迭代的哈希表数组的索引
safe; // 是否安全？
dictEntry *entry, // 当前哈希节点
*nextEntry; // 当前哈希节点的后继节点
} dictIterator;
分析
rehash
在字典中使用了两个hash表就是为了方便进行rehash的，rehash主要有两种方式，一是由后台调用cron进行按照100步进进行hash，二是在进行添加删除字典中的元素的时候进行1步的hash。
这里每一次的hash的步进是以真个hash key对应的链表为单位的，也就是说1步进的rehash是将原来hash表中的一个key链表进行rehash到新的哈希表中的位置。这里可以看出Redis在此处是牺牲了内存但是换来了性能的响应。将rehash进行分散操作可以避免阻塞导致的性能急剧下降。www.zzzyk.com
迭代器
迭代器的属性如果是安全的则表明可以在迭代的过程中进行dictAdd等其他的操作，而如果迭代器是不安全的则只能进行next的操作。
同时Redis限制在有迭代器访问字典的时候进行rehash，因为这样会造成对一个元素访问多次。但是在rehash的过程中可以随时的对字典进行遍历，一旦迭代器开始遍历字典了，rehash就会暂停知道没有迭代器在对字典进行遍历为止。
补充：软件开发 , C++ ,
