【Redis学习笔记（二）】之字典结构详解

朴灿烈づ我的快乐病毒、 2023-10-07 15:40 56阅读 0赞

#### 文章目录 ####

*   *  本文章由公号【开发小鸽】发布！欢迎关注！！！
     *  一． 字典
     *   *  （一） 概述
         *  （二） 字典的实现
         *   *  1. 哈希表
             *  2. 哈希表节点
             *  3. 字典
         *  （三） 哈希算法
         *  （四） 键冲突问题
         *  （五） rehash

### 本文章由公号【开发小鸽】发布！欢迎关注！！！ ###

**老规矩–妹妹镇楼：**

![20200721223424816.JPG][]

### 一． 字典 ###

#### （一） 概述 ####

一种用于保存键值对的抽象数据结构，一个键可以和一个值进行关联，每个键都是唯一的。由于C语言中没有内置字典，所以Redis构建了自己的字典实现，在Redis中的用途也很广泛，如Redis的数据库就是使用字典作为底层实现的，还有哈希键的底层实现之一等等。

#### （二） 字典的实现 ####

Redis的字典使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，每个哈希表节点保存了字典中的一个键值对。

##### 1. 哈希表 #####

Redis字典所使用的哈希表使用dictht结构定义：

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

table属性是一个数组，每个元素都是一个指向dictEntry结构的指针，该结构为哈希表节点，保存着一个键值对；

size属性记录了哈希表的大小，即table数组的大小；

used记录了哈希表目前已有节点的数量；

sizemask属性的值等于size-1，用于和哈希值一起决定一个键应该被放到table数组中的哪个索引之上，后面有解释

##### 2. 哈希表节点 #####

哈希表节点使用dictEntry结构表示，该结构保存着一个键值对。

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

key属性为键值对中的键；

v属性为键值对中的值，可以是指针或是整数，即union中的任一个；

next属性是指向另一个哈希表节点的指针，可以将多个哈希值相同的键值对链接在一起，姐姐键冲突问题。

##### 3. 字典 #####

字典由dict结构实现

typedef struct dict{
        
    	dictType *type;
    	void *privdata;
    	dictht ht[2];
    	int trehashidx;
    }dic;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的；

ht属性是一个包含两个项的数组，每个项都是一个dictht哈希表，一般情况下字典使用ht\[0\]哈希表，ht\[1\]只有在对ht\[0\]进行rehash时使用；

trehashidx记录了rehash目前的进度，如果没有进行rehash，则为-1

#### （三） 哈希算法 ####

当要将一个新的键值对添加到字典中时，首先根据键来计算出哈希值和索引值，再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Redis计算哈希值的方法是dict->type->hashFunction(key)，计算出哈希值后，根据哈希表的sizemask属性和哈希值，计算出索引值：