hash字典,又称hash表,也叫映射(Map)或者散列表,主要存储键值对,是程序开发语言中最最最常用的数据结构.也是我们大学计算机专业的必修课.一般的高级语言都会内置hash字典的实现.但是C并没有内置,所以Redis需要自己实现一套hash字典.
redis关于字典的实现,主要由dict.h和dict.c两个文件实现.
1C语言基础static关键字的作用static修饰局部变量,此变量只能在作用域内访问,但是变量存储在静态区,函数执行完后变量不会销毁.普通局部变量在函数执行完后,立即销毁
static修饰全局变量,表示此变量只能在当前文件内访问
static修饰函数,表示此函数只能在当前文件内访问
具体细节可以参考黄裕玲的
union(共用体)与struct(结构体)的区别结构体的各个成员会占用不同的内存，互相之间没有影响.
共用体的所有成员占用同一段内存，修改一个成员会影响其余所有成员.
结构体占用的内存大于等于所有成员占用的内存的总和（成员之间可能会存在缝隙），共用体占用的内存等于最长的成员占用的内存。共用体使用了内存覆盖技术，同一时刻只能保存一个成员的值，如果对新的成员赋值，就会把原来成员的值覆盖掉。
2hash字典的结构hash表一般的实现都是数组+链表来实现.数组来做hash散列,链表用来解决hash冲突的问题.如果我们了解过java的hashMap的话,不难发现,java7的hashMap的实现跟redis的hash表的实现如出一辙,java8关于hashMap的实现会略复杂一些,增加了链表转红黑树的内容.数据结构都是通用的,如果看过jdk的hashMap的源码,再看redis的hash表,基本没什么难度.
redis的hash字典大体结构图如下:
2.1hash表节点的结构//hash表的节点
typedefstructdictEntry{
//节点的key
void*key;
//节点的值v,v可以是指针,也可以是uint64整数,也可以是int64整数,还可以是浮点数
union{
void*val;
uint64_tu64;
int64_ts64;
doubled;
}v;
//下一个节点
structdictEntry*next;
}dictEntry;
hash表节点,主要是包含了k,v键值对和下一个节点的指针,从结构体我们可以看出,这是一个hash表节点会组成一个单向链表
hash表的key是Void*指针类型,也就相当于java的Object,值v是一个共用体,也可以是uint64整数,也可以是int64整数,还可以是浮点数
2.2hash表结构//hash表结构体
typedefstructdictht{
//hash表的指针数组,dictEntry*表示hash节点的指针,再加一个*,也就是dictEntry**表示数组的首地址
dictEntry**table;
//hash数组大小,一般为2^n
unsignedlongsize;
//hash数组长度掩码,sizemask=size-1
unsignedlongsizemask;
//hash表的kv对的个数
unsignedlongused;
}dictht;
由hash表结构,我们可以看出,redis也是通过数组做hash散列的.
hash表数组的size长度一般为2^n的大小,保证这样的大小可以通操作来计算出hash槽的位置,如果数组容量不是2^n的大小,那么就需要通过取模来获取hash表的槽索引,取模操作相对操作性能会差一些.
szimmask表示数组掩码,一般是size-1,如:假如数组长度为8,那么掩码就为7,掩码转换成二进制就为...
used表示hash表中kv的个数
2.3字典类型的结构//字典类型
typedefstructdictType{
//键的hash函数
uint64_t(*hashFunction)(constvoid*key);
//复制键的函数
void*(*keyDup)(void*privdata,constvoid*key);
//值的复制函数
void*(*valDup)(void*privdata,constvoid*obj);
//键的比较函数
int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);
//键的销毁函数
void(*keyDestructor)(void*privdata,void*key);
//值的销毁函数
void(*valDestructor)(void*privdata,void*obj);
//根据扩容后的数组的内存和负载因子判断是否可以扩容
int(*expandAllowed)(size_tmoreMem,doubleusedRatio);
}dictType;
字典类型的结构体主要提供相关函数的指针,用于做扩展,类似java的抽象方法和接口
这样做就相当于实现多态了,不同的dictType对应的函数指针都不一样
2.4redis字典的结构//字典的结构体
typedefstructdict{
//字典类型的指针
dictType*type;
//携带的私有数据
void*privdata;
//hash字典的数组,长度为2,主要是用于渐进式hash时使用
dicththt[2];
//rehash下一个要迁移的桶索引,rehash不进行时为-1
longrehashidx;/*rehashingnotinprogressifrehashidx==-1*/
//pauserehash0表示rehash是暂停的.安全的迭代需要停止
int16_tpauserehash;/*If0rehashingispaused(0indicatescodingerror)*/
}dict;
由上面的结构体,我们可以看出redis的字典是有两个hash表组成的.常用的hash表是ht[0],当进行rehash时,会使用到ht[1]做渐进式重hash.
privdata和type主要是为了实现多态字典而已设置的,privdata主要是携带了特定函数需要的一些可选参数,type则保存了一批可自定义特定函数的指针,redis会根据字典的用途,在type中设置不同的特定函数
rehashidx当字典正在rehash时,会将下一个要rehash的槽索引记录到当前字段
pauserehash表示暂停当前的rehash状态,安全的迭代和扫描都需要暂停rehash的,当pauserehash大于0时,则表示rehash暂停,等于0时表示可以rehash.为什么暂停需要计数?因为安全迭代器和扫描都有可能同时存在多个,所以pauserehash的值是很有可能大于1的
3字典通用操作实现3.1创建字典/*Createanewhashtable*/
//创建空字典的指针
dict*dictCreate(dictType*type,
void*privDataPtr)
{
//分配字典内存
dict*d=zmalloc(sizeof(*d));
//初始化字典
_dictInit(d,type,privDataPtr);
//返回字段指针
returnd;
}
/*Initializethehashtable*/
//初始化hash表
int_dictInit(dict*d,dictType*type,
void*privDataPtr)
{
//重置第0个hash表
_dictReset(d-ht[0]);
//重置第1个hash表
_dictReset(d-ht[1]);
//设置字典类型
d-type=type;
//设置私有数据
d-privdata=privDataPtr;
//不进行rehash时,为-1
d-rehashidx=-1;
d-pauserehash=0;
returnDICT_OK;
}
//hash字典重置
staticvoid_dictReset(dictht*ht)
{
//清空
ht-table=NULL;
ht-size=0;
ht-sizemask=0;
ht-used=0;
}
创建字典主要的操作是,分配字典内存,并且对字典类型和私有数据进行赋值,注意,此时字典的hash表还没初始化的,其他统计数据都是0
3.2根据键查询节点//根据key查询节点
dictEntry*dictFind(dict*d,constvoid*key)
{
dictEntry*he;
uint64_th,idx,table;
//如果字典为空,则直接返回NULL
if(dictSize(d)==0)returnNULL;/*dictisempty*/
//如果字典正在rehash,则执行一次rehash步聚
if(dictIsRehashing(d))_dictRehashStep(d);
//计算key的hash值
h=dictHashKey(d,key);
//遍历字典的hash表
for(table=0;table=1;table++){
//计算出key所有的hash槽索引
idx=hd-ht[table].sizemask;
//根据hash槽获取首节点
he=d-ht[table].table[idx];
//遍历链表,直到找到key一样的节点
while(he){
//如果找到,则直接返回找到的节点
if(key==he-key
dictCompareKeys(d,key,he-key))
returnhe;
he=he-next;
}
//如果没找到,且字典没有rehash,则直接返回NULL
if(!dictIsRehashing(d))returnNULL;
}
//没找到,返回NULL
returnNULL;
}
//获取key对应的值
void*dictFetchValue(dict*d,constvoid*key){
dictEntry*he;
//根据key查询节点
he=dictFind(d,key);
//如果节点存在,则获取节点的值,否则返回NULL
returnhe?dictGetVal(he):NULL;
}
大概的思路是,计算出给定键key的hash值,然后先在第一个hash表中获取对应的槽索引,如果槽存在链表首节点,则遍历链表,直到找到节点的key与传入的key相等的节点
如果字典正在rehash,那么第一个hash表没找到,则会在第二张hash表中查询
这里注意key的比较,优先比较内存地址是否一样,再用