1. 前言

如果了解HashMap，那本篇会很容易理解

2. 键值的组织结构

为了实现从key到value的快速访问，Redis使用哈希表来保存所有键值对，这个哈希表其实就是一个数组；数组的每个元素称为一个哈希桶；所以常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

哈希桶中的entry元素中保存了key的指针和value的指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过value指针被查找到。

如上图所示，这个哈希表保存了所有的键值对，可以将它称为全局哈希表。

使用哈希表的最大好处很明显，就是可以用O(1) 的时间复杂度来快速查找到键值对，而使用者只需要计算key的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的entry元素。

这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系；也就是说不管哈希表里有10 万个key还是100 万个key，只需要一次计算就能找到相应的键。

不过当往Redis中写入大量数据后，可能会发现操作有时候会突然变慢了，这其实可能是哈希表的冲突问题和rehash带来的操作阻塞。

向哈希表中写入更多数据时，哈希冲突是不可避免的问题。

这里的哈希冲突是指：两个key的哈希值相同，都落在了同一个哈希桶中；
毕竟哈希桶的个数通常要少于key的数量，这也就是说，难免会有一些key的哈希值对应到了同一个哈希桶中。

redis解决哈希冲突的方式是采用链式哈希（链表），就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

这样就会出现一个问题，如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，查找效率降低。

所以Redis会对哈希表做rehash操作，rehash也就是增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

为了使rehash操作更高效，Redis默认使用了两个全局哈希表：哈希表1和哈希表2，
一开始，当刚插入数据时，默认使用哈希表1，此时的哈希表2并没有被分配空间；随着数据逐步增多，Redis开始执行rehash。

给哈希表2分配更大的空间，例如是当前哈希表 1 大小的两倍；
渐进式rehash
Redis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到哈希表 2 中；
等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的entries。
释放哈希表1的空间

这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。