纸上得来终觉浅，绝知此事要躬行！

哈希，对于大家来说应该是比较熟悉的一种数据结构了，因为大多数的编程语言都实现了哈希结构，可能叫法不一样而已，比如字典。而且哈希的应用场景也是非常的多，就拿Redis来说，其实它本身就是一个大的哈希结构的数据库。

这里我们说的哈希结构，指的是Redis键值对中值的类型是哈希类型，也就是说值本身也是一个键值对结构。

我们按三部分来介绍：

1. 内部编码
2. 常用命令
3. 典型应用场景

内部编码

哈希类型的内部编码有两种：压缩列表ziplist和哈希表hashtable。

有两个参数控制何时使用ziplist，何时使用hashtable，这两个参数在配置文件中，可以自由配置：

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

注释的意思：当哈希有少量的条目，并且最大的条目不超过给定的阈值时，使用内存高效的数据结构对其进行编码。可以使用以下指令配置这些阈值。需要注意的是，这两个参数的条件是并且的关系，也就是说，当不满足其中之一的时候，内部编码就自动变成hashtable了。那这两个参数是什么意思呢？从名字来看，其实大概可以猜出来：hash-max-ziplist-entries表示哈希中元素个数，默认是512个；hash-max-ziplist-value表示哈希中每个元素的值的大小，默认是64字节。当哈希类型中元素个数和大小满足参数配置时，Redis默认使用ziplist来存储哈希类型。

那么，ziplist和hashtable有什么区别呢？从配置看，当数据膨胀之后，才会使用hashtable作为内部编码，那么ziplist在小数据量时应该是比hashtable更有优势。

（1）压缩列表ziplist

压缩列表ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，它的结构如下

其中：zlbytes表示整个压缩列表占用的内存字节数，在内存重分配或者计算zlend的时候使用，是一个4字节的整型；zltail表示压缩列表表尾节点距离压缩列表的起始地址有多少个字节，通过这个偏移量，可以直接计算出表尾的地址，无需遍历压缩列表，也是一个4字节的整型；zllen表示压缩列表的节点数量，值得注意的是，这是一个2字节的整型，所以能表示的最大数量是65535，当zlen值是65535时，说明压缩列表的节点数量可能超过了能表示的最大数量，这时，需要遍历压缩列表才能得到真实的节点数量；field1、value1..等等表示的是压缩列表中的一个个节点，其中field表示哈希键，value表示哈希值；zlend是用来标记压缩列表的末端，是一个特殊值0xFF，即十进制的255。

在这个例子中，压缩列表总长度zlbytes为0x50，即80字节；zltail为0x3c，也就是说假如有一个指针指向压缩列表的起始位置，那么这个指针加上偏移量60，就可以计算出表尾节点的地址；zllen为0x4，表示包含4个节点。

每当有新的键值对加入到当前的哈希对象中时，程序会先将键构造成节点，推到压缩列表的表尾，然后把值构造成节点，推到压缩表的表尾，也就是说同一键值对的键节点和值节点是挨在一起的，键在前，值在后。

那么，压缩列表的节点构成是怎么样的呢？

为了行文方便，我们姑且称之为节点。我们首先要知道节点存储的是什么，然后才去讨论该怎么存。对于哈希类型来说，ziplist的节点包含哈希的键和哈希的值，不管是键还是值，最终在内存中都是两种类型：字节数组或者整数值。那节点如何区分存的是字节数组还是整数值呢？答案就在节点的结构上

节点的结构分为三个部分：

• prus_entry_length表示前一个节点的字节长度，这部分占用1个或者5个字节，如果前一个节点的字节长度小于254字节（一个字节能记录下），那就占用1个字节，如果长度大于254个字节，就占用5个字节，其中首个字节设置为0xFE，标志该部分占用五个字节记录长度，其余部分记录真实的长度。这部分的主要作用，其实是为了方便从表尾向表头遍历，假如有一个指向某个节点的指针，那么通过该属性就可以计算前一个节点的起始地址，最终回溯到表头；

• encoding记录的是content里保存的数据的编码和长度，这部分占用1个或者2个或者5个字节。上边说过，节点保存的是字节数组或者整数值，encoding通过最高两位（首个字节的前两位）来区分是字节数组还是整数值，如下表所示，“_”表示留空，b、x等字母位用来表示实际的二进制数据，为了方便阅读，多个字节用空格分隔

• content就比较简单了，就是保存的真正的值，至于它的类型和长度，encoding中已经记录了。

说到这，大家可能有疑问了，previous_entry_length记录了前一个节点的长度，而且自身长度是不固定的，那如果前一个节点的长度改变了，确切的说是从小于254变成大于254或者反之，那当前节点的pervious_entry_length就需要增加到5个字节或者缩小到1个字节记录长度，如果这个属性的改变，导致当前节点的长度也从小于254变成大于254或者反之，同样会导致其后继节点的改变，以此类推，就会发生连锁更新的问题，除了更新，删除也会导致连锁更新。确实，连锁更新的问题确实存在，而且复杂度比较高，但是，它真正能造成性能问题的概率非常低，原因有二：一、当压缩列表中有多个连续的、且长度介于250字节到253字节之间的节点，连锁更新才有可能引发，在实际情况中，这非常少见；二、即使发生连锁更新，但是只要是连锁更新的节点数量不多，也不会对性能造成影响，比如说三五个节点的连锁更新是绝对不会影响性能的。也就是说，发生连锁更新的条件非常苛刻，正常情况下，几乎不可能。

最后要说一下，ziplist的时间复杂度平均是O(n)。

（2）hashtable内部编码的实现

另外一种编码是hashtable，它是用Redis底层的字典结构实现的，其实又是一个哈希表。说到哈希表，就必然涉及到哈希算法、哈希冲突、rehash等共性问题。

Redis使用MurmurHash2算法来计算哈希值，这种算法的优点是，即使键是有规律的，算法仍然能给出一个很好的随机分布性，并且算法的速度也是非常快的。

至于哈希冲突，Redis采用的是链地址法解决冲突，每个节点都有一个next指针，通过指针链接哈希到同一个索引上的节点。

关于rehash，需要先介绍一下字典的结构

typedef struct dict {
	dictType *type;
  void *privdata;
  // 哈希表
  dictht ht[2];
  // rehash索引
  in trehashindex;
} dict;

在字典的定义中，哈希表定义了一个长度为2的哈希表数组，一般情况下，字典只是用ht[0]哈希表，ht[1]哈希表只会在对ht[0]进行rehash时使用。还有一点需要注意的是，rehash不是一次性完成的，而是分多次，渐进式的完成的，也叫作渐进式rehash。因为，当哈希表中键值对数量非常多的时候，一次性rehash所进行的庞大计算量可能导致服务在一段时间内停止对外服务，也就是阻塞，对性能有很大的影响，不符合Redis的设计初衷，所以通过渐进式rehash一点点慢慢的把ht[0]中的键值对rehash到ht[1]中。rehash的步骤：1、对ht[1]分配空间，如果是扩容，分配空间大小是第一个大于等于ht[0]中键值对数量*2的2的n次幂，如果是收缩，分配空间是第一个大于等于ht[0]键值对数量的2n；2、把ht[0]中的所有键值对重新rehash到ht[1]上，这个过程是渐进式的，如果在rehash的过程中，对字典进行添加、修改、删除等操作，会同步在两个哈希表上进行，直到ht[0]中的键值对全部迁移到ht[1]中；3、释放ht[0]，将ht[1]设置为ht[0]。

那字典什么时候扩容，什么时候收缩呢？这和负载因子有关，负载因子的计算方式是哈希表已保存节点数量/哈希表大小。当服务器没有执行BGSAVE或者BGREWRITEAOF时，负载因子大于等于1就扩展；当服务器执行BGSAVE或者BGREWRITEAOF时，负载因子大于等于5就扩展；当负载因子小于0.1时，收缩。

常用命令

（1）设置值、获取值、删除值

（2）统计键数量

（3）批量设置、批量获取

（4）判断键是否存在

（5）获取所有键、所有值、所有键值

需要注意的是，如果键值个数比较多，使用hgeall时可能会有阻塞Redis的可能，可以使用hmget获取部分键或者使用hscan获取全部键。

（6）渐进式遍历

（7）键值自增

使用场景

就像常用命令里的示例一样，哈希最普遍的使用场景就是缓存类用户信息数据，相对于使用普通的字符串去保存这类信息，使用哈希有以下优点

1. 内存占用少，使用字符串保存的时候，要为没一个field设置一个Redis键，而Redis键除了键本身外，还需要额外的结构保存其他信息，占用一定量的内存，需要注意的是，如果编码转换为hashtable后，可能占用内存反而会更多；
2. 每一个field的可以单独添加、更新、删除，相对来说字符串必须整体操作；
3. 数据直观，如果把信息序列化成一定格式后，用字符串保存也会直观，但是序列化反序列化有一定的开销；