字典是一种用于保存键值对的 抽象数据结构 ，也被称为查找表、映射或关联表。
在字典中，一个 键 （key）可以和一个值（value）进行关联，这些关联的 键 和值就称之为键值对。
抽象数据结构，啥意思？就是可以需要实际的数据结构是实现这个功能。抽象，意味着它这是实现功能的标准，凡是能够完成这些功能的都可以是其实现。
redis的字典
字典作为一种数据结构内置在很多高级编程语言里面，但是redis是基于C语言进行开发的，所以没有内置这种数据结构，redis只能构建自己的字典实现。
字典通常可以由两种底层数据结构组成，分别是线性表（数组）和hash表。而redis一般是采用hash表的方式进行构建
redis字典为啥不用线性表实现
字典基于用线性表实现，如果我这个字典有200个键值对，那么我就开辟一个长度为200的数组对这些元素进行放置。
基于线性表实现的字典的优缺点很明显：
1、实现简单，适用于任意关键字类型。
2、平均检索效率低（线性时间），表长度n比较大时，检索比较耗时。
3、删除操作的效率比较低，不太适合频繁变动的字典。
字典在插入删除上的频繁让线性表无法胜任此任务。
推荐观看：Redis实战精讲
哈希如何实现字典
之前写过一篇文章，关于java中的hashcode解析，有兴趣的读者可以回看下一些经典的hash函数和实现
面试官问我：hashcode 是什么？和equals是兄弟吗？
redis字典所使用的 哈希表 由dict.h/dictht组成
typedef struct dictht {
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小，即哈希表数组大小
unsigned long sizemask; //哈希表大小掩码，总是等于size-1，主要用于计算索引
unsigned long used; //已使用节点数，即已使用键值对数
}dictht;
可以看到redis声明了一个结构体，里面由一个哈希表数组，哈希表数组大小的long值，一个用于计算索引的哈希表大小掩码以及已使用的节点数构成。
这个哈希表数组，存放的是哈希节点dicEntry，我们会将key-value键值对给它放进去。
typedef struct dictEntry {
void *key; //存放key值
union {
void *val; //存放value值
uint64_t u64; //uint64_t整数
int64_t s64; //int64_t整数
}v;
struct dictEntry *next; //指向下个哈希表节点，形成链表
}dictEntry;
如图所示就通过next指针来将两个索引相同的键k1和k0连接在一起。
Redis 中的 字典 由 dict.h/dict 结构表示：
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
可以看到字典里有一个长度为2的哈希表数组，那么为啥不是三个四个甚至更多呢？感觉哈希表越多不是效率更快吗？
其实设置2的原因在于，h[0]用于存储，h[1]用于当容量不足时进行扩充,更多的哈希表也用不上，反而可能在扩充时要同步成为性能瓶颈。
字典如何增添一个元素
当要将一个新的键值对加入到字典中的时候，首先要计算这个key的哈希值和索引值，然后再根据这个索引值放入字典中h[0]的索引位置
举个例子， 对于图 4-4 所示的字典来说， 如果我们要将一个键值对 k0 和 v0 添加到字典里面， 那么程序会先使用语句：
hash = dict->type->hashFunction(k0);
计算机 k0 的哈希值。
假设计算得出的哈希值为 8 ， 那么程序会继续使用语句：
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;
计算出键 k0 的索引值 0 ， 这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上， 如图 所示。
什么时候会进行扩容
按照java中hashmap的说法，当负载因子 loadFactor>0.75 的情况下会进行扩容
在redis中，字典里的哈希会根据以下两种情况进行扩容：
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；
其中哈希表的负载因子可以通过公式：
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
渐进式rehash如何实现
首先要清楚为什么rehash的时候要渐进式。
这就好比去参加高考，肯定是初中毕业后读三年高中，一点点学习高中知识后才可以参加高考，这才可以取得不错的成绩。学习是循序渐进的，hash也要，不然中考完直接去参加高考，这谁顶得住啊。
Rehash操作分为两种：
扩展：当负载因子较大时，应该扩大 dictht::size 以降低平均长度，加快查询速度。
收缩：当负载因子较小时，应该减小 dictht::size 以减少对内存的浪费。
当整体的数据量比较少，如百八十个key-value对存储的时候，hash的过程肯定耗时不会很多。但是在生产环境下，一个数据库下key-value值都是有百万级别的，在进行rehash操作的时候势必会达到秒级别的运算。所以这个hash的过程不是一次性集中的完成，而是分多次渐进式的完成。
以下是哈希表渐进式 rehash 的详细步骤：
- 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
- 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
- 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增1。
- 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
rehash的过程中有数据变化怎么办
关于字典的操作无非就是四个，增删改查。
操作类型过程增加直接将key-value对增加到h[1]中删除先删除h[0]，再删除h[1]修改直接修改h[1]查找先在h[0]中查找，查询不到再到h[1]中
这样就能保证redis在h[0]上是只少不多，所有的记录都会被迁移到h[1]上。
如何解决哈希碰撞
这个问题还是我面试腾讯的时候面试官问我的原题。
一开始我说了两个思路，一个是无限增大线性表的容量，一个是采用数组+链表的方式。
面试官：对这两个都是构成hash的方式，但是如果我的两个键值对的hashcode是一样的呢？
我：那就可以将这个hash算法设计的复杂化，比如hash里头再嵌套一层hash，这样碰撞的几率就会变小了。
面试官：这种方法其实也是可以的，那还有没有其他方法呢？
我：....（支支吾吾中）
然后面试就结束了orz
其实还有另一种方法我不知道就是公共溢出区法
建立一个公共溢出区，假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
转自公众号： JerryCodes
如果觉得本文对你有帮助，可以关注一下我公众号，回复关键字【面试】即可得到一份Java核心知识点整理与一份面试大礼包！另有更多技术干货文章以及相关资料共享，大家一起学习进步！
京公网安备 11010502036488号