java开发工程师，专注于内核源码，算法，数据结构。 qq：630501400
分类： C/C++
2012-12-16 22:29:55
MySQL动态hash结构
1.常用的实现方式
前一段时间一直在研究mysql中的hash结构，大概搞清楚了这种no empty slot的hash结构，读了几篇关于mysql中的hash结构文章，发现很多文章对于这种动态hash的关键点解释不够清楚，特此把这些天看mysql中hash的这段代码的体会写一下。
mysql中的hash结构不同于一般的那种用链表解决冲突的hash结构，链表解决冲突的hash结构用在memcached，jdk中，最常见的hash结构如下图：
这种hash结构实现起来十分简单，事先分配好一个2^n大小的一个数组，然后对键值对2^n取余数，然后把数据根据余数放到相应的数组下标中，如果恰好这个位置元素已经被其他元素占据了，那么就通过一个单链表，来解决键值冲突，如果hash结构中键值的个数超过一定的阈值，就认为这个结构中数据元素太多了，很高的概率hash后必须通过遍历冲突链表来找到键值，这时再把hash数组的规模以2的倍数增长，然后rehash每个元素即可。
还有一种hash结构也是预先分配好一个数组，如果元素冲突，不采取链表解决冲突，采取取下一个空闲位置作为元素的真实存储地址。
不管怎样，上面的这两种hash结构的优点就是好理解，好实现，缺点就是浪费空间，可以发现，hash数组是预先分配好的，那么元素的空间都是已经定的了，例子：如果按照上面的结构，如果4位置永远没有元素的话，那么这个位置占有的空间永远就是浪费的。
2.无空闲空间的动态hash结构
mysql中的hash结构的特点就是没有浪费的空闲空间，数组是动态分配的，任何时刻，这个数组所开辟的空间总是和当前hash结构中元素的个数相同。
实现的重点就在于对一个元素求hash值然后通过一个计算掩码的公式求得这个元素真实的hash数组的位置，在之前那两中hash结构中，这个公式一般是：hash mod 2^n，但是这个动态hash结构的计算掩码的公式是：
代码：
这里hashnr是一个字符串所代表的hash值，buffmax是2^n,maxlength是当前数组中记录的个数（它就是当前数组的长度，分配的空间），这里通过代码可以看到maxlength介于buffmax/2到buffmax之间。上面这段代码的意思是，按照原有的那种取余数的方式计算掩码，对hashnr除以buffmax取余数，这里会出现一种情况就是有可能求余得到的键值会大于当前等于当前record的数量，按照原来的方式来说只要对buffmax求余数，那么从对应的hash数组的范围就是[0，buffmax-1],在这区间都是分配好的内存，但是动态hash结构中，不会分配超过records的数组，也就是从(records,buffmax-1]是没有分配内存的，数组的大小就是records，而不是buffmax，这里处理方法就是把buffmax除以2后，再去取得余数，得到对应的hash键值。
这里除以2，为什么不除以3，是另有玄机的，可以知道对于一个数除以a，和这个数除以2/a得到的余数之差就是2/a，这个是必然的，例如39/8=7，那么39/4=3，7和3之间差的是4，就是4=8/2，那么就说明了如果hash值对buffmax求余的话，如果大于等于records，那么就会折半再去取余数，这个余数和真实余数之间差buffmax/2。
可以看出这个动态hash表在求余数大于等于records的情况下，选择了一种折中的办法，就是把这个hash值通过buffmax/2求得一个临时的hash掩码。
这个动态hash表，每插入一个元素records就会加1，如果records==buffmax时，buffmax就会再次增大两倍。这个规则我们会发现有问题，先假设上次我们成功插入了元素，掩码落在了[0,records-1]之内，这时由于成功插入了新的元素records就会加1，这时如果原来的掩码通过buffmax计算出来的掩码比records大，就落在[0，records)之内，现在records增加了一位，那么原来存放上一个记录的位置就出现了问题。他应该在当前records的位置。
所以这种动态hash结构的特点就是在插入新元素之前，试着恢复原来本该属于当前新开辟数组的位置元素，那么属于这个新地方的元素的下标计算方法：
这段代码的意思就是先把blength（records位于[blength/2,blength]之间）除以2，然后当前records减去halfbuff即可，就是能计算出上一步本该属于当前位置的元素的下标，这个过程就是前面讲到求余数的逆过程，举例：如果当前records=5 blength=8，那么如果一个元素hash值是13那么通过求掩码知道，去余数是5，但是这时records=5，那么通过那种折中的办法，13/4=1，那么1就是最终的掩码的位置。那么上一步插入了数据之后，records=6，那么原来上一步插入数据13就应该是掩码=5，那么当前records=6，6-5=1，这个1位置的元素就是上一步有可能掩码是5的元素，由于records的限制，被放到了1的位置，这是就需要把他重新放大掩码为5的位置上来。
如何知道当前hash值是否是由于records的限制被放到1的位置，还是通过直接计算掩码得到本该属于他的位置1的地方。通过位操作符&就可以得到结果
398 if (!(hash_nr & halfbuff))
这句代码的意思就是判断这个hash值是否属于低位（本该属于低位还是被records限制放到的低位，低位以records为界），还是刚才的例子13&4>0,那么就说明13的hash值属于高位，不属于原来掩码为1的位置；9&4=0，那么就说明9这个元素就是属于掩码位置为1的位置。
通过上面的一段分析，动态hash结构，每次插入新的元素就要分配一个元素的位置，首先要去移动上一步被放到低位的元素，恢复到原来属于它的位置。这里只需要处理records-halfbuff位置的元素，因为在这个元素之前都已经处理过了，比这个元素大的处理移动不了，因为records的大小还没有到达能够移动这些大掩码的数据。画个图来解释一下前面讲到的知识。
如图所示,hash结构已经存储了5个元素，现在records=5，blength=8，蓝色的空间（index=[0,4]）代表已经分配的空间，每个分配的空间都被数据占用，没有空闲的，index=5的绿色空间是新分配的,用于新插入新的数据，红色空间，index=[6,7]是不存在的，为了显示blength才画出来。那么在插入新数据之前，因为新分配的空间可能原先属于hash掩码是5的元素，那么在插入新元素之前首先需要找到这个元素，把它放到5的地方，空闲出来的地方才作为没有被利用的位置，插入新的元素。要知道原本属于index=5的元素一定被hash到了index=1的地方（因为对blength=8求余为5，那么对4求余那么一定是1），那么看看index=1的元素hash值到底是多少，如果是1，那么index=1的元素就不用移动了，否则这个index=1的元素调整到5的位置。
也就是说这个动态hash结构，每次插入一个元素之前都要调整一下原来的结构，把原来被插入到其他index的元素重新移动到属于它本来的index上，这就是动态hash结构的精髓。
3.元素的移动
通过上面的分析，在新插入数据之前，需要调整已有元素的位置，目标就是重新恢复高位元素的链表，同时修正低位元素的链表，因为当前链表就是低位链表，这个链表含有高位元素，要把恢复到起点是records元素高位链表中，当前链表起点就是records-blength/2元素，如果这个元素的hash掩码等于records，那么说明这个元素属于index=records，那么需要移动这个元素到这个位置，同时这个元素的移动会导致其他节点的next指针的混乱（因为这个元素的位置发生了移动），所以元素移动的目的就是把属于高位的元素回复到原来的位置，同时恢复低位和高位元素的next指针。
移动元素的逻辑参照源代码，需要分清low和high，low表示有元素本来就属于当前的hash掩码，high表示这个元素不属于当前hash掩码值，真正的掩码值是再加上blength/2，在同一个hash掩码的情况下，几个重要的表示位，我说下我理解的意义：（可能有偏差）
重要的变量：
对于元素的移动，是从当前records-blength/2的元素开始，开始调整具有相同hash掩码元素的位置（原因参看前面的解释，由于属于当前位置的元素按照2/blength被重新计算掩码，这个位置一定是records-blength/2），大体上分为两种情况，一种是当前位置的元素的重新按照新的records计算hash掩码还属于原来的掩码，就认为这个是低位，另一种是当前位置的元素重新按照records计算hash掩码属于records位置，认为这个是高位。
元素位置的调整和next指针的变化代码：
说明：注意元素的移动只是移动data，next指针不移动。
case1：当前元素的hash的掩码属于低位，理论上这部分元素不应该被移动，但是如果键值冲突的元素，应该被移动到原来属于它的位置，同时更新next指针
1-a:同样的hash掩码，在低位还没有出现过
1-a-1：在低位没有出现，但是过在高位出现了，那么高位出现的元素，肯定把高位的元素恢复到了records的位 置，这时只需要把这个元素恢复到空闲的位置（高位元素让出的位置），把当前的位置标志为empty。
1-a-2：表示低位没有出现过，高位也没有出现，那么当前的元素保持当前的位置，低位的元素就是要保持原有的hash掩码的位置。
1-b：表示当前元素的前一个低位元素占据新的空闲的位置，这时新的空闲位置的next指针还是原来的，需要上一个低位元素的next指针指到当前位置的低位元素。
举例：如果是当前元素是低位，上一个元素属于低位，同时上个元素由于高位元素让出了位置，更改了低位元素的位置（由于高低位掩码相同，低位被挤到了其他掩码的位置），这时需要重新构造低位元素的next的指针
假设b元素和a元素拥有相同的hash掩码，都属于低位，a元素的位置不属于当前掩码的位置，需要被调到绿色的位置，同时a原来的位置变成了空闲的位置，a位置需要重设置a指向b的next指针。
代码中有个细节：
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
这段代码的意思是：flag中变为 LOWFIND | LOWUSED，同时去掉状态HIGHUSED，表示上一个元素不是高位元素了，这是因为设置完当前元素b和上一个元素a的next指针后（a->next=b），如果下一个元素c是高位的话，那么按照原来逻辑b->next=c,那么这样next链表就会出现错误，所以这时候把HIGHUSED设置成false，这样就导致了递归到c元素时会重新设置上一个高位元素到当前元素c的next指针。
Case2：表示当前元素是高位元素
2-a：如果之前没有出现过高位元素，那么就把当前元素放到空闲的位置，如果不是第一个高位元素，就不需要移动了，因为后面元素的链表是完整的，第二个元素到后面的高位元素next指针都是对的，只是第一个元素到第二个高位元素的next指针不对，因为第一个高位元素被移动到了新的empty的位置。
2-b：这种情况类似于1-b，就是设置第一个高位元素的next指针到第二个元素，后面的next指针都正确，不用管，这 种情况会导致后面一个元素如果是低位元素，需要调整上一个低位元素next指针指到下一个低位元素，所以这种情况需要表达式flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED)屏蔽掉状态LOWUSED。
4.新元素的插入
hash结构的records数量增加了1，导致了hash结构重新调整了掩码等于records和records-blength/2（高位元素和低位元素）的元素的位置。这是新元素就可以插入了。计算新元素的掩码，找到相应的位置，如果那个位置和empty指针的位置相同，那么说明这个元素是这个掩码的第一个元素，直接插入即可。不等于empty指针的位置，那么说明有元素占据了属于新元素的位置，可能是hash掩码相同的元素，或者掩码不同的元素。如果是掩码相同，那么就把当前元素放到empty的位置，同时原来位置的元素的next指针指到empty的位置。如果掩码不同，把当前元素放到empty的位置，同时要把等于这个元素掩码的链表的最后一个链接到这个新元素上面，这需要找到这个掩码的最后一个元素。
代码：
总结：
本文介绍分析了一种无浪费空间的动态hash结构，这种hash结构的特点：对元素掩码位置的空间不存在时，先暂时放到低位中（位置是records-blength/2），新的元素插入时，空间被分配了，重新把暂时放到低位的元素恢复到原来的高位中，恢复原来位置时需要同时恢复低位链表和高位链表。作者水平有限，分析不到位和有错误的地方，希望大家积极讨论。
参考文章：
