Redis 数据结构 hashtable

小咪咪 2023-10-04 12:52 35阅读 0赞

## 回顾 ##

在上篇博客 [Redis 数据结构 linkedlist][Redis _ linkedlist] 中我们介绍了 Redis 的 linkedlist（双端链表），这篇博客我们来看看 Redis 的 hashtable（哈希表）。

## version：3.0 ##

> 以版本为 3.0 的 Redis 进行分析

### 结构 ###

源码地址：[3.0/src/dict.h][3.0_src_dict.h]

#### 哈希表 ####

下述代码对应 dict.h 中的 `dictht`

/*
     * 哈希表结构
     * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
     */
    typedef struct dictht {
        
    	// 哈希表数组
        dictEntry **table;
        // 哈希表的大小
        unsigned long size;
        // 哈希表的大小掩码（总是 size-1）
        unsigned long sizemask;
    	// 哈希表当前的已有结点数量
    	unsigned long used;
    } dictht;

#### 哈希表结点 ####

下述代码对应 dict.h 中的 `dictEntry`

typedef struct dictEntry {
        
    	// 键
        void *key;
        // 值
        union {
        
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        // 指向下一个哈希表结点的指针
        struct dictEntry *next;
    } dictEntry;

> key 是键，v 是值，next 是指向下一个哈希表结点的指针，此指针可以将多个哈希值相同的键值对连在一起，形成 [单链表][Link 1] ，解决键冲突的问题。

**例图**

当前未存在 hash 冲突，包含了两个键值对的哈希表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]

当前存在 hash 冲突，包含了三个键值对的哈希表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 1]

#### 字典 ####

下述代码对应 dict.h 中的 `dict`

typedef struct dict {
        
    	// 指向 dictType 结构的指针（dictType 结构保存的是操作特定类型键值对的函数）
        dictType *type;
        // 保存上述所说函数的参数
        void *privdata;
        // 哈希表
        dictht ht[2];
        // rehash 索引，rehash 不进行时值为 -1 
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        // 正在运行的迭代器数量
        int iterators; /* number of iterators currently running */
    } dict;

其中需要注意的是：ht 属性是包含两个项的数组，每一个数组都是一个 dictht 哈希表，一般情况下只使用第一个哈希表（ht\[0\]）,ht\[1\] 会在哈希表进行 rehash 时使用。

**扩展：** Redis 的 rehash 过程是「渐进式」的，即「将很大块迁移数据的开销平摊到多次小的操作中」，目的是降低主线程的性能影响。

**例图**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 2]

## version：3.2+ ##

> 以版本为 3.2 的 Redis 进行分析

3.2 的和 3.0 的一样，就不再赘述了。

## 关联阅读 ##

[Redis 基础][Redis]

[Redis 数据结构 SDS][Redis _ SDS]

[Redis 数据结构 linkedlist][Redis _ linkedlist]

[Redis 数据结构 hashtable][Redis _ hashtable]

[Redis 数据结构 skiplist][Redis _ skiplist]

[Redis 数据结构 ziplist][Redis _ ziplist]

[Redis 数据结构 intset][Redis _ intset]

[Redis 数据结构 quicklist][Redis _ quicklist]

[Redis 对象 RedisObject][Redis _ RedisObject]

[Redis _ linkedlist]: https://mindartisan.blog.csdn.net/article/details/116384345
[3.0_src_dict.h]: https://github.com/redis/redis/blob/3.0/src/dict.h
[Link 1]: https://mindartisan.blog.csdn.net/article/details/113622842
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210509133633102.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210509133531183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210509141742614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[Redis]: https://mindartisan.blog.csdn.net/article/details/110290715
[Redis _ SDS]: https://mindartisan.blog.csdn.net/article/details/115283999
[Redis _ hashtable]: https://mindartisan.blog.csdn.net/article/details/116562596
[Redis _ skiplist]: https://mindartisan.blog.csdn.net/article/details/117194957
[Redis _ ziplist]: https://mindartisan.blog.csdn.net/article/details/117387561
[Redis _ intset]: https://mindartisan.blog.csdn.net/article/details/118196924
[Redis _ quicklist]: https://mindartisan.blog.csdn.net/article/details/118884060
[Redis _ RedisObject]: https://mindartisan.blog.csdn.net/article/details/119521399