字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。在字典中，一个键可以和一个值进行关联，这些关联的键和值称为键值对。键值对中键是唯一的,我们可以根据键key通过映射查找或者更新对应的值value。
很多高级开发语言有对应集合支持字典这种数据结构，比如Java中的Map集合。C语言并未内置字典这种数据结构，Redis构建了自己的字典实现。
应用
字典在Redis中应用非常广泛，Redis数据库就是使用字典作为数据底层的实现。对数据的增、删、改、查操作也是建立在字典之上操作。
当执行命令：
set msg "hello"
在数据库中创建一个键为 msg数据字典表设计，值为 hello 的键值对，这个键值对就用字典来实现的。创建其他数据类型的键值对，比如list、hash、set、sort set也是用字典来实现的。
处理用来表示数据中的键值对，字典还是hash数据类型底层实现之一数据字典表设计，比如一个hash数据类型website，包含100个键值对，这些键值对中的键是网址名称，值是网页地址:
redis> HGETALL website
1)"Redis"
2)"Redis.io"
3)"nacos"
4)"nacos.io"
.....
website键的底层就是一个字典，包好了100个键值对，例如：
字典的实现
Redis字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点，每个哈希表节点保存字典中的键值对。
哈希表
Redis字典使用的哈希表由 dict.h/dictht 结构来表示：
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
// table 数组
dictEntry **table;
// 哈希表的大小
unsigned long size;
// 等于size-1，用于计算索引值
unsigned long sizemask;
// 已有的键值对数量
unsigned long used;
} dictht;
注释：这是哈希表结构，每个字典有两个实现增量重散列，从旧的哈希表到新的哈希表。
下图展示一个大小为4空哈希表（没有包含任务的键值对）：
哈希表节点
哈希表节点使用dictEntry结构来表示，每个dictEntry结构都保存着一个键值对：
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下一个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
其中：
下图展示两个键的hash值相同的哈希表节点k0和k1，两者通过next指针连接在一起。
字典
Redis 中的字典由dict.h/dict结构表示：
typedef struct dict {
// 类型特定的函数
dictType *type;
// 私有函数
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
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;
下图为一个普通状态下（没有进行rehash）的字典：
哈希算法
当要将一个新的键值对添加到字典中，程序需要先根据键值对中的键计算出哈希值和索引值，然后根据索引值，将包含新键值的哈希表放在哈希表数组的指定索引上。
Redis计算哈希值和索引值的步骤如下：
使用字典设置的哈希函数，计算键的哈希值。
hash = dict—>type->hashFunction(key)
使用哈希表的sizemask属性和哈希值，取余计算出哈希值。
index = dict ->ht[x].sizemask & hash
了解过HashMap底层原理的同学应该知道，上面计算索引值和HashMap找到索引下标的原理是类似的。
什么是取余&运算？
取余就是计算两数相除的余数， 比如一个数组长度为4，索引范围是0~3,需要放置0,1,7，放置如下图所示：
举个例子，要将一个键值对k0和v0添加到下方的空字典表中：
首先计算键的哈希值：
hash = dict—>type->hashFunction(key)
计算键k0的哈希值。 假设计算出来的哈希值为8，然后计算索引值：
index = dict -> ht[0].sizemask & hash = 3 & 8 = 0;
计算出键k0的索引值0，这表示键值对k0和v0的节点放置到哈希表数组下标0的位置上，如下图所示：
键冲突
当两个或者两个以上的计算出数组索引值一致时，就发生了键冲突。
Redis的哈希表采用链表法来解决键冲突，每个哈希表的节点都有一个next指针，多个哈希表节点用next指针组成一个单链表，被分配到同一个数组索引上的多个节点使用单向链表连接起来，这就很好的解决了键冲突的问题。
举个例子，程序要将一个键值对k2和v2添加到下图的哈希表中，并且计算k2的索引值为2,那么键k1和k2将发生冲突：
解决冲突的办法就是使用next指针将k2和k1所在的节点连接起来，如下图所示：
总结参考
Redis设计与实现
———END———
限 时 特 惠：本站每日持续更新海量各大内部创业教程，一年会员只需128元，全站资源免费下载点击查看详情
站 长 微 信：jiumai99