Hash基础简介

哈希表是根据键直接访问内存储存位置的数据结构。它通过一个哈希函数，计算键对应的哈希值，然后，将数据存储在对应的区域。加快数据查找。

使用哈希函数计算哈希表地址时，可能会遇到地址冲突。有两种解决方式：开发寻址法，链地址法。开放寻址法就是，取当前冲突的地址的下一个空闲地址作为当前的哈希地址；链地址法是将哈希表每个位置的所有值保存在一个链表中。当遇到冲突时，追加在链表中。

Redis中的Hash

简介

Redis中大量应用哈希结构来存储数据。常见的k-v，hash等，底层存储都是hash字典。暂时抛开Redis而言，如果自己要实现一个hash存储，需要考虑哪些方面呢？

首先，我们需要选择一个hash函数来处理key。此外，需要考虑地址冲突，这个冲突处理决定了我们这个hash的存储结构。这几个方面定好了，大致就可以实现一个基础的hash了。但是不仅仅如此，如果考虑到数据增长的问题，我们不可能一开始就申请一个G的内存来存储数据，最好是根据需要来申请。这就需要考虑一个扩容的处理。此外，当hash表扩容以后，原先拥挤的hash是不是需要重新考虑一下优化呢。就像，原先住在10平米的房子，桌子，柜子上堆满了杂物。现在搬到了一个20平米的房子，有足够的空间了，这时候就需要重新整理房间了。这个过程叫做rehash。

通过上面一个设想，也就大致说出了Redis中hash的相关知识。Redis使用链地址法来处理地址冲突，它的hash表有n个bucket。每个bucket对应一组数据。在Redis 3.0的版本中，使用的是MurmurHash 2.0哈希函数来计算索引。Redis的扩容思路是，当，hash表中总的元素数/hash表总的bucket数 > 负载因子，进行扩容操作。扩容大小是找到一个2^n值，刚好大于等于原始bucket的两倍。每次扩容后，会触发rehash操作。Redis采用渐进式rehash来优化结构。所谓渐进式就是，每次只调整几个bucket，慢慢的全部调整完。

具体实现

首先是hash相关的结构体定义

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    ...
} dictType;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

这些结构体，用一张图来表示如下

图片

大致过程是，当Redis初始化hash时，先初始化一个dict结构体。(这里是有误的，初始的Redis hash结构底层并不是字典，而是一个压缩表。只有当大小达到一个范围时，才会采用字典存储hash。但是这里主要学习hash，所以不在意这个逻辑。)

然后，此时执行hset hello world，Redis会执行dictAddRaw方法，目的是，往这个哈希表中插入一个元素。插入元素的过程中，会首先计算这个key的hash，找到对应的bucket。如果当前bucket已经有元素了，Redis是将最新的数据插入到链表的开头。简简单单的一个插入，里面还隐藏了一些其他的额外操作，包括扩容等。可以看下面的代码。

插入函数如下

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    // 如果当前哈希表在rehash状态，则忙里偷闲的rehash一次
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 计算hash，找到对应的bucket。这里面也有其他文章。
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    // 如果在rehash状态，则把个元素插入到ht[1]表中，否则插入到ht[0]表中。
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    dictSetKey(d, entry, key);
    return entry;
}

计算key的hash值，找到bucket

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /**
     * 在这里进行hash表的扩容操作！
     * 扩容思路就是，如果当前hash表为空，则初始化4个bucket。
     * 如果当前bucket不为空，则，根据bucket数和已经存在的元素数来找到一个合适的2^n大小。
     */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    // 根据murmurhash2算法，计算一个32位的hash值
    h = dictHashKey(d, key);
    // 这里遍历ht[0]和ht[1]。是因为，rehash操作，会让两个哈希表均有数据存在。所以需要全部查一遍。
    for (table = 0; table <= 1; table++) {
        /**
         * 重要。这里解释了为什么扩容的大小必须是2^n。
         * 因为sizemask = size - 1。所以转为二进制，即是全1。这里进行&操作，能保证均匀分布在bucket中。
         */ 
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

rehash操作

rehash一般发生在hash扩容后。可以看到前面的Redis字典结构，每个字典都有两个哈希表。即是通过这两个表来进行rehash操作的。

大致思路是，当发生扩容以后，会标记字典rehashidx状态值。表明，进入rehash状态。Redis在一些操作里面打了锚点，如果当前处于rehash状态，则顺手执行一次rehash。挺好的，均摊一下执行成本。

rehash执行过程。扩容后，两个hash表的大小是一样的。rehash就是将ht[0]里面的bucket，重新计算hash，存入到ht[1]中。每次搬完一个bucket，ht[0].used就减一。这样，当归0后，即表示全部迁移完了。然后就是释放ht[0]的内存，将ht[0]和ht[1]互换。

一个感觉，就是有条不紊。hash表大的话，可能几百万个元素，如果阻塞执行，还是挺费时的。

其他

Redis中hash字典还有一个比较重要的应用。我们知道Redis中有数据库的概念。即RedisDb。Redis支持多个数据库，只不过通常都是使用的默认的0数据库。RedisDb底层就是一个dict结构。也就是说，Redis的所有k-v数据都存在一个hash表中。

接着，思考一个小问题，一个RedisDb一共可以存储多少个k-v数据？

答案是2^32个。为什么呢？因为redis中的hash算法只能生成一个32位hash值。另外，也因为字典中的size和sizemask使用的是unsighed long类型，这个类型使用4个字节32位，也就是说，sizemask最大是2^32-1。即使一个128位的hash，进行与操作后，最终也只能得到一个2^32范围内的bucket索引，此时hash失效了。不过，实际情况，内存容量也不会支持这么多key。

最后

Redis作为Web开发中的一个基础组件，应用相当广泛。本身使用c语言编写，可读性还是很强的。可以扩宽自己的一些思路。