MySQL動態(tài)hash結(jié)構(gòu)常用的實現(xiàn)方式

這篇文章主要介紹“MySQL動態(tài)hash結(jié)構(gòu)常用的實現(xiàn)方式”，在日常操作中，相信很多人在MySQL動態(tài)hash結(jié)構(gòu)常用的實現(xiàn)方式問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”MySQL動態(tài)hash結(jié)構(gòu)常用的實現(xiàn)方式”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

MySQL動態(tài)hash結(jié)構(gòu)
1.常用的實現(xiàn)方式
      前一段時間一直在研究mysql中的hash結(jié)構(gòu)，大概搞清楚了這種no empty slot的hash結(jié)構(gòu)，讀了幾篇關(guān)于mysql中的hash結(jié)構(gòu)文章，發(fā)現(xiàn)很多文章對于這種動態(tài)hash的關(guān)鍵點解釋不夠清楚，特此把這些天看mysql中hash的這段代碼的體會寫一下。
      mysql中的hash結(jié)構(gòu)不同于一般的那種用鏈表解決沖突的hash結(jié)構(gòu)，鏈表解決沖突的hash結(jié)構(gòu)用在memcached，jdk中，最常見的hash結(jié)構(gòu)如下圖：

      這種hash結(jié)構(gòu)實現(xiàn)起來十分簡單，事先分配好一個2^n大小的一個數(shù)組，然后對鍵值對2^n取余數(shù)，然后把數(shù)據(jù)根據(jù)余數(shù)放到相應(yīng)的數(shù)組下標(biāo)中，如果恰好這個位置元素已經(jīng)被其他元素占據(jù)了，那么就通過一個單鏈表，來解決鍵值沖突，如果hash結(jié)構(gòu)中鍵值的個數(shù)超過一定的閾值，就認(rèn)為這個結(jié)構(gòu)中數(shù)據(jù)元素太多了，很高的概率hash后必須通過遍歷沖突鏈表來找到鍵值，這時再把hash數(shù)組的規(guī)模以2的倍數(shù)增長，然后rehash每個元素即可。
      還有一種hash結(jié)構(gòu)也是預(yù)先分配好一個數(shù)組，如果元素沖突，不采取鏈表解決沖突，采取取下一個空閑位置作為元素的真實存儲地址。
      不管怎樣，上面的這兩種hash結(jié)構(gòu)的優(yōu)點就是好理解，好實現(xiàn)，缺點就是浪費空間，可以發(fā)現(xiàn)，hash數(shù)組是預(yù)先分配好的，那么元素的空間都是已經(jīng)定的了，例子：如果按照上面的結(jié)構(gòu)，如果4位置永遠(yuǎn)沒有元素的話，那么這個位置占有的空間永遠(yuǎn)就是浪費的。

2.無空閑空間的動態(tài)hash結(jié)構(gòu)

      mysql中的hash結(jié)構(gòu)的特點就是沒有浪費的空閑空間，數(shù)組是動態(tài)分配的，任何時刻，這個數(shù)組所開辟的空間總是和當(dāng)前hash結(jié)構(gòu)中元素的個數(shù)相同。
      實現(xiàn)的重點就在于對一個元素求hash值然后通過一個計算掩碼的公式求得這個元素真實的hash數(shù)組的位置，在之前那兩中hash結(jié)構(gòu)中，這個公式一般是：hash mod 2^n，但是這個動態(tài)hash結(jié)構(gòu)的計算掩碼的公式是：
代碼：

1.  

2. 182 static uint my_hash_mask(my_hash_value_type hashnr, size_t buffmax,

3. 183                          size_t maxlength)              

4. 184 {  

5. 185   if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1)); 

6. 186   return (hashnr & ((buffmax >> 1) -1));

7. 187 }  

       這里hashnr是一個字符串所代表的hash值，buffmax是2^n,maxlength是當(dāng)前數(shù)組中記錄的個數(shù)（它就是當(dāng)前數(shù)組的長度，分配的空間），這里通過代碼可以看到maxlength介于buffmax/2到buffmax之間。上面這段代碼的意思是，按照原有的那種取余數(shù)的方式計算掩碼，對hashnr除以buffmax取余數(shù)，這里會出現(xiàn)一種情況就是有可能求余得到的鍵值會大于當(dāng)前等于當(dāng)前record的數(shù)量，按照原來的方式來說只要對buffmax求余數(shù)，那么從對應(yīng)的hash數(shù)組的范圍就是[0，buffmax-1],在這區(qū)間都是分配好的內(nèi)存，但是動態(tài)hash結(jié)構(gòu)中，不會分配超過records的數(shù)組，也就是從(records,buffmax-1]是沒有分配內(nèi)存的，數(shù)組的大小就是records，而不是buffmax，這里處理方法就是把buffmax除以2后，再去取得余數(shù)，得到對應(yīng)的hash鍵值。
       這里除以2，為什么不除以3，是另有玄機(jī)的，可以知道對于一個數(shù)除以a，和這個數(shù)除以2/a得到的余數(shù)之差就是2/a，這個是必然的，例如39/8=7，那么39/4=3，7和3之間差的是4，就是4=8/2，那么就說明了如果hash值對buffmax求余的話，如果大于等于records，那么就會折半再去取余數(shù)，這個余數(shù)和真實余數(shù)之間差buffmax/2。
       可以看出這個動態(tài)hash表在求余數(shù)大于等于records的情況下，選擇了一種折中的辦法，就是把這個hash值通過buffmax/2求得一個臨時的hash掩碼。
       這個動態(tài)hash表，每插入一個元素records就會加1，如果records==buffmax時，buffmax就會再次增大兩倍。這個規(guī)則我們會發(fā)現(xiàn)有問題，先假設(shè)上次我們成功插入了元素，掩碼落在了[0,records-1]之內(nèi)，這時由于成功插入了新的元素records就會加1，這時如果原來的掩碼通過buffmax計算出來的掩碼比records大，就落在[0，records)之內(nèi)，現(xiàn)在records增加了一位，那么原來存放上一個記錄的位置就出現(xiàn)了問題。他應(yīng)該在當(dāng)前records的位置。
       所以這種動態(tài)hash結(jié)構(gòu)的特點就是在插入新元素之前，試著恢復(fù)原來本該屬于當(dāng)前新開辟數(shù)組的位置元素，那么屬于這個新地方的元素的下標(biāo)計算方法：

1. 386 halfbuff= info->blength >> 1;

2. 387

3. 388 idx=first_index=info->records-halfbuff;

      這段代碼的意思就是先把blength（records位于[blength/2,blength]之間）除以2，然后當(dāng)前records減去halfbuff即可，就是能計算出上一步本該屬于當(dāng)前位置的元素的下標(biāo)，這個過程就是前面講到求余數(shù)的逆過程，舉例：如果當(dāng)前records=5 blength=8，那么如果一個元素hash值是13那么通過求掩碼知道，去余數(shù)是5，但是這時records=5，那么通過那種折中的辦法，13/4=1，那么1就是最終的掩碼的位置。那么上一步插入了數(shù)據(jù)之后，records=6，那么原來上一步插入數(shù)據(jù)13就應(yīng)該是掩碼=5，那么當(dāng)前records=6，6-5=1，這個1位置的元素就是上一步有可能掩碼是5的元素，由于records的限制，被放到了1的位置，這是就需要把他重新放大掩碼為5的位置上來。
      如何知道當(dāng)前hash值是否是由于records的限制被放到1的位置，還是通過直接計算掩碼得到本該屬于他的位置1的地方。通過位操作符&就可以得到結(jié)果
398 if (!(hash_nr & halfbuff))
      這句代碼的意思就是判斷這個hash值是否屬于低位（本該屬于低位還是被records限制放到的低位，低位以records為界），還是剛才的例子13&4>0,那么就說明13的hash值屬于高位，不屬于原來掩碼為1的位置；9&4=0，那么就說明9這個元素就是屬于掩碼位置為1的位置。
      通過上面的一段分析，動態(tài)hash結(jié)構(gòu)，每次插入新的元素就要分配一個元素的位置，首先要去移動上一步被放到低位的元素，恢復(fù)到原來屬于它的位置。這里只需要處理records-halfbuff位置的元素，因為在這個元素之前都已經(jīng)處理過了，比這個元素大的處理移動不了，因為records的大小還沒有到達(dá)能夠移動這些大掩碼的數(shù)據(jù)。畫個圖來解釋一下前面講到的知識。

      如圖所示,hash結(jié)構(gòu)已經(jīng)存儲了5個元素，現(xiàn)在records=5，blength=8，藍(lán)色的空間（index=[0,4]）代表已經(jīng)分配的空間，每個分配的空間都被數(shù)據(jù)占用，沒有空閑的，index=5的綠色空間是新分配的,用于新插入新的數(shù)據(jù)，紅色空間，index=[6,7]是不存在的，為了顯示blength才畫出來。那么在插入新數(shù)據(jù)之前，因為新分配的空間可能原先屬于hash掩碼是5的元素，那么在插入新元素之前首先需要找到這個元素，把它放到5的地方，空閑出來的地方才作為沒有被利用的位置，插入新的元素。要知道原本屬于index=5的元素一定被hash到了index=1的地方（因為對blength=8求余為5，那么對4求余那么一定是1），那么看看index=1的元素hash值到底是多少，如果是1，那么index=1的元素就不用移動了，否則這個index=1的元素調(diào)整到5的位置。
      也就是說這個動態(tài)hash結(jié)構(gòu)，每次插入一個元素之前都要調(diào)整一下原來的結(jié)構(gòu)，把原來被插入到其他index的元素重新移動到屬于它本來的index上，這就是動態(tài)hash結(jié)構(gòu)的精髓。
3.元素的移動
      通過上面的分析，在新插入數(shù)據(jù)之前，需要調(diào)整已有元素的位置，目標(biāo)就是重新恢復(fù)高位元素的鏈表，同時修正低位元素的鏈表，因為當(dāng)前鏈表就是低位鏈表，這個鏈表含有高位元素，要把恢復(fù)到起點是records元素高位鏈表中，當(dāng)前鏈表起點就是records-blength/2元素，如果這個元素的hash掩碼等于records，那么說明這個元素屬于index=records，那么需要移動這個元素到這個位置，同時這個元素的移動會導(dǎo)致其他節(jié)點的next指針的混亂（因為這個元素的位置發(fā)生了移動），所以元素移動的目的就是把屬于高位的元素回復(fù)到原來的位置，同時恢復(fù)低位和高位元素的next指針。
      移動元素的邏輯參照源代碼，需要分清low和high，low表示有元素本來就屬于當(dāng)前的hash掩碼，high表示這個元素不屬于當(dāng)前hash掩碼值，真正的掩碼值是再加上blength/2，在同一個hash掩碼的情況下，幾個重要的表示位，我說下我理解的意義：（可能有偏差）

1. LowFind：表示有元素屬于當(dāng)前的hash掩碼

2. LowUsed：低位元素是否還占據(jù)了老的空閑位置（false代表上一個低位元素占據(jù)了新的空閑位置，true代表使用的還是老的位置）

3. HighFind：表示有元素不屬于當(dāng)前的hash掩碼，等于當(dāng)前掩碼+blength/2

4. HighUsed：高位元素是否占據(jù)了老的空閑位置（false代表上一個高位元素占據(jù)了新的空閑位置，true代表使用的還是老的位置）

重要的變量：

1. empty：表示hash結(jié)構(gòu)中空閑的index

2. gpos：表示屬于低位（當(dāng)前掩碼）的上一個元素的index

3. ptr_to_rec：表示屬于當(dāng)前掩碼的上一個元素的data

4. gpos2：表示屬于當(dāng)前掩碼+blength/2的上一個元素的index

5. ptr_to_rec2：表示屬于高位（當(dāng)前掩碼+blength/2）的上一個元素的data

      對于元素的移動，是從當(dāng)前records-blength/2的元素開始，開始調(diào)整具有相同hash掩碼元素的位置（原因參看前面的解釋，由于屬于當(dāng)前位置的元素按照2/blength被重新計算掩碼，這個位置一定是records-blength/2），大體上分為兩種情況，一種是當(dāng)前位置的元素的重新按照新的records計算hash掩碼還屬于原來的掩碼，就認(rèn)為這個是低位，另一種是當(dāng)前位置的元素重新按照records計算hash掩碼屬于records位置，認(rèn)為這個是高位。
     元素位置的調(diào)整和next指針的變化代碼：

1.  

2. 385   data=dynamic_element(&info->array,0,HASH_LINK*); //計算hash數(shù)組第一個元素的位置

3. 386   halfbuff= info->blength >> 1;       //為了得到元素可能屬于records位置的index

4. 387 

5. 388   idx=first_index=info->records-halfbuff; //減去halfbuff得到可能屬于records位置的index

6.       //還不滿就需要恢復(fù)那些放錯位置的index上的數(shù)據(jù)

7. 389   if (idx != info->records)                             /* If some records */

8. 390   {

9. 391     do

10. 392     {

11. 393       pos=data+idx;             //得到第一個index，低位

12. 394       hash_nr=rec_hashnr(info,pos->data);   //重新計算下hash值

13. 395       if (flag == 0)                            /* First loop; Check if ok */

14. 396         if (my_hash_mask(hash_nr, info->blength, info->records) != first_index)

15. 397           break;

16. 398       if (!(hash_nr & halfbuff))//做與操作，根據(jù)hash值判斷是否是真正屬于records位置的

17. 399       {                                         /* Key will not move */

18.        //與操作的結(jié)果等于0說明這個hash值的元素就是屬于當(dāng)前位置的，進(jìn)入case1

19. 400         if (!(flag & LOWFIND))//如果元素屬于低位沒有出現(xiàn)過，進(jìn)入case1-a

20. 401         {

21. 402           if (flag & HIGHFIND)

22.       //如果這個元素屬于低位，但是這個屬于高位的元素已經(jīng)找到，那么當(dāng)前元素肯定是由于位置沖突，屬于低位，但是被擠到了其他的位置

23. 403           {                        //進(jìn)入case1-a-1

24. 404             flag=LOWFIND | HIGHFIND;

25. 405             /* key shall be moved to the current empty position */

26. 406             gpos=empty;             //現(xiàn)在的位置pos變成empty

27. 407             ptr_to_rec=pos->data;

28. 408             empty=pos;                          /* This place is now free */

29. 409           }

30. 410           else

31. 411           {                            //進(jìn)入case1-a-2

32. 412             flag=LOWFIND | LOWUSED;             /* key isn't changed */

33. 413             gpos=pos;

34. 414             ptr_to_rec=pos->data;

35. 415           }

36. 416         }

37. 417         else

38. 418         {                             //進(jìn)入case1-b

39. 419           if (!(flag & LOWUSED))

40. 420           {

41. 421             /* Change link of previous LOW-key */

42. 422             gpos->data=ptr_to_rec;

43. 423             gpos->next= (uint) (pos-data);

44. 424             flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);

1.  

2. 425           }

3. 426           gpos=pos;

4. 427           ptr_to_rec=pos->data;

5. 428         }

6. 429       }

7. 430       else                            //進(jìn)入case2

8. 431       {                                         /* key will be moved */

9. 432         if (!(flag & HIGHFIND))       //進(jìn)入case2-a

10. 433         {

11. 434           flag= (flag & LOWFIND) | HIGHFIND;

12. 435           /* key shall be moved to the last (empty) position */

13. 436           gpos2 = empty; empty=pos;

14. 437           ptr_to_rec2=pos->data;

15. 438         }

16. 439         else

17. 440         {                             //進(jìn)入case2-b

18. 441           if (!(flag & HIGHUSED))

19. 442           {

20. 443             /* Change link of previous hash-key and save */

21. 444             gpos2->data=ptr_to_rec2;

22. 445             gpos2->next=(uint) (pos-data);

23. 446             flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);

24. 447           }

25. 448           gpos2=pos;

26. 449           ptr_to_rec2=pos->data;

27. 450         }

28. 451       }

29. 452     }

30. //遞歸到屬于這個hash掩碼沖突鏈表的最后一個元素

31. 453     while ((idx=pos->next) != NO_RECORD);

32. 454 

33. 455     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)

34. 456     {

35. //如果沒有LowUsed,說明當(dāng)前鏈表的最后一個元素不是原來的位置，就設(shè)置next指針為null

36. 457       gpos->data=ptr_to_rec;

37. 458       gpos->next=NO_RECORD;

38. 459     }

39. 460     if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)

40. 461     {

41. 462       gpos2->data=ptr_to_rec2;

42. 463       gpos2->next=NO_RECORD;

43. 464     }

44.  

說明：注意元素的移動只是移動data，next指針不移動。
case1：當(dāng)前元素的hash的掩碼屬于低位，理論上這部分元素不應(yīng)該被移動，但是如果鍵值沖突的元素，應(yīng)該被移動到原來屬于它的位置，同時更新next指針
     1-a:同樣的hash掩碼，在低位還沒有出現(xiàn)過
          1-a-1：在低位沒有出現(xiàn)，但是過在高位出現(xiàn)了，那么高位出現(xiàn)的元素，肯定把高位的元素恢復(fù)到了records的位 置，這時只需要把這個元素恢復(fù)到空閑的位置（高位元素讓出的位置），把當(dāng)前的位置標(biāo)志為empty。
          1-a-2：表示低位沒有出現(xiàn)過，高位也沒有出現(xiàn)，那么當(dāng)前的元素保持當(dāng)前的位置，低位的元素就是要保持原有的hash掩碼的位置。
     1-b：表示當(dāng)前元素的前一個低位元素占據(jù)新的空閑的位置，這時新的空閑位置的next指針還是原來的，需要上一個低位元素的next指針指到當(dāng)前位置的低位元素。
  舉例：如果是當(dāng)前元素是低位，上一個元素屬于低位，同時上個元素由于高位元素讓出了位置，更改了低位元素的位置（由于高低位掩碼相同，低位被擠到了其他掩碼的位置），這時需要重新構(gòu)造低位元素的next的指針

       假設(shè)b元素和a元素?fù)碛邢嗤膆ash掩碼，都屬于低位，a元素的位置不屬于當(dāng)前掩碼的位置，需要被調(diào)到綠色的位置，同時a原來的位置變成了空閑的位置，a位置需要重設(shè)置a指向b的next指針。
代碼中有個細(xì)節(jié)：
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
      這段代碼的意思是：flag中變?yōu)?LOWFIND | LOWUSED，同時去掉狀態(tài)HIGHUSED，表示上一個元素不是高位元素了，這是因為設(shè)置完當(dāng)前元素b和上一個元素a的next指針后（a->next=b），如果下一個元素c是高位的話，那么按照原來邏輯b->next=c,那么這樣next鏈表就會出現(xiàn)錯誤，所以這時候把HIGHUSED設(shè)置成false，這樣就導(dǎo)致了遞歸到c元素時會重新設(shè)置上一個高位元素到當(dāng)前元素c的next指針。        

Case2：表示當(dāng)前元素是高位元素

      2-a：如果之前沒有出現(xiàn)過高位元素，那么就把當(dāng)前元素放到空閑的位置，如果不是第一個高位元素，就不需要移動了，因為后面元素的鏈表是完整的，第二個元素到后面的高位元素next指針都是對的，只是第一個元素到第二個高位元素的next指針不對，因為第一個高位元素被移動到了新的empty的位置。

      2-b：這種情況類似于1-b，就是設(shè)置第一個高位元素的next指針到第二個元素，后面的next指針都正確，不用管，這 種情況會導(dǎo)致后面一個元素如果是低位元素，需要調(diào)整上一個低位元素next指針指到下一個低位元素，所以這種情況需要表達(dá)式flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED)屏蔽掉狀態(tài)LOWUSED。

4.新元素的插入
        hash結(jié)構(gòu)的records數(shù)量增加了1，導(dǎo)致了hash結(jié)構(gòu)重新調(diào)整了掩碼等于records和records-blength/2（高位元素和低位元素）的元素的位置。這是新元素就可以插入了。計算新元素的掩碼，找到相應(yīng)的位置，如果那個位置和empty指針的位置相同，那么說明這個元素是這個掩碼的第一個元素，直接插入即可。不等于empty指針的位置，那么說明有元素占據(jù)了屬于新元素的位置，可能是hash掩碼相同的元素，或者掩碼不同的元素。如果是掩碼相同，那么就把當(dāng)前元素放到empty的位置，同時原來位置的元素的next指針指到empty的位置。如果掩碼不同，把當(dāng)前元素放到empty的位置，同時要把等于這個元素掩碼的鏈表的最后一個鏈接到這個新元素上面，這需要找到這個掩碼的最后一個元素。
代碼：

1.  

2.        //計算這個records的掩碼

3. 468   idx= my_hash_mask(rec_hashnr(info, record), info->blength, info->records + 1);

4. 469   pos=data+idx;

5. 470   if (pos == empty)    //如果這個掩碼的位置是空閑的，直接插入

6. 471   {

7. 472     pos->data=(uchar*) record;

8. 473     pos->next=NO_RECORD;

9. 474   }

10. 475   else

11. 476   {

12. 477     /* Check if more records in same hash-nr family */

13. 478     empty[0]=pos[0];

14.        //計算pos位置元素的掩碼

15. 479     gpos= data + my_hash_rec_mask(info, pos, info->blength, info->records + 1);

16. 480     if (pos == gpos) //如果相等，直接插入元素到空閑位置，同時把pos位置的next指針指到新元素

17. 481     {

18. 482       pos->data=(uchar*) record;

19. 483       pos->next=(uint) (empty - data);

20. 484     }

21. 485     else

22.         //如果掩碼不相同，找到掩碼等于gpos的最后一個元素，同時把最后一個元素的next指針指到新的元素

23. 486     {

24. 487       pos->data=(uchar*) record;

25. 488       pos->next=NO_RECORD;

26. 489       movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));

27. 490     }

28. 491   }

29. 492   if (++info->records == info->blength)

30. 493     info->blength+= info->blength;

31. 494   return(0);

32.  

到此，關(guān)于“MySQL動態(tài)hash結(jié)構(gòu)常用的實現(xiàn)方式”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>