Redis数据类型之字典

标签（空格分隔）： redis

redis的字典

字典又称符号表(symbol table)，关联数组(associative array)，或者映射(map)。是用于保存键值对的一种抽象数据结构。
字典的key是唯一的，对键值对的操作基本都是基于key来操作的。redis中的数据库底层是使用字典来实现的，对于数据库的增删改查都是基于字典来实现的。redis的哈希键也是基于字典来实现的。

具体的实现是在src下的dict.h和dict.c文件

字典的数据结构

哈希表结点

            
                /*
 * 哈希表节点
 */
                typedef
                struct dictEntry {

    // 键void *key;

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

    // 指向下个哈希表节点，形成链表struct dictEntry *next;

} dictEntry;
        

哈希表的数据结构

            
                /*
 * 哈希表
 */
                typedef
                struct dictht {

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

    // 哈希表大小unsignedlong size;

    // 哈希表大小掩码，用于计算索引值// 总是等于 size - 1unsignedlong sizemask;

    // 该哈希表已有节点的数量unsignedlong used;

} dictht;
        

字典的数据结构

            
                /*
 * 字典
 */
                typedef
                struct dict {

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

    // 私有数据void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引// 当 rehash 不在进行时，值为 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在运行的安全迭代器的数量int iterators; /* number of iterators currently running */

} dict;
        

其中的dictType是一个struct

            
                /*
 * 字典类型特定函数
 */
                typedef
                struct dictType {

    // 计算哈希值的函数unsignedint (*hashFunction)(constvoid *key);

    // 复制键的函数void *(*keyDup)(void *privdata, constvoid *key);

    // 复制值的函数void *(*valDup)(void *privdata, constvoid *obj);

    // 对比键的函数int (*keyCompare)(void *privdata, constvoid *key1, constvoid *key2);

    // 销毁键的函数void (*keyDestructor)(void *privdata, void *key);

    // 销毁值的函数void (*valDestructor)(void *privdata, void *obj);

} dictType;
        

            
                // 哈希表
    dictht ht[2];
        

这里的ht是一个包含两项数据的数组，数组的每一项都是一个dictht哈希表，一般情况下，只使用ht[0]，ht[1]是在rehash的情况下使用。

哈希算法

当需要向字典添加一对键值对时，程序首先根据字典的key计算出hash值和索引值，然后根据索引值，将包含新键值对的哈希表结点放到哈希数组指定的索引位置上。

redis计算hash值和索引的方法如下

            
                // 计算给定键的哈希值
                #define dictHashKey(d, key) (d)->type->hashFunction(key)
                // 计算索引值
idx = h & d->ht[table].sizemask;
        

哈希冲突

当两个或者两个以上的键被分配到哈希数组的同一个索引上，被称为哈希冲突。

哈希冲突的解决方法：

1. 开放定址法(包括线性探查法、线性补偿探测法、随机探测)
2. 拉链法，又称链地址法

redis如何解决哈希冲突？
链地址法，每个哈希表结点都有一个next指针域，多个哈希表结点可以构成一个单链表，被分配到同一个索引的键可以使用这个next指针连起来，从而解决哈希冲突。

版权声明：本文为博主原创文章，未经博主允许不得转载。