Redis(设计与实现):03---数据结构之字典（hashtable、struct dictht、struct dictEntry、struct dict）

一、字典介绍

• 字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构
• 在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值）， 这些关联的键和值就称为键值对
• 字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等

二、字典在Redis中的应用场景

• ①Redis的数据库就是使用字典来作为底层实现的， 对数据库的增、删、查、改操作也是构建在对字典的操作之上的
  • 举个例子，当我们执行下面命令，在数据库中创建一个键为"msg"，值为"hello world"的键值对时，这个键值对就是保存在 代表数据库的字典里面的：

redis> SET msg "hello world"
OK

• ②字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的 底层实现

例如：

• website是一个包含10086个键值对的哈希键，这个哈希键的键都是一些数据 库的名字，而键的值就是数据库的主页网址：

• website键的底层实现就是一个字典，字典中包含了10086个键值对，例如：
  • 键值对的键为"Redis"，值为"Redis.io"
  • 键值对的键为"MariaDB"，值为"MariaDB.org"
  • 键值对的键为"MongoDB"，值为"MongoDB.org"

• ③除了用来实现数据库和哈希键之外，Redis的不少功能也用到了字典，我们将在后面介绍

三、字典的底层实现

• Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个 哈希表节点就保存了字典中的一个键值对

哈希表（struct dictht）

• Redis字典所使用的哈希表由dict.h/dictht结构定义：

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

• 成员介绍：
  • table属性：是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个 dictEntry结构保存着一个键值对
  • size属性：记录了哈希表的大小，也即是table数组的大小
  • used属性：则记录了哈希表目前已有节点（键值对）的数量
  • sizemask属性：的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面
• 例如：下图展示了一个大小为4的空哈希表（没有包含任何键值对）

哈希表节点（struct dictEntry）

• 哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

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

• 成员如下：
  • key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是 一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数
  • next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连 接在一次，以此来解决键冲突（collision）的问题
• 例如：下图就展示了如何通过next指针，将两个索引值相同的键k1和k0连接在一 起

字典（struct dict）

• Redis中的字典由dict.h/dict结构表示：

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash 索引。当rehash 不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;


typedef struct dictType {
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    //复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    //对比键的函数
    int (*keyCompare)
    (void *privdata, const void *key1, const void *key2);
    //销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    //销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

• 成员如下：
  • type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的
  • type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定 类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数
  • 而privdata属性则保存了需要传给那些类型特定函数的可选参数
  • ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下， 字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
  • 除了ht[1]之外，另一个和rehash有关的属性就是rehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1
• 下图展示了一个普通状态下（没有进行rehash）的字典

四、哈希算法

• 当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上 面
• Redis计算哈希值和索引值的方法如下：

#使用字典设置的哈希函数，计算键key 的哈希值hash = dict->type->hashFunction(key);

#使用哈希表的sizemask 属性和哈希值，计算出索引值
#根据情况不同，ht[x] 可以是ht[0] 或者ht[1]
index = hash & dict->ht[x].sizemask;

• MurmurHash2算 法：
  • 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算 法来计算键的哈希值
  • MurmurHash算法最初由Austin Appleby于2008年发明，这种算法的优点在于，即使输入 的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快
  • MurmurHash算法目前的最新版本为MurmurHash3，而Redis使用的是MurmurHash2，关 于MurmurHash算法的更多信息可以参考该算法的主页：http://code.google.com/p/smhasher/