深入了解Redis【五】内部编码数据结构之字典dict

引言

字典dict相当于java中的HashMap，用来实现redis数据库和redis的hash类型value。

1、数据结构

字典数据结构分为三部分，字典dict、哈希表dictht、节点dictEntry。一个dict包含两个dictht，一个dictht有多个dictEntry,每个dictEntry代表key-val。

1.1、节点dictEntry

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

和java中的java.util.HashMap.Node差不多：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
		//略......
}

1.2、哈希表dictht

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;  
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

和java的HashMap差不多

1.3、字典dict

/*
 * 字典
 */
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

其中ht[2]是两个dictht哈希表，一般只使用ht[0],ht[1]只有rehash的时候使用。

2、hash算法

作用就是通过计算key的hash值，再通过计算得出索引值，确定此键值对将要放在哈希表数组的哪个位置。

// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

// 计算索引值
idx = h & d->ht[table].sizemask;

当字典被用作数据库的底层实现或者哈希键的底层实现是使用MurmurHash算法。
这种算法即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，计算速度非常快，使用简单。
反正我是不懂。具体在hyperloglog.c源码中的MurmurHash64A函数。

3、解决键冲突

从哈希节点的数据结构上就能看出其解决键冲突的原理:

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

即链地址法，当有键冲突时，将新的节点放到链表的头节点，这样速度快。
但是如果冲突的过多，还是会有长链表，java中的解决思路是增加红黑树，redis中没有。

4、rehash

当哈希表中的键值对数量太多或者太少时，会通过rehash来操作，为了让hash表的负载因子维持在一个合理范围。
步骤：

为ht[1]分配空间
如果是扩张，大小为：目前已使用节点数的两倍：d->ht[0].used*2
如果是收缩，大小为：目前已使用节点数：ht[0].used
最后通过 _dictNextPower(size)计算出真正的大小：

/*
 * 哈希表的初始大小
 */
#define DICT_HT_INITIAL_SIZE     4

/* Our hash table capability is a power of two */
/*
 * 计算第一个大于等于 size 的 2 的 N 次方，用作哈希表的值
 *
 * T = O(1)
 */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}