MySQL動態hash結構常用的實現方式

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

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結構的計算掩碼的公式是：
代碼：

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是當前數組中記錄的個數（它就是當前數組的長度，分配的空間），這里通過代碼可以看到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結構的特點就是在插入新元素之前，試著恢復原來本該屬于當前新開辟數組的位置元素，那么屬于這個新地方的元素的下標計算方法：

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

2. 387

3. 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掩碼的情況下，幾個重要的表示位，我說下我理解的意義：（可能有偏差）

1. LowFind：表示有元素屬于當前的hash掩碼

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

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

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

重要的變量：

1. empty：表示hash結構中空閑的index

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

3. ptr_to_rec：表示屬于當前掩碼的上一個元素的data

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

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

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

1.  

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

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

4. 387 

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

6.       //還不滿就需要恢復那些放錯位置的index上的數據

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))//做與操作，根據hash值判斷是否是真正屬于records位置的

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

18.        //與操作的結果等于0說明這個hash值的元素就是屬于當前位置的，進入case1

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

20. 401         {

21. 402           if (flag & HIGHFIND)

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

23. 403           {                        //進入case1-a-1

24. 404             flag=LOWFIND | HIGHFIND;

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

26. 406             gpos=empty;             //現在的位置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           {                            //進入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         {                             //進入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                            //進入case2

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

9. 432         if (!(flag & HIGHFIND))       //進入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         {                             //進入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,說明當前鏈表的最后一個元素不是原來的位置，就設置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：當前元素的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的位置，同時要把等于這個元素掩碼的鏈表的最后一個鏈接到這個新元素上面，這需要找到這個掩碼的最后一個元素。
代碼：

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.  

到此，關于“MySQL動態hash結構常用的實現方式”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！