阿里面试官：谈谈对Redis哈希表的理解

很多朋友问我能不能搞个八股文精讲，把面试问题讲透，于是系列就这样诞生了。让我们在第一期谈谈Redis。

相信大家对哈希表并不陌生，今天顺便说一下，谈谈Redis的哈希表。

哈希表是一种存储数据的结构，它有许多名称（键值对、字典、符号表、映射和相关数组）。在哈希表中，键和值是一个对应的关系，一个键key对应于一个值value。哈希表的数据结构可以通过键key在o（1）时间复杂性下获得相应的值。

Redis实现了Hash表，因为C语言本身没有内置哈希表的数据结构。

哈希表最关键的问题是哈希冲突。也就是说，两个项目，经过哈希函数计算，发现相应的存储位置是相同的。在这种情况下，需要进一步处理。

每个人都应该背诵我写的数据结构和算法八股文背诵版，还记得解决Hash冲突的方法吗？

该方法的核心是：一旦发生冲突，项目将顺延.

让我们举个例子。

1. 按照hash算法，新键值应该有箭头的位置，但这个位置是值得的：

开放地址法

2. 因此，需要存储顺延的位置：

开放地址法

3. 顺延位置也是值得的，然后顺延

开放地址法

3. 顺延位置还是有值的，然后顺延，最后存放在上面

开放地址法

Redis所采用的方法是拉链法。让我们看看下面的例子。新键值的计算应存储在2号中。此时，2号已经有了正确的键值。因此，通过链表直接挂在2号键值对1的下方。

拉链法

新的键值对也是如此，通过链表挂在二号键值对2下。

在谈论rehash之前，首先需要引入一个定义:负载因子。让我们来看看负载因子的定义:

负载因子 = 散列表中元素的数量/散列表的长度

假如负载因子高，说明哈希冲突的概率高，这将严重降低搜索效率。

假如负载因子低，说明这个哈希表似乎占用了太多的空间，大部分空间都没有元素。

该程序需要扩展或收缩哈希表，以使负载因子值在合理范围内。由于空间变大或缩小，以前的键在旧表的存储位置，在新表中不一定相同，需要重新计算。重新计算并将旧表元素转移到新表元素的过程称为rehash。无论是java中的hashmap，concurrenthashmap，还是今天要讲的Redis哈希表，都涉及到rehash过程。

让我们来看看RedisHash表的逻辑设计结构 Redis的哈希表主要由三个结构组成：

1. dictht。简单地表示一个哈希表
2. dictEntry。哈希表中的一个，可以看作是一个键值对。
3. dict。Redis将哈希表结构调用到外层，包括两个dicththt

typedef struct dictht {     dictEntry **table; ///哈希表数组(哈希表集合)    unsigned long size; //Hash表大小     unsigned long sizemask; ///哈希表掩码    unsigned long used;//Hash表已使用的尺寸} dictht;

稍微解释一下每个项目。

1. table：指针数组哈希表项
2. size：不需要解释哈希表的大小。
3. sizemask:掩码。其实这个值的设计思路很棒。假设Redis的长度是3，你想访问第五个元素。如果按照之前的方法，一定要访问超出Redis哈希表范围的地址空间。因此，Redis规定，如果你想访问元素，首先要做好index和size，切断超过redis长度的部分，这样就不会出现内存安全问题。
4. 使用Hash表的大小。不解释。

说到Hash表，我们来看看哈希项。

typedef struct dictEntry {     void *key;     union {         void *val;         uint64_t u64;         int64_t s64;         double d;     } v;     struct dictEntry *next;} dictEntry;

众所周知，Redis采用拉链法解决哈希冲突问题。因此，Redis的哈希表项有一个next指针，指向下一个元素。通过这个指针，您可以访问多个具有相同哈希值的键对。

最后，让我们来看看dict结构。

typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2];    int reshaidx;} dict;

大家一定很好奇，好好dict，做两个哈希表怎么办？当然也有不好奇的朋友，但是忍不住面试官也很好奇。

答案显示，两个hash表是为了rehash。

在什么情况下需要rehash？

• 如果redis没有在执行后台备份，则当负载因子大于或等于1时执行。(反正CPU闲着也闲着)
• 如果redis在执行后台备份，则当负载因子大于或等于5时执行。(CPU正在进行备份，所以我们会改变真正挤压的表格。CPU闲置后，我们会稍微挤压rehash。)

让我们来看看需要rehash的执行步骤：

1. 给ht[1]分配空间。分配空间由ht[0]的具体参数决定。
2. 将ht[0]存储的键值对，重新计算hash值和索引值，并赋值到ht[1]的相应位置。
3. 赋值完成后，释放ht[0]占用的空间，并将ht[0]指向ht[1]当前地址。
4. ht[1]指向空表。

由于第二步采用的计算方法如果在一定时间内完成，占用的资源过高，redis提出了一种渐进的rehash方法。以白话为例，原来是一次一次搬运，现在已经成为分批搬运。

在分批搬运过程中，不可避免地会收到各种其他要求。

1. 当redis哈希表添加新的键值时，redis将数据直接存储在ht[1]表中。
2. 对于查询请求，即查询特定键对应的值时，redis首先会在ht[0]中查找，如果查找失败，则会在ht[1]表中查找。
3. redis将首先在ht[0]中搜索更新请求，如果搜索失败，将在ht[1]表中更新。
4. redis将首先在ht[0]中搜索删除请求，如果搜索失败，将在ht[1]表中删除。