共计 9525 个字符，预计需要花费 24 分钟才能阅读完成。
这篇文章主要介绍“MySQL 动态 hash 结构常用的实现方式”，在日常操作中，相信很多人在 MySQL 动态 hash 结构常用的实现方式问题上存在疑惑，丸趣 TV 小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”MySQL 动态 hash 结构常用的实现方式”的疑惑有所帮助！接下来，请跟着丸趣 TV 小编一起来学习吧！
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 结构的计算掩码的公式是：
代码：
182 static uint my_hash_mask(my_hash_value_type hashnr, size_t buffmax,
183 size_t maxlength)
184 {
185 if ((hashnr (buffmax-1)) maxlength) return (hashnr (buffmax-1));
186 return (hashnr ((buffmax 1) -1));
187 }
这里 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 结构的特点就是在插入新元素之前，试着恢复原来本该属于当前新开辟数组的位置元素，那么属于这个新地方的元素的下标计算方法：
386 halfbuff= info- blength 1;
387
388 idx=first_index=info- records-halfbuff;
这段代码的意思就是先把 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 掩码的情况下，几个重要的表示位，我说下我理解的意义：（可能有偏差）
LowFind：表示有元素属于当前的 hash 掩码
LowUsed：低位元素是否还占据了老的空闲位置（false 代表上一个低位元素占据了新的空闲位置，true 代表使用的还是老的位置）
HighFind：表示有元素不属于当前的 hash 掩码，等于当前掩码 +blength/2
HighUsed：高位元素是否占据了老的空闲位置（false 代表上一个高位元素占据了新的空闲位置，true 代表使用的还是老的位置）
重要的变量：
empty：表示 hash 结构中空闲的 index
gpos：表示属于低位（当前掩码）的上一个元素的 index
ptr_to_rec：表示属于当前掩码的上一个元素的 data
gpos2：表示属于当前掩码 +blength/ 2 的上一个元素的 index
ptr_to_rec2：表示属于高位（当前掩码 +blength/2）的上一个元素的 data
对于元素的移动，是从当前 records-blength/ 2 的元素开始，开始调整具有相同 hash 掩码元素的位置（原因参看前面的解释，由于属于当前位置的元素按照 2 /blength 被重新计算掩码，这个位置一定是 records-blength/2），大体上分为两种情况，一种是当前位置的元素的重新按照新的 records 计算 hash 掩码还属于原来的掩码，就认为这个是低位，另一种是当前位置的元素重新按照 records 计算 hash 掩码属于 records 位置，认为这个是高位。
元素位置的调整和 next 指针的变化代码：
385 data=dynamic_element(info- array,0,HASH_LINK*); // 计算 hash 数组第一个元素的位置
386 halfbuff= info- blength 1; // 为了得到元素可能属于 records 位置的 index
387
388 idx=first_index=info- records-halfbuff; // 减去 halfbuff 得到可能属于 records 位置的 index
// 还不满就需要恢复那些放错位置的 index 上的数据
389 if (idx != info- records) /* If some records */
390 {
391 do
392 {
393 pos=data+idx; // 得到第一个 index，低位
394 hash_nr=rec_hashnr(info,pos- data); // 重新计算下 hash 值
395 if (flag == 0) /* First loop; Check if ok */
396 if (my_hash_mask(hash_nr, info- blength, info- records) != first_index)
397 break;
398 if (!(hash_nr halfbuff))// 做与操作，根据 hash 值判断是否是真正属于 records 位置的
399 { /* Key will not move */
// 与操作的结果等于 0 说明这个 hash 值的元素就是属于当前位置的，进入 case1
400 if (!(flag LOWFIND))// 如果元素属于低位没有出现过，进入 case1-a
401 {
402 if (flag HIGHFIND)
// 如果这个元素属于低位，但是这个属于高位的元素已经找到，那么当前元素肯定是由于位置冲突，属于低位，但是被挤到了其他的位置
403 { // 进入 case1-a-1
404 flag=LOWFIND | HIGHFIND;
405 /* key shall be moved to the current empty position */
406 gpos=empty; // 现在的位置 pos 变成 empty
407 ptr_to_rec=pos- data;
408 empty=pos; /* This place is now free */
409 }
410 else
411 { // 进入 case1-a-2
412 flag=LOWFIND | LOWUSED; /* key isn t changed */
413 gpos=pos;
414 ptr_to_rec=pos- data;
415 }
416 }
417 else
418 { // 进入 case1-b
419 if (!(flag LOWUSED))
420 {
421 /* Change link of previous LOW-key */
422 gpos- data=ptr_to_rec;
423 gpos- next= (uint) (pos-data);
424 flag= (flag HIGHFIND) | (LOWFIND | LOWUSED);
425 }
426 gpos=pos;
427 ptr_to_rec=pos- data;
428 }
429 }
430 else // 进入 case2
431 { /* key will be moved */
432 if (!(flag HIGHFIND)) // 进入 case2-a
433 {
434 flag= (flag LOWFIND) | HIGHFIND;
435 /* key shall be moved to the last (empty) position */
436 gpos2 = empty; empty=pos;
437 ptr_to_rec2=pos- data;
438 }
439 else
440 { // 进入 case2-b
441 if (!(flag HIGHUSED))
442 {
443 /* Change link of previous hash-key and save */
444 gpos2- data=ptr_to_rec2;
445 gpos2- next=(uint) (pos-data);
446 flag= (flag LOWFIND) | (HIGHFIND | HIGHUSED);
447 }
448 gpos2=pos;
449 ptr_to_rec2=pos- data;
450 }
451 }
452 }
// 递归到属于这个 hash 掩码冲突链表的最后一个元素
453 while ((idx=pos- next) != NO_RECORD);
454
455 if ((flag (LOWFIND | LOWUSED)) == LOWFIND)
456 {
// 如果没有 LowUsed, 说明当前链表的最后一个元素不是原来的位置，就设置 next 指针为 null
457 gpos- data=ptr_to_rec;
458 gpos- next=NO_RECORD;
459 }
460 if ((flag (HIGHFIND | HIGHUSED)) == HIGHFIND)
461 {
462 gpos2- data=ptr_to_rec2;
463 gpos2- next=NO_RECORD;
464 }
说明：注意元素的移动只是移动 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 的位置，同时要把等于这个元素掩码的链表的最后一个链接到这个新元素上面，这需要找到这个掩码的最后一个元素。
代码：
// 计算这个 records 的掩码
468 idx= my_hash_mask(rec_hashnr(info, record), info- blength, info- records + 1);
469 pos=data+idx;
470 if (pos == empty) // 如果这个掩码的位置是空闲的，直接插入
471 {
472 pos- data=(uchar*) record;
473 pos- next=NO_RECORD;
474 }
475 else
476 {
477 /* Check if more records in same hash-nr family */
478 empty[0]=pos[0];
// 计算 pos 位置元素的掩码
479 gpos= data + my_hash_rec_mask(info, pos, info- blength, info- records + 1);
480 if (pos == gpos) // 如果相等，直接插入元素到空闲位置，同时把 pos 位置的 next 指针指到新元素
481 {
482 pos- data=(uchar*) record;
483 pos- next=(uint) (empty – data);
484 }
485 else
// 如果掩码不相同，找到掩码等于 gpos 的最后一个元素，同时把最后一个元素的 next 指针指到新的元素
486 {
487 pos- data=(uchar*) record;
488 pos- next=NO_RECORD;
489 movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
490 }
491 }
492 if (++info- records == info- blength)
493 info- blength+= info- blength;
494 return(0);
到此，关于“MySQL 动态 hash 结构常用的实现方式”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注丸趣 TV 网站，丸趣 TV 小编会继续努力为大家带来更多实用的文章！
