redis_字典_哈希hash-白红宇

redis_字典_哈希hash

阅读量：6388 次

发布时间：2019-06-23

本文共 1773 字，大约阅读时间需要 5 分钟。

字典、哈希表基本数据结构

redis字典使用哈希表作为底层实现，基本结构就是数组+散列

typedef struct dictht {    // 哈希表数组    dictEntry **table;    // 哈希表数组的大小    unsigned long size;    // 掩码，用于计算新加入的元素的index（sizemask值等于size-1）    unsigned ling sizemask;    // 哈希表中已有节点的数量    unsigned long used;} dictht;

其中，哈希表数组中的每一个节点，与1.8之前的jdk中map很相似，也是链表结构

typedef struct dictEntry {    // 键    void *key    // 值    union {        void *val;        uint64_t u64;        int64_t s64;    } v;    // 指向下个哈希表节点，形成链表    struct dictEntry *next;} dictEntry;

最终的redis字典内部，由2个哈希表构成。平时只使用其中的一个，当需要扩展或收缩哈希表时，启用第二个，后续详细介绍

redis字典结构如下：

typedef struct dict {    dictType *type    void *privdata;    // 哈希表（实际存储数据），平时使用ht[0]，当需要扩展或收缩哈希表时，将ht[0]的数据rehash到ht[1]，然后释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，done    dictht ht[2];    // 是否正在执行rehash的标识，不在进行时为-1    int trehashidx;} dictEntry;

下面介绍一些hash操作常遇到的问题：index选择、index冲突、rehash触发条件、rehash流程

index选择

index选择和jdk类似

首先计算出哈希值 hash = dict -> type -> hashFunction(key);

再位运算 index = hash & dict -> ht[0].sizemask;
- 注意，这要求ht[0]的大小为2的n次幂，方便hash值被按位与到哈希表的大小里

index冲突

采用链地址方法，冲突的节点被添加在冲突链的头部。不会变成树，就是链

rehash触发条件

哈希表的扩展、收缩会触发rehash，这里和jdk不类似了

扩展条件（满足任意一个即可）：

负载因子（已保存节点数量ht[0].used / 哈希表大小ht[0].size） >=1、且服务器目前没有在执行 BGSAVE 或 BGREWRITEAOF

负载因子 >=5、且服务器目前在执行 BGSAVE 或 BGREWRITEAOF

收缩条件：

负载因子 < 0.1

rehash流程

在rehash发生之前，数据都保存在两个哈希表中的第一个ht[0]中，从这里开始rehash流程：

为ht[1]分配空间。
- 如果是扩展，则ht[1]大小为大于等于ht[0].used * 2 的第一个2的n次幂。比如ht[0]大小为16，used为17，则扩展后大小为64
- 如果是收缩，则ht[1]大小为大于等于ht[0].used 的第一个2的n次幂。比如ht[0]大小为128，used为10，则收缩后大小为16