【LSP】教学基础篇——REDIS基础数据结构

无名

3.字典（dictht）

字典又称之为hash，或者映射（map），也可以理解为redis自己实现的JDK1.7版本的HashMap。是一种用于保存键值对的抽象数据结构。在字典中，一个键（Key）可以和一个值（value）进行关联，成为一个键值对。

字典中每个键都是唯一的。程序可以在字典中根据键查找与之关联的值，或者通过键来跟新或者删除值。接下来的内容将详细介绍Redis中字典的两种底层实现。

第一种：ziplist

当字典中的元素满足以下两个条件时，字典的底层将会使用ziplist来报错键值对。

1.字典对象保存的所有键值对的键和值的字符串长度都小于64个字节。

2.字段对象保存的键值对数量小于512个。

看到这里也许有的看官会不明白了。在上面我们刚刚学过ziplist压缩列表，大家都知道这其实就是一个数组。前面的列表可以用数组来保存，但是这里是键值对啊，一个map，怎么用数组来保存？

各位看官先莫慌，按照惯例先上图（毕竟无图无真相啊）：




第二种：hash表

hash表顾名思义，其本质就是一个HashMap。下面我带各位看官们看看他的结构

复制代码
typedef struct dict{
    dictType *type;//类型特定函数
    void *privdata;//私有函数
    dictht ht[2];//hash表
    int trehashidx;//扩容索引 当不在扩容的时候 为-1
};

typedef struct dictht{
    dictEntry **table;//哈希表数组
    unsigned long size;//哈希表大小
    unsigned long sizemask;//哈希表槽位取模基准参数 总是等于size - 1
    unsigned long used;//已有节点数量
}

typedef struct dictEntry{
    void *key;//键
    //值 这里三个属性是因为 值可能是一个对象引用也可能是 一个uint64_t或者int64_t整数值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //下一个节点 多个槽位相同的值 串联成一个链表
    struct dictEntry *next;
}
复制代码
结构示意图：




渐进式rehash ：

字典在扩容的过程中会在 ht[1] 创建一个新的哈希表，而且它并不会一次性将所有的数据都转移到新的哈希表之中。而是分而治之，像蚂蚁搬家一样，一部分一部分的迁移，我们称之为渐进式rehash。

因为篇幅原因，后面会写一篇专门的文章来详细说明渐进式rehash和在迁移过程中获取元素的方式，这里就简略的介绍一下。

4.集合（sets）

Redis集合中的Set集合，相当与java中的HashSet，它内部的键值对是无序的，唯一的。在Redis中Set集合底层也存在两种实现方式。

第一种，当一个集合只包含整数值元素，并且这个集合的元素数量不超过512时，Redis就会使用整数集合作为集合键的底层实现。

复制代码
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
};
复制代码
contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量，也即是contents数组的长度。虽然intset结构将contents数组声明为int8_t类型的数组。但实际上contents数组的真正类型取决于encoding；

如果encoding类型为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组。

如果encoding类型为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组。

如果encoding类型为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组。