Hash表与Dict及渐进式Rehash

1435597771 ·

Redis Hash是什么

RedisHash是Redis中的数据类型，他存储的是键值对数组。键值对数组中，每一个元素都是一个key-value成对出现。

RedisHash底层实现

RedisHash的底层实现数据结构是listpack和dict。在键值对数组个数小于512个,所有值小于64字节，那么就用listpack来存储键值对。

如果不满足上述条件，那么Redishash就会选择用Dict（也叫做哈希表，不过因为哈希表和Hash数据结构在字面上看上去是一个东西，所以就用Dict来表述哈希表，用作区分Hash数据结构）结构体来存储键值对数组。本文主要来介绍Dict结构体

Dict是什么

Dict是一个保存键值对的数据结构，他本质上是一个数组。为什么说他是数组，我们需要看Dict的结构体来说明。dict的字段有：

  • ht[2]：是两个dictht结构体，平时存放数据只存放进一个dictht中。

那么dictht的结构是什么样子的呢，他有几个字段需要说明

  • dictEntry **table: 是一个数组，数组中的元素存储的是 指向 dictEntry的指针。我们常说的hash桶就是指这个数组中的一个位置。实际的值就是存储在这个数组中元素指向的地址

  • size：dictht大小，表明dictEntry **table有几个元素

  • sizemask：dictht大小掩码，用来计算索引值

  • used：used是一个简单的累加计数器，代表当前哈希表里所有dictEntry` 节点（包含所有拉出来的链表节点）的绝对物理总数

dictEntry **table是什么：他是一个数组，数组中每个元素都是一个指向dictEntry的指针。

我们一直都在说dictEntry，那么他又是什么呢？

dictEntry的字段如下：

  • key: 就是我们往hash中存入的key

  • value：往hash中存入的value

  • next： 这个字段比较重要，他是指向下一个dictentry的指针

所以，我们通过next这个字段可以看见，dictEntry是一个单向链表。

我们结合dictEntry和dictEntry **table 可以看出来，ditch就是一个数组+单向链表的结构

数据是如何存入Dict中的

我们在上面了解了Dict的基础信息，知道了Dict是Hash数据结构的底层实现之一，那么一个键值对是如何存入Dict中的呢？

他的步骤是：

  1. 对键值对中的key进行哈希函数运算，计算出哈希值

  2. 将哈希值与dict大小取模计算，计算出来的位置，就是这个键值对在table中的位置

  3. 将键值对放入对应的哈希桶中

我们举例子再说明一下：dictEntry **table的大小为8，有key1-value1的键值对要存入其中。 hash(key1)%8 = 1 ，那么这个键值对就会被放在第一个位置。hash(key10)%8 = 2,那么就会被放入第二个位置。那么如果是hash(key9)%8=1，他是应该要存入第一个位置的对不对，那么他是怎么存放的呢？

我们说过每一个dictEntry中有next节点，key9和key1要存入一个哈希桶中，这叫做哈希冲突，那么原来桶1已经存放了key1， 现在来了key9，就新建一个节点，让桶1指向key9，然后key9的next指向key1。

这种用链表的方式解决哈希冲突，也叫做链式哈希。

现在有一个问题，如果哈希冲突严重，那么会造成单向链表过长，造成检索效率下降，那么Redis是如何解决这个问题的呢？

渐进式Rehash是什么

为了解决哈希冲突严重的问题，redis中使用渐进式Rehash的方法，我们先来了解什么是Rehash。

还记得我们说过Dict结构体中 是使用了两个dictht，只在其中一个dictht中存入数据吗？存数据的我们给他起名ht[0]，那么ht[1]就是在Rehash中使用的，也就是扩容，整个过程分三步：

  • 给ht[1]分配空间，是ht[0]的两倍大小

  • 将ht[0]中的数据转移给ht[1]中

  • 迁移完成，ht[0]的空间被释放，把ht[1]设置为ht[0]，然后创建一个新的ht，为下一次rehash做准备

整个过程看起来很简单，但是这里面有问题，问题就在第二步中，在迁移数据的时候，会涉及大量的数据拷贝，redis又是单线程的，如果数据多，可能会对redis造成阻塞，无法服务别的请求。

为了解决这个问题，redis提出了渐进式Rehash，其实简单来说，就是不一次性迁移完所有的数据，在对数据每一次更新，新增等操作的时候，除了再执行操作之外，还会执行迁移操作。 巧妙的把数据迁移拆分成多次处理请求过程中。

同时，在数据的迁移的过程中，因为会使用到两个ht，所以更新，删除都会在这两个ht中进行操作。 总的来说，现在ht[0]中找对应的key，如果没找到就去ht[1]中找。需要特别说明的是，新增操作直接在ht[1]中操作。

负载因子

我们说了渐进式Rehash是什么，那么什么时候他会被触发呢？

在redis中提出了负载因子这个概念。还记得我们dichht中有size和used这两个字段吗？

负载因子就是used/size 。

  • 当负载因子大于等于1，并且Redis没有在执行RDB快照或者没有进行AOF重写的时候就会进行rehash操作

  • 当负载因此大于等于5的时候，不论redis在进行什么操作，都会强制执行rehash操作

常用命令

  • HSET key field value: 在存储一个哈希表（key）的键值对

  • HGET key field： 获取哈希表（key）中对应的field的值

  • HMSET key [field value...] 在一个哈希表（key）存储多个键值对

  • HMGET key [field...] 批量获取哈希表中的多个field对应的值

  • HDEL key field [field....] 删除哈希表(key)中的field键值对

  • HLEN key 获取哈希表中field的数量

  • HGETALL key 获取哈希表中所有的键值对

  • HINCRBY key field n 给哈希表key中的field对应的值+n

使用场景

  • 缓存对象：与string不同的是，用hash缓存结构型的数据。而string只能缓存字符串，因此可以说明string+json 才能达成hash数据类型的操作。但是hash的优势在于，可以直接操作哈希表中的键值对