Redis[六]Hash数据类型

1.存储类型
2.存储原理
- 2.1 压缩列表
- 2.2 hashTable(dict)
3.hash函数
4.哈希冲突
5.rehash
- 5.1为什么要定义两个hash表？
- 5.2什么时候触发扩容？
6.Hash的应用场景

接着上一章最后抛出的疑问，我们来分析redis的hash数据结构。

1.存储类型

hash是一种包含键值对的无序散列表数据结构，value只能是字符串，不能嵌套其他类型。

同样是存储字符串，hash与string的主要区别在于：

把所有相关的值聚焦到一个key中，节省内存空间
只使用一个key，减少key冲突
当需要批量获取值的时候，只需要使用一个命令，减少内存 IO CPU的消耗

hash不适合的场景包括：

field不能单独设置过期时间
没有bit操作
需要考虑数据量分布的问题（value值特别大的时候，无法分不到多个节点）

2.存储原理

Redis 的 Hash 本身也是一个 KV 的结构，类似于 Java 中的 HashMap。外层的哈希（Redis KV 的实现）只用到了 hashtable。当存储 hash 数据类型时，我们把它叫做内层的哈希。内层的哈希底层可以使用两种数据结构实现。

ziplist：OBJ_ENCODING_ZIPLIST（压缩列表）
hashtable：OBJ_ENCODING_HT（哈希表）

2.1 压缩列表

ziplist 是一个经过特殊编码的双向链表，它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。

The general layout of the ziplist is as follows:
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

typedef struct zlentry {
    unsigned int prevrawlensize; /* 上一个链表节点占用的长度 */
    unsigned int prevrawlen; /* 存储上一个链表节点的长度数值所需要的字节数 */
    unsigned int lensize; /* 存储当前链表节点长度数值所需要的字节数 */
    unsigned int len; /* 当前链表节点占用的长度 */
    unsigned int headersize; /* 当前链表节点的头部大小（prevrawlensize + lensize），即非数据域的大小 */
    unsigned char encoding; /* 编码方式 */
    unsigned char *p; /* 压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
} zlentry;

zlentry结构其实没啥用，仅仅用来作为接收数据的，实际上的使用要看源码注释。

当 hash 对象同时满足以下两个条件的时候，使用 ziplist 编码：

所有的键值对的健和值的字符串长度都小于等于 64byte（一个英文字母一个字节）；
哈希对象保存的键值对数量小于 512 个。

接下来看一下源码：

首先在redis.conf配置文件中我们可以对哈希底层编码的转换阈值进行配置。

# 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.
# ziplist 中最多能存放的 entry 节点数量
hash-max-ziplist-entries 512
# ziplist 中最大能存放的值长度
hash-max-ziplist-value 64

if (hashTypeLength(o) > server.hash_max_ziplist_entries)
    hashTypeConvert(o, OBJ_ENCODING_HT);

void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
    for (i = start; i <= end; i++) {
        if (sdsEncodedObject(argv[i]) &&sdslen(argv[i]->ptr) > server.hash_max_ziplist_value){
            hashTypeConvert(o, OBJ_ENCODING_HT);
            break;
        }
    }
}

一个哈希对象超过配置的阈值（键和值的长度有>64byte，键值对个数>512 个）时，会转换成哈希表（hashtable）。

2.2 hashTable(dict)

在 Redis 中，hashtable 被称为字典（dictionary），它是一个数组+链表的结构。Redis 的 KV 结构是通过一个 dictEntry 来实现的。Redis 又对 dictEntry 进行了多层的封装。key 是键值对中的键，v 是键值对中的值，它是一个联合类型，方便存储各种结构；next 是链表指针，指向下一个哈希表节点，他将多个哈希值相同的键值对串联在一起，用于解决键冲突，也就是所谓的链地址法。

typedef struct dictEntry {
    void *key; /* key 关键字定义 */
    union {
        void *val; /* value 定义 */
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; /* 指向下一个键值对节点 */
} dictEntry;

dictEntry 放到了 dictht（hashtable 里面）：

typedef struct dictht {
    dictEntry **table;  /* 哈希表数组 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /* 掩码大小，用于计算索引值。总是等于 size-1 */
    unsigned long used; /* 已有节点数 */
} dictht;

dictht放到了 dict 里面:

type 是一个指向 dict.h/dictType 结构的指针，保存了一系列用于操作特定类型键值对的函数
privdata 保存了需要传给上述特定函数的可选参数
ht 是两个哈希表，一般情况下，只使用ht[0]，只有当哈希表的键值对数量超过负载(元素过多)时，才会将键值对迁移到ht[1]，这一步迁移被称为 rehash (重哈希)，rehash 一会儿我会带领大家看源码
rehashidx 由于哈希表键值对有可能很多很多，所以 rehash 不是瞬间完成的，需要按部就班，那么 rehashidx 就记录了当前 rehash 的进度，当 rehash 完毕后，将 rehashidx 置为-1

typedef struct dict {
    dictType *type; /* 字典类型 */
    void *privdata; /* 私有数据 */
    dictht ht[2]; /* 一个字典有两个哈希表 */
    long rehashidx; /* rehash 索引 */
    unsigned long iterators; /* 当前正在使用的迭代器数量 */
} dict;

从最底层到最高层 dictEntry->dictht->dict->OBJ_ENCODING_HT。

关于类型处理函数：有点类似Java中的接口或者抽象类，在dictType中做了一个声明。

typedef struct dictType {
    //计算哈希值
    uint64_t (*hashFunction)(const void *key);
    //copy key
    void *(*keyDup)(void *privdata, const void *key);
    //copy value
    void *(*valDup)(void *privdata, const void *obj);
    // compare key
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键
    void (*keyDestructor)(void *privdata, void *key);
    //销毁值
    void (*valDestructor)(void *privdata, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

总结一下hash表的存储结构：

dicth 后面是 NULL 说明第二个 dicth 还没用到。dictEntry*后面是 NULL 说明没有 hash 到这个地址。dictEntry 后面是NULL 说明没有发生哈希冲突。

3.hash函数

看完了hash的数据结构，我们来看一看Redis中对于hash函数的实现。

再此，我在前面先唠叨下，hash函数的基本概念。hash函数主要就是输入原内容，然后经过一系列运算之后，可以计算出一个值，这个值决定了该元素在hash表中的存放位置。

同一个key不论第几次传入hash函数，输出的结果应该是一样的。如果两次调用hash函数的结果不一致，那这个键就丢了（找不到），那说明hash函数式错误的。
另外，因为实现hash表的空间是有限的，所以我们要尽量让key更加均匀的分布。

接下来我们来看一下Redis中对于hash函数的实现，其实现在siphash.c。

uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {
#ifndef UNALIGNED_LE_CPU
    uint64_t hash;
    uint8_t *out = (uint8_t*) &hash;
#endif
    //1.初始化
    //1.1 初始化4个向量 v0 v1 v2 v3
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    //1.2 将128位的key用little-endian(较小的字节在低位)编码为64位的k0,k1
    uint64_t k0 = U8TO64_LE(k);
    uint64_t k1 = U8TO64_LE(k + 8);
    uint64_t m;
    const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t));
    const int left = inlen & 7;
    uint64_t b = ((uint64_t)inlen) << 56;
    //1.3 用k0,k1初始化v0,v1,v2,v3
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
    // 2. 压缩
    for (; in != end; in += 8) {
        //2.1 split message
        //#define U8TO64_LE(p) (*((uint64_t*)(p)))
        m = U8TO64_LE(in);
        v3 ^= m;
        SIPROUND;
        v0 ^= m;
    }
    switch (left) {
    case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */
    case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */
    case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */
    case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */
    case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */
    case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */
    case 1: b |= ((uint64_t)in[0]); break;
    case 0: break;
    }
    v3 ^= b;
    SIPROUND;
    v0 ^= b;
    //结束
    v2 ^= 0xff;
    SIPROUND;
    SIPROUND;
    //得到最终结果
    b = v0 ^ v1 ^ v2 ^ v3;
#ifndef UNALIGNED_LE_CPU
    U64TO8_LE(out, b);
    return hash;
#else
    return b;
#endif
}

由此可见Redis底层使用的hash算法是SipHash 算法，在本文中不作为重点内容介绍，如果有兴趣的同学可以自行了解。当然了我们也可以在回顾下，Java中的HashMap的hash算法。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

如果key==null，hash值就是0，hash值就等于key的hash值^h无符号右移16位。异或：相同则返回0，不同返回1。这就是哈希map底层使用的扰动，为了让高16位也参与运算。防止哈希冲突。

4.哈希冲突

hash冲突一定是发生在添加元素的时候，所以我们直接去看添加元素的过程。

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key, NULL);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

我们接着往下看

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {
    ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if ((index = _dictKeyIndex(d, key, dictHashKey(d, key), existing)) == -1)
        return NULL;
    /* 根据是否rehash，选择hash表，如果在 rehash 过程中，则将元素添加到 rehash 新建的哈希表中 */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    //分配内存，执行插入
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    /* 设置key */
    dictSetKey(d, entry, key);
    return entry;
}

我们来总结下这个插入的流程：

判断当前的字典是否在进行 rehash，如果是，则执行一步 rehash，否则忽略。判断 rehash 的依据就是 rehashidx 是否为 -1
通过 _dictKeyIndex 找到一个索引，如果返回-1表明字典中已经存在相同的 key，调用**_dictKeyIndex**
根据是否在 rehash 选择对应的哈希表
分配哈希表节点 dictEntry 的内存空间，执行插入，插入操作始终在链表头插入，这样可以保证每次的插入操作的时间复杂度一定是 O(1) 的，插入完毕，used属性自增
dictSetKey 是个宏，调用字典处理函数中的 keyDup 函数进行键的复制

宏：编译前定义的，静态代码替换。

接下来我们再看来看一下索引定位的逻辑：

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing) {
    ...
    /* 判断是否需要进行rehash操作 */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    //因为可能存在 rehash 的情况，所以查找的时候是遍历 dict 的 ht 数组，从两个 hash 表中查找
    for (table = 0; table <= 1; table++) {
        /* 计算索引值 */
        idx = hash & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while (he) {
            //判断key是不是已经存在了
            if (key == he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        //判断当前是不是正在进行rehash操作
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

判断当前哈希表是否需要进行扩展
通过位与计算索引，即插入到哈希表的哪个槽位中
查找当前槽位中的链表里是否已经存在该键，如果存在直接返回 -1；这里的 dictCompareKeys 也是一个宏，用到了keyCompare 这个比较键的函数
如果当前没有在做 rehash，那么 ht[1] 必然是一个空表，所以不能遍历 ht[1]，需要及时跳出循环
5.rehash

上面的添加过程，我们还有一个rehash没有讲，接下来我们来看一下。rehash其实就是随着数据的不断添加，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。其实这里和java的hashMap有点类似，也有负载因子和扩容的概念。

负载因子：当前已使用结点数量除上哈希表的大小，即：load_factor = ht[0].used / ht[0].size
哈希表的扩容
- 当哈希表的负载因子大于5时，为 ht[1] 分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂
- 将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个
- 当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件，将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备

Redis 中实现哈希表扩展调用的是 dict.c/_dictExpandIfNeeded 函数

static int _dictExpandIfNeeded(dict *d) {
  /* 如果当前增在进行rehash操作，直接返回。 */
  if (dictIsRehashing(d)) return DICT_OK;
  /* 如果哈希表是空的，对哈希表进行初始化操作，初始化长度为4。 */
  if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
  /*
   * 如果已使用节点与字典大小的比例达到1：1 ，
   * 并且我们在全局设置里面允许哈希表的扩容
   * 或者在安全的扩容区间内
   * 或者或负载因子达到5。
   * 我们将哈希表的桶位扩容为原来的2倍
   */
  if (d->ht[0].used >= d->ht[0].size &&
      (dict_can_resize ||
       d->ht[0].used / d->ht[0].size > dict_force_resize_ratio) &&
      dictTypeExpandAllowed(d)) {
      return dictExpand(d, d->ht[0].used + 1);
  }
  return DICT_OK;
}

扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。

为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表

将 rehashidx 设置为0，表示正式开始 rehash，前两步是在 dict.c/_dictExpand 中实现的

int _dictExpand(dict *d, unsigned long size, int *malloc_failed) {
 if (malloc_failed) *malloc_failed = 0; //分配内存失败
 if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; //如果size小于哈希表中实际存储的元素个数，返回false。
 dictht n; //n代表的是新的hash表
 unsigned long realsize = _dictNextPower(size); //hash表真实的使用量
 if (realsize == d->ht[0].size) return DICT_ERR;//如果 realsize 小于哈希表中实际存储的元素个数，返回false。
 n.size = realsize; //设置新表的长度
 n.sizemask = realsize - 1; //设置容量掩码
 if (malloc_failed) { //如果内存分配失败
     //尝试吧新表的长度设置为实际存在的元素个数的长度
     n.table = ztrycalloc(realsize * sizeof(dictEntry *));
     *malloc_failed = n.table == NULL;
     if (*malloc_failed) //如果分配失败，返回错误
         return DICT_ERR;
 } else //内存分配成功的逻辑
     n.table = zcalloc(realsize * sizeof(dictEntry *));
 n.used = 0;
 if (d->ht[0].table == NULL) { //如果 ht[0]为空
     d->ht[0] = n; //将新创建的hash表指针指向ht[0]
     return DICT_OK;
 } //接下来就是ht[0]不为空的情况
 d->ht[1] = n;
 d->rehashidx = 0;
 return DICT_OK;
}

在进行 rehash 期间，每次对字典执行增、删、改、查操作时，程序除了执行指定的操作外，还会将哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表（遍历很久遇到的都是NULL），从而导致函数阻塞时间太长，这里引入了一个 “最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。这一步实现在 dict.c/dictRehash 中：

最后，当 ht[0].used 变为0时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table，并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。

int dictRehash(dict *d, int n) {
 int empty_visits = n * 10; /* Max number of empty buckets to visit. */
 if (!dictIsRehashing(d)) return 0;
 while (n-- && d->ht[0].used != 0) {
     dictEntry *de, *nextde;
     /* rehashidx不能溢出，之所以我们确定有更多的元素，是因为ht[0]用过！= 0 */
     assert(d->ht[0].size > (unsigned long) d->rehashidx);
     while (d->ht[0].table[d->rehashidx] == NULL) {
         d->rehashidx++;
         if (--empty_visits == 0) return 1;
     }
     de = d->ht[0].table[d->rehashidx];
     /* 节点迁移 */
     while (de) {
         uint64_t h;
         nextde = de->next;
         /* 获取在新表中的索引 */
         h = dictHashKey(d, de->key) & d->ht[1].sizemask;
         de->next = d->ht[1].table[h];
         d->ht[1].table[h] = de;
         d->ht[0].used--;
         d->ht[1].used++;
         de = nextde;
     }
     d->ht[0].table[d->rehashidx] = NULL;
     d->rehashidx++;
 }
 /* 判断我们是不是已经rehash完了整个表 */
 if (d->ht[0].used == 0) {
     ...
     // 迁移完毕，rehashdix 置为 -1
     d->rehashidx = -1;
     return 0;
 }  
 return 1;/* 返回1表示还有节点需要迁移 */
}

哈希表的收缩，同样是为 ht[1] 分配空间，大小等于max( ht[0].used, DICT_HT_INITIAL_SIZE )，然后和扩展做同样的处理即可。

int htNeedsResize(dict *dict) {
 long long size, used;
 size = dictSlots(dict);
 used = dictSize(dict);
 return (size > DICT_HT_INITIAL_SIZE && (used * 100 / size < HASHTABLE_MIN_FILL));
}

在此，我们对rehash进行一个总结。

5.1为什么要定义两个hash表？

redis 的 hash 默认使用的是 ht[0]，ht[1]不会初始化和分配空间。哈希表 dictht 是用链地址法来解决碰撞问题的。在这种情况下，哈希表的性能取决于它的大小（size 属性）和它所保存的节点的数量（used 属性）之间的比率：比率在 1:1 时（一个哈希表 ht 只存储一个节点 entry），哈希表的性能最好；如果节点数量比哈希表的大小要大很多的话（这个比例用 ratio 表示，5 表示平均一个 ht 存储 5 个 entry），那么哈希表就会退化成多个链表，哈希表本身的性能优势就不再存在。在这种情况下需要扩容。Redis 里面的这种操作叫做 rehash。

为字符 ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0]当前包含的键值对的数量。

ht[1]的大小为第一个大于等于 ht[0].used*2。

将所有的 ht[0]上的节点 rehash 到 ht[1]上，重新计算 hash 值和索引，然后放入指定的位置。
当 ht[0]全部迁移到了 ht[1]之后，释放 ht[0]的空间，将 ht[1]设置为 ht[0]表，并创建新的 ht[1]，为下次 rehash 做准备。

5.2什么时候触发扩容？

static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

ratio = used / size，已使用节点与字典大小的比例。

dict_can_resize 为 1 并且 dict_force_resize_ratio 已使用节点数和字典大小之间的比率超过 1：5，触发扩容。

6.Hash的应用场景

①String

String能做的，hash也都可以做。

②存储对象类型的数据

比如对象或者一张表的数据，比 String 节省了更多 key 的空间，也更加便于集中管理。

③购物车

key：用户 id；field：商品 id；value：商品数量。

+1：hincr。-1：hdecr。删除：hdel。全选：hgetall。商品数：hlen。