网站解除域名绑定/服装网络营销策划书

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

Redis字典所使用的哈希表由dict.h/dicht结构定义（跟SDS一样也是一个结构体）

typedef struct dictht{

//哈希表底层数组

dictEntry **table;

//哈希表大小

unsigned long size;

//哈希表大小掩码，用来计算索引值的

//总是等于size - 1

unsigned long sizemask;

//该哈希表已有结点的数量

unsigned long used;

}dictht

下面简单介绍以下这几个对象

• 哈希表的底层数组table，存放的是哈希表结点，即键值对（下面会说）

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

• used属性记录了哈希表目前已经有的结点数量

• sizemask属性的值总是等于size-1，这个属性和哈希值一起决定插入进来的键值对会被放入数组里面的哪个位置。

哈希表结点使用dictEntry结构表示（也是一个结构体），每个dictEntry结构都保存着一个键值对

typedef dictEntry(

//键

void *key;

//值

union{

//指针类型

void *val;

//无符号整数类型 64位

unit64_t u64;

//有符号整数类型 64位

int64_t s64;

} v;

//指向下一个哈希表的结点，形成链表

struct dictEntry *next;

)dictEntry

key属性就是键值对里面的键值，而v属性，也是一个联合体，里面保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个无符号64位整数和有符号64位整数。

next属性是一个指针，指向下一个哈希表结点，这让就形成了一个链表，这个叫做链地址法，用来解决哈希冲突问题。

模型大概像下面这样

现在看看字典的实

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

现（哈希表只是底层实现，还有其他属性）

Redis中的字典由dict.h/dict结构表示

typedef struct dict(

//类型特定函数

dictType *type;

//私有数据

void *privdata;

//哈希表数组

dictht ht[2]

//rehash索引

//当rehash不存在时，值为-1

int rehashidx;

)

• type和pridata是针对不同类型的键值对，为创建多态字典设置的。

• type属性是一个指向dictType结构体的指针，dictType结构保存了一簇用于操作特定类型键值对的函数（也就是不同类型的键值对会对应不同的操作函数），Redis会为用途不同的字典设置不同的类型特定函数。

• pridata属性则保存了需要传给那些类型特定函数的可选参数（也就是type里面的那些操作函数所需要对应类型的参数)

• • dictType如下所示

typedef struct dictType(

//计算哈希值的函数

unsigned int(*hashFunction)…

//复制键的函数

void *(*keyDup)…;

//复制值的函数

int (*valDup)…;

//对比键的函数

int (*keyCompare) …;

//销毁键的函数

void (*keyDestruction)…

//销毁值的函数

void (*valDestructor)…

)

​ 里面总共有5个方法，计算哈希值、复制键、复制值、对比键（没有对比值）、销毁键、销毁值

• ht是一个哈希表数组，ht[2]代表里面存储了两个哈希表，在一般情况下，只会使用ht[0]里面的哈希表，而ht[1]里面的哈希表只会在ht[0]哈希表进行rehash操作时才会使用。

• 除了ht[1]跟rehash相关外，还有一个rehashidx属性，它记录了rehash目前的进度，如果目前没有进行rehash的话，它的值为-1。

当要将一个新的键值对添加到字典中时，程序需要先根据键值计算出哈希值，然后根据哈希值计算出索引值，然后再根据索引值，将包含键值对的哈希表结点放到哈希表数组的指定索引上面

计算哈希值，其实就是调用字典里面的type指向的dictType结构体，里面有个方法就是计算哈希值的。

过程如下

#使用字典设置的哈希函数，计算键key的哈希值

hash = dict -> type -> hashFunction(key);

#使用哈希表的sizemask属性和哈希值来计算出索引值

#根据情况的不同，哈希表可以选择ht[0]或者ht[1]

index = hash & dict->ht[x].sizemask;