Redis哈希表源码深度解析，技术大牛力荐，助你掌握底层数据结构

Redis的哈希表其实就是用了一个数组加链表的经典结构，当数据量大了以后，它会自动扩容，把数组变大，然后把老的数据一点点搬过去，这样你查东西就快了。

哈希表长啥样？

在Redis的源码里，哈希表主要是两个结构。一个叫"dictht"，你可以把它想象成一个装数据的架子。这个架子首先有一个数组，数组里的每个位置都能挂一条链子。然后还有一个数字记录这个数组现在有多大，另一个数字记录已经挂了多少个数据。

另一个更重要的结构叫"dict"，它管着两个上面说的那种架子。一个架子是平时用的，另一个架子是专门用来搬家的。搬家就是我们说的扩容或者缩容。这个"dict"结构里还有一些函数指针，比如怎么算一个键的哈希值，怎么比较两个键是不是一样。

它是怎么存东西的？

当你往Redis的哈希表里塞一个键值对，比如 hset myhash name "张三"，它先会拿这个键"name"去算一个哈希码。这个码是个很大的数。然后用这个数对数组的大小求个余数，得到的结果就是应该放在数组的第几个格子里。

数组的每个格子不直接放数据，它是一个链表的头。如果那个格子里已经有一个数据了（这叫哈希冲突），它就把新的数据做成一个节点，挂在链子的最前面。所以查找的时候，先找到格子，再顺着链子一个一个看是不是要找的键。

最重要的搬家（扩容/缩容）过程

这是哈希表最核心的聪明之处。它不会等到架子完全塞满了才扩容，那样就太慢了。它看两个条件：一是当前架子上的数据总数是不是已经比数组长度还大了；二是是否在搬家过程中。如果数据太多又没在搬家，它就启动扩容。

扩容就是新申请一个更大的数组，大小是原来的两倍左右（实际是比2的n次方大的最小2的n次方）。然后，它把原来旧架子上所有的数据，重新计算在新数组里的位置，一个一个挂到新架子上。这个过程不是一口气做完的，是每次你下次来访问或者修改哈希表的时候，它顺带着搬一两个。这样就不会因为一次性搬所有数据而导致Redis卡住半天不响应，这个设计非常巧妙。

缩容就是反过来，当数据删掉很多，数组显得太空旷了，它也会启动搬家，搬到一个更小的数组里，节省内存。

为什么技术大牛都推荐看这个？

因为这是一个教科书级别的工程设计。它把数据结构课本上的哈希表理论，用非常高效、实用的方式实现了出来，尤其是那个渐进式的搬家过程，完美平衡了性能和即时响应。理解了它，你就理解了大部分内存数据库处理海量键值对的核心思路，对你自己设计系统也大有帮助。

自己动手试一试

光看不行，最好能去读读源码。文件主要是Redis源码里的"dict.h"和"dict.c"。不用怕，代码写得挺清楚的。你可以先找找`dictAdd`函数，看看插入一个键值对是怎么走的。再找找`_dictRehashStep`函数，看看它每次是怎么搬一点点家的。跟着流程走一遍，印象就深了。

FAQ

1. Redis哈希表的扩容阈值是多少？为什么这么设计？
Redis哈希表的扩容触发条件是：哈希表中保存的节点数量（used）大于等于数组长度（size），并且此时没有在进行渐进式rehash。通俗讲，就是当数组的每个位置平均至少挂了一个数据时，就可能触发扩容。这么设计是为了在链表变得过长、影响查找效率之前，就提前扩大数组，将数据打散，保持O(1)查询时间复杂度的期望。它是在空间和时间效率间做了一个平衡。

2. 渐进式rehash期间，查找和删除操作怎么进行？
在渐进式rehash（搬家）过程中，字典（dict）同时持有两个哈希表（ht[0]和ht[1]）。当进行查找、删除或更新操作时，程序会先在旧的哈希表(ht[0])里找，如果没找到，并且正在rehash，就会再去新的哈希表(ht[1])里找一次。插入操作则一律只插入新的哈希表(ht[1])，这样保证旧表的数据只减不增，最终全部搬完。这个过程对用户是完全无感的。

3. 普通程序员需要看这个源码吗？
如果你只是使用Redis，那不需要。但如果你想深入理解高性能存储系统的设计精髓，或者面试时想给面试官留下深刻印象，或者自己遇到类似大量数据快速存取的设计难题，那非常值得一看。它是一份非常优质的学习材料，能帮你建立对底层数据结构的直觉。

引用来源：本文核心内容基于Redis 7.0.x版本开源代码，主要文件为 src/dict.h 与 src/dict.c。