数据库数据字典举例(非关系型数据库Redis之字典)

【本文详细介绍了非关系型数据库Redis中字典的基本概念和使用方法，欢迎读者朋友们阅读、转发和收藏！】

字典，简单说就是存储 key-value 键值数据，当然 value=NULL 那么就是集合了。字典通俗来说就是 C++ STL 中的 map ， STL 中的 map 是用 red-black tree 实现的，因为 map 不仅能够保证 key 不重复，而且 key 还是按照字典序存储的，而 Redis 中的字典并不要求有序，因此为了降低编码的难度使用哈希表作为字典的底层实现。 Redis 的字典是使用一个桶 bucket ，通过对 key 进行 hash 得到的索引值 index ，然后将 key-value 的数据存在桶的 index 位置， Redis 处理 hash 碰撞的方式是链表，两个不同的 key hash 得到相同的索引值，那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候，字典不免会退化成多个链表，效率大大降低， Redis 采用 rehash 的方式对桶进行扩容来解决这种退化。

Redis 使用的 hash 算法有以下两种：

1. MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好，具体信息请参考 MurmurHash 的主页： http://code.google.com/p/smhasher/ 。

2. 基于 djb 算法实现的一个大小写无关散列算法：具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html 。

可参看源码

通过 dictCreate 函数创建一个新字典 dict *dictCreate(dictType *type, void *privDataPtr)

根据字典当前的状态，将一个 key-value 元素添加到字典中可能会引起一系列复制的操作：

Ø 如果字典未初始化（即字典的 0 号哈希表 ht[0] 的 table 为空），那么需要调用 dictExpand 函数对它初始化；

Ø 如果插入的元素 key 已经存在，那么添加元素失败；

Ø 如果插入元素时，引起碰撞，需要使用链表来处理碰撞；

Ø 如果插入元素时，引起程序满足 Rehash 的条件时，先调用 dictExpand 函数扩展哈希表的 size ，然后准备渐进式 Rehash 操作。

Rehash 的触发机制：当每次添加新元素时，都会对工作哈希表 ht[0] 进行检查，如果 used （哈希表中元素的数目）与 size （桶的大小）比率 ratio 满足以下任一条件，将激活字典的 Rehash 机制： ratio=used/size ， ratio>=1 并且 dict_can_resize 为真； ratio 大于变量 dict_force_resize_ratio 。

Rehash 执行过程：创建一个比 ht[0].used 至少两倍的 ht[1].table ；将原 ht[0].table 中所有元素迁移到 ht[1].table ；清空原来 ht[0] ，将 ht[1] 替换成 ht[0] 。

渐进式 Rehash 主要由两个函数来进行：

_dictRehashStep: 当对字典进行添加、查找、删除、随机获取元素都会执行一次，其每次在开始 Rehash 后，将 ht[0].table 的第一个不为空的索引上的所有节点全部迁移到 ht[1].table ；

dictRehashMilliseconds: 由 Redis 服务器常规任务程序 (serverCron) 执行，以毫秒为单位，在一定时间内，以每次执行 100 步 rehash 操作。