数据结构-字典

字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对

哈希表

哈希表由dict.h/dictht结构定义

typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于size-1 unsigned long sizemask; // 哈希表已有节点的数量 unsigned long used; } dictht;

table 是一个数组，里面每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存一个键值对。size属性记录哈希表的大小，即table数组的大小，used属性记录所有节点的数量，sizemask属性等于size-1,用来计算一个键放到table数组上哪个索引上面

哈希表节点

typedef struct dictEntry { // 键 void *key; // 值 union { void *val; unit64_tu64; int64_ts64; } // 指向下个哈希表节点，形成链表 struct dictEntry *next; }dictEntry;

字典

字典由 dict.h/dict 结构表示

typedef struct dict { //类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当rehash不在进行时，值为-1 int rehashidx; }dict;