Redis字典

03 June 2018 »Redis

Redis没有使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型，并将SDS作为Redis的默认字符串表示。字典是一种用于保存键值对的抽象数据结构。字典中的每个键都是独一无二的，程序根据键查找与之关联的值，或者通过键来进行值的更新，又或者通过键来删除整个键值对。 Redis中的数据库就是通过字典实现的，还有哈希键的底层也是通过字典实现。

字典的结构
解决键的冲突
rehash

字典的结构

(1) 哈希表节点

哈希表节点使用dictEntry结构表示

typedef struct dictEntry{

    // 键
    void *key;

    // 值    
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下一个哈希表节点
    struct dictEntry *next;
}

key 属性保存键值对中的键，v属性保存键值对中的值，值可以是指针，next属性是一个指向下一个哈希表节点的指针，通过这个指针属性可以将多个哈希表节点构成链表，用这种方法来解决冲突。即当对key使用某种hash算法得到的哈希值上有节点了，那么就会将当前的节点使用头插法加到该链表中。

(2) 哈希表

typedef struct dictht{

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表掩码，用于计算索引值
    // 总等于size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数目
    unsigned long used;
} dictht;

table 是一个数组，数组中每一个元素都是指向一个dictEntry结构的指针

(3) 字典

typedef struct dict{

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash索引
    // 当没有进行rehash时，索引为1
    int trehashidx;
} dict;