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语言编写,可读性还是很强的。可以扩宽自己的一些思路。