nber1994



redis数据结构-字典

January 8, 2019

redis数据结构-字典(dict)

hash表结构

哈希表结构
typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size
    //哈希表大小掩码,用于计算索引值,总之等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}

table是一个数组,数组中的每个元素都是指向dictEntry结构的指针,每个dictEntry保存这一个键值对

hash节点

typedef struct dictEntry {
        //键
        void *key;
        //值
        union {
            void *val;
            uint64_tu64;
            int64_ts64;
        }v;
        //指向下一个hash节点,形成链表
        struct dictEntry *next;
} dictEntry;

其中next可以连接相同的节点,可以通过这个指针将相同哈希值的多个键值对节点连接起来,来解决哈希冲突的问题

字典结构

字典由如下结构表示:

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privData;
    //哈希表
    dictht ht[2];
    //rehash索引
    //当rehash不进行时,值为-1
    int trehashidx;
}

hash算法

hash算法根据键值,计算出哈希值,在结合sizemask的值,计算出索引值
向hash表添加一个键值对时,先根据hash算法计算出键值对的哈希值和索引值
再根据索引值确定新的哈希表节点放到指定索引上

解决键冲突

rehash

当hash表的装载因子大于1时,redis会将hash表进行rehash操作

步骤:

rehash的条件

渐进式的rehash

当存在大量的键值对时,rehash会带来大量的运算,并且在此期间不能响应请求,所以采用渐进式的rehash方法

重点回顾