本文转载自微信公众号《学Java的小姐姐》，作者0618，转载请联系小姐姐正在学习Java公众号。前言各位小可爱们，我们又见面了。今天的文章来自去年面试的面试题，结果被虐了。这部分我就不说了，下次我会做一个特别的，把我在采访中被虐的著名场景写下来。哈哈哈哈，废话少说，开始吧。😂Redis中广泛使用Hash类型，通过字典结构维护key到value的映射。做笔记，这里测试一下。API的使用API??使用起来比较简单，所以大致写下如下。插入数据hset使用hset命令向myhash中插入两个key和value键值对，分别是(name,zhangsan)和(age,20)，返回当前myhash的长度。获取数据hget使用hget命令获取myhash中key为name的值。获取所有数据hgetall使用hgetall命令获取myhash中所有的key和value值。获取所有键使用hkeys命令获取myhash中的所有键值。获取长度使用hlen命令获取myhash的长度。获取所有值使用hvals命令获取myhash中的所有值。具体逻辑图正文即将开始。hash底层主要采用字典dict结构，整体呈现逐层封装。首先，dict由四部分组成，分别是dictType（类型，不是那么重要）、dicttht（核心）、rehashidx（渐进哈希的符号）、iterators（迭代器），其中最重要的是dicttht和rehashidx。接下来是dicttht，它由两个数组组成，一个是真正的数据存储位置，另一个是用于hash过程，包含的变量是真正的数据表和一些公共变量。最后一个数据节点和上一篇提到的双向链表一样。每个节点都有一个next指针，方便指向下一个节点。这样做的目的是为了解决哈希冲突。详情见下图。在这里看不懂没关系，后面我会详细讲解每个模块。（看到这里不要直接跳过）双向链表的定义字典结构dict先来看字典结构dict，包括四个部分，重点是dicttht[2]（真实数据）和rehashidx（渐进哈希符号）。具体图如下。具体代码如下：//字典结构typedefstructdict{dictType*type;//类型，包括一些自定义函数，这些函数使key和value存储void*privdata;//私有数据dictththt[2];//二hashtablelongrehashidx;//渐进式哈希标记，如果为-1，表示hashunsignedlongiterators没有进行中;//正在迭代的迭代器个数}dict;数组结构dictthtdictht主要包括四部分，1是真正的数据dictEntry类型2是数组的大小；3是hash操作的参数sizemask，不是很重要，记住等于size-1即可；4是使用的数据节点数，当前节点有多少数据。具体代码如下：//哈希结构typedefstructdict{dictEntry**table;//真实数据的数组unsignedlongsize;//数组的大小unsignedlongsizemask;//用户将哈希映射到表的位置索引,其值始终等于size-1unsignedlongused;//使用的节点数}dicttht;数据节点dictEntrydictEntry是真正的数据节点，包括key,value和next节点。//每个节点的结构typedefstructdictEntry{void*key;//keyunion{void*val;uint64_tu64;int64_ts64;doubled;}v;//valuestructdictEntry*next;//下一个数据节点的地址}dictEntry;扩展过程让我们从渐进式哈希图的第一部分开始。为什么dictht[2]需要两个数组存储，而真正的数据只需要一个数组就够了？这个其实和Java的HashMap类似，是一种数据加链表的结构，随着数据量的增加，hash碰撞发生的频率越来越高，每个数组后面的链表变长，使得整个链表非常繁琐.如果业务需要大量的查询操作，因为是链表，只能从头开始查询，等一个数组的所有链表都查询完了再开始下一个数组，这样查询时间会被无限延长。这无疑是为了扩容，所以第一个数组存放的是真正的数据，第二个数组是用来扩容的。第一个数组中的节点通过哈希运算映射到第二个数组，然后依次进行。那么在这个过程中还能对外提供服务吗？答案是肯定的，因为它可以随时停止，这就引出了下一个变量rehashidx。（根本不是生硬的过渡，哈哈哈）rehashidx其实是一个符号量。如果为-1，则表示没有当前扩展。如果不是-1，表示当前展开到哪个下标位置，方便下次使用。标记位置继续扩大。这么说是不是太抽象了，还是一头雾水，我把扩展过程发给大家，点赞评论多点赞。第一步：扩容前，rehashidx为-1，表示没有扩容。第一个数组中dictEntry的长度为4，一共有5个节点，所以used为5。Step2展开时，rahashidx为第一个数组的第一个下标位置，为0展开后的大小是大于2的n次方used*2的最小值，即能包含这些节点*2的2的倍数的最小值。因为当前有5个数据节点，used*2=10，大小为展开后的数组为16，是大于10的2次方的最小值。从第一个数组的下标位置0开始，查找第一个元素，找到key为name，value为张三的节点，对它进行散列，找到第二个数组下标为1的位置，保存节点移动过去其实就是指针的移动。这里简单说一下。Step3移动完key为name，value为张三的节点后，继续移动第一个数组dicttht[0]中下标为0的后续节点，移动步骤同上。Step4继续移动第一个数组dicttht[0]中下标为0的后续节点全部移动，开始移动下标1的节点，发现没有数据，于是移动下标2的节点，并同时修改rehashidx为2，移动步骤同上。整个过程的关键点是rehashidx，也就是第一个数组的移动下标位置。如果当前内存不足或操作系统繁忙，可以随时停止扩容过程。如果停止后对对象进行操作，会是什么样子？如果是新增，直接添加第二个数组，因为如果添加到第一个数组，以后还是要移动的，所以没必要浪费如果时间是delete,update,query，先查找第一个数组，如果没有找到，再查询第二个数组。字典的实现（源码分析）创建并初始化字典，首先分配内存，然后调用初始化方法_dictInit，主要是赋值操作。重点关注rehashidx赋值-1（这个验证了刚才的图，-1表示没有进行hash扩展。），最后返回是否创建成功。/*创建并初始化字典*/dict*dictCreate(dictType*type,void*privDataPtr){dict*d=zmalloc(sizeof(*d));_dictInit(d,type,privDataPtr);return;}/*Initializethehashtable*/int_dictInit(dict*d,dictType*type,void*privDataPtr){_dictReset(&d->ht[0]);_dictReset(&d->ht[1]);d->type=type;d->privdata=privDataPtr;d->rehashidx=-1;//赋值为-1，表示没有hashd->iterators=0;returnDICT_OK;}扩容dict中有一个静态方法_dictExpandIfNeed判断是否需要扩容。首先通过dictIsRehashing方法判断是否处于hash状态，该方法调用宏常量#definedictIsRehashing(d)((d)->rehashidx!=-1)，即判断rehashidx是否为-1，如果为-1，即不在hash状态，如果条件为假，则可以展开，如果不为-1，则为hash状态，如果条件为真，则不能展开展开，直接返回常量DICT_OK。然后判断第一个数组的大小是否为0，如果是0则展开到默认大小4，如果不为0则执行下面的代码。然后判断是否需要扩容。if中有3个条件。具体分析如下。最后是调用dictExpand扩展方法，参数为数据节点ht[0].used*2的double大小。上面扩展过程的数组大小16在这里得到了验证。扩展方法比较简单。获取扩展尺寸并将第二个尺寸设置为新尺寸。这么说感觉有点空洞，看流程图。展开流程图具体代码：staticint_dictExpandIfNeeded(dict*d){//判断是否处于展开状态，通过调用宏常量#definedIsRehashing(d)((d)->rehashidx!=-1)//判断是否可以展开if(dictIsRehashing(d))returnDICT_OK;//判断第一个数组的大小是否为0，如果为0则调用展开方法，大小为宏常量//#defineDICT_HT_INITIAL_SIZE4if(d->ht[0].size==0)returndictExpand(d,DICT_HT_INITIAL_SIZE);//下面先列出if条件中用到的参数//staticintdict_can_resize=1;值为1表示可以扩容//staticunsignedintdict_force_resize_ratio=5;//我们分析一下if条件，如果第一个数组中所有节点的个数都大于等于第一个数组的大小（说明节点数据已经有点大了）//并且可以扩容（值为1）或者所有节点数除以数组大小大于5//这个条件表示扩容条件，第一个就是节点必须大于等于数组的长度，//第二点是可以扩容，数据太多，二选一if(d->ht[0].used>=d->ht[0].size&&(dict_can_resize||d->ht[0].used/d->ht[0].size>dict_force_resize_ratio)){//调用扩容方法returndictExpand(d,d->ht[0].used*2);}returnDICT_OK;}intdictExpand(dict*d,unsignedlongsize){dictthtn;//得到展开后的真实大小，找到比size大的最小值，是倍数共2页ze=_dictNextPower(size);//一些判断条件if(dictIsRehashing(d)||d->ht[0].used>size)returnDICT_ERR;if(realsize==d->ht[0].size)returnnDICT_ERR;n.size=realsize;n.sizemask=realsize-1;n.table=zcalloc(realsize*sizeof(dictEntry*));n.used=0;//第一个hash为null，表示初始化完毕if(d->ht[0].table==NULL){d->ht[0]=n;returnDICT_OK;}//是哈希，为第二个哈希设置新的长度，d->ht[1]=n;d->rehashidx=0;//当前设置为hashreturningDICT_OK;}/*找到大于size的最小值，并且是2的倍数*/staticunsignedlong_dictNextPower(unsignedlongsize){unsignedlongi=DICT_HT_INITIAL_SIZE;if(size>=LONG_MAX)returnLONG_MAX;while(1){if(i>=size)returni;i*=2;}}Progressivehashprogressivehash过程已经通过上图说明。下面主要看看代码是怎么实现的，流程是不是？展开后执行dictRehash方法。参数包括要移动的哈希表d和步数n。先判断标志位rehashidx是否等于-1。如果等于-1，则表示散列完成。如果不等于-1，则执行下面的代码。然后循环遍历第一个数组上的每个下标，每次移动下标位置，都需要更新rehashidx的值，每次加1。然后进行第二个循环，遍历下标链表的每个节点，完成数据迁移，主要是指针的移动和一些参数的修改。最后返回一个int值。如果为0，则表示整个数据已经被哈希。如果它返回1，则表示已完成部分哈希，但尚未全部完成。下次可以继续通过rehashidx值进行hash。具体代码如下：//re-hashthishashtable//Redis的哈希表结构有两个table数组，t0和t1，通常只用一个t0，需要re-hash的时候再hash到另一个table数组//参数列表//1.d：要移动的哈希表，结构中对哪个桶进行了重新哈希//2.n：重新哈希N步//返回值返回0表示整表hasbeenre-hashed哈希完成，返回1表示未完成intdictRehash(dict*d,intn){intempty_visits=n*10;//如果当前rehashidx=-1，则返回0，表示哈希完成if(!dictIsRehashing(d))return0;//分为n步，ht[0]仍然没有移动节点while(n--&&d->ht[0].used!=0){dictEntry*de,*nextde;assert(d->ht[0].size>(unsignedlong)d->rehashidx);//第一个循环用于更新rehashidx的值，因为有些桶是空的，所以rehashidx不会每次都前进一个位置，但可能会前进几个位置，但不超过10个。//将rehashidx移动到节点下标ht[0]，即table[d->rehashidx]非空while(d->ht[0].table[d->rehashidx]==NULL){d->rehashidx++;if(--empty_visits==0)return1;}//第二个循环用于将ht[0]表中找到的非空桶中的链表（或单节点）复制到htIn[1]de=d->ht[0].table[d->rehashidx];/*使用循环将数据节点移动过来*/while(de){unsignedinth;nextde=de->next;h=dictHashKey(d,de->key)&d->ht[1].sizemask;de->next=d->ht[1].table[h];d->ht[1].table[h]=de;d->ht[0].used--;d->ht[1].used++;de=nextde;}d->ht[0].table[d->rehashidx]=NULL;d->rehashidx++;}if(d->ht[0].used==0){zfree(d->ht[0].table);d->ht[0]=d->ht[1];_dictReset(&d->ht[1]);d->rehashidx=-1;return0;}return1;}总结本文主要讲Redis的Hash数据类型的字典结构Dict的底层实现，首先使用Hash的一些API，并引出字典结构Dict分析其三个主要组成部分，字典结构Dict，数组结构Dictht，以及数据节点结构DictEntry，然后通过多张流程图讲解扩容过程和rehash过程，最后结合源码描述字典。如创建过程、扩容过程、渐进哈希过程，穿插流程图讲解。
