源码文件在 dict.h 和 dict.c 中
哈希表节点定义
哈希表节点使用 dictEntry 结构表示，一个dictEntry 是一个键值对
typedef struct dictEntry {
// 键
void *key;
// 值，可以是指针，可以是uint64_t 或者int64_t
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
//使用链表法解决哈希冲突问题
struct dictEntry *next;
} dictEntry;
哈希表定义
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
table 属性是一个数组， 数组中的每个元素都是一个指向 dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
当为table申请内存的时候，假设要设置哈希表大小为 len，那么申请的内存大小为 len * sizeof(dictEntry *)，len乘以一个指针类型所占的大小，因为 table[i] 也是一个指针。然后让 size = len
sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
下图展示了大小为4的一个哈希表的结构，键 k1和k0索引相同，也就是出现了哈希冲突，使用链表解决哈希冲突。并且，当一个新的索引相同的结点加入，总是把新结点插入链表的头部
image.png
字典定义
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx;
} dict;
type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：
- type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
- 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。
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;
ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1
普通状态下（没有进行rehash）的字典
image.png
字典迭代器
typedef struct dictIterator {
// 被迭代的字典
dict *d;
// table ：正在被迭代的哈希表号码，值可以是 0 或 1 。
// index ：迭代器当前所指向的哈希表索引位置。
// safe ：标识这个迭代器是否安全
int table, index, safe;
// entry ：当前迭代到的节点的指针
// nextEntry ：当前迭代节点的下一个节点
// 因为在安全迭代器运作时， entry 所指向的节点可能会被修改，
// 所以需要一个额外的指针来保存下一节点的位置，
// 从而防止指针丢失
dictEntry *entry, *nextEntry;
long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
} dictIterator;
如果 safe 属性的值为 1 ，那么在迭代进行的过程中，程序仍然可以执行 dictAdd 、 dictFind 和其他函数，对字典进行修改。
如果 safe 不为 1 ，那么程序只会调用 dictNext 对字典进行迭代，而不对字典进行修改。
特定函数
由 struct dictType 衍生出一系列宏定义函数
dictSlots
返回给定字典的大小
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
dictSize
返回字典的已有节点数量
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
dictIsRehashing
查看字典是否正在 rehash
#define dictIsRehashing(ht) ((ht)->rehashidx != -1)
dictFreeKey
释放给定字典节点的键
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key)
dictSetKey
设置给定字典节点的键
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
entry->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
entry->key = (_key_); \
} while(0)
dictFreeVal
释放给定字典节点的值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
dictSetVal
设置给定字典节点的值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
entry->v.val = (_val_); \
} while(0)
dictSetSignedIntegerVal
将一个有符号整数设为节点的值
#define dictSetSignedIntegerVal(entry, _val_) \
do { entry->v.s64 = _val_; } while(0)
dictSetUnsignedIntegerVal
将一个无符号整数设为节点的值
#define dictSetUnsignedIntegerVal(entry, _val_) \
do { entry->v.u64 = _val_; } while(0)
dictCompareKeys
比对两个键
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
dictHashKey
计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
dictGetKey
返回获取给定节点的键
#define dictGetKey(he) ((he)->key)
dictGetVal
返回获取给定节点的值
#define dictGetVal(he) ((he)->v.val)
dictGetSignedIntegerVal
返回获取给定节点的有符号整数值
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
dictGetUnsignedIntegerVal
返回给定节点的无符号整数值
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
网友评论