Go語言 map的實現

數據結構

哈希表的數據結構中一些關鍵的域如下所示：

struct Hmap
{
    uint8   B;    // 可以容納2^B個項
    uint16  bucketsize;   // 每個桶的大小

    byte    *buckets;     // 2^B個Buckets的數組
    byte    *oldbuckets;  // 前一個buckets，只有當正在擴容時才不為空
};

上面給出的結構體只是Hmap的部分的域。需要注意到的是，這里直接使用的是Bucket的數組，而不是Bucket*指針的數組。這意味著，第一個Bucket和后面溢出鏈的Bucket分配有些不同。第一個Bucket是用的一段連續(xù)的內存空間，而后面溢出鏈的Bucket的空間是使用mallocgc分配的。

這個hash結構使用的是一個可擴展哈希的算法，由hash值mod當前hash表大小決定某一個值屬于哪個桶，而hash表大小是2的指數，即上面結構體中的2^B。每次擴容，會增大到上次大小的兩倍。結構體中有一個buckets和一個oldbuckets是用來實現增量擴容的。正常情況下直接使用buckets，而oldbuckets為空。如果當前哈希表正在擴容中，則oldbuckets不為空，并且buckets大小是oldbuckets大小的兩倍。

具體的Bucket結構如下所示：

struct Bucket
{
    uint8  tophash[BUCKETSIZE]; // hash值的高8位....低位從bucket的array定位到bucket
    Bucket *overflow;           // 溢出桶鏈表，如果有
    byte   data[1];             // BUCKETSIZE keys followed by BUCKETSIZE values
};

其中BUCKETSIZE是用宏定義的8，每個bucket中存放最多8個key/value對, 如果多于8個，那么會申請一個新的bucket，并將它與之前的bucket鏈起來。

按key的類型采用相應的hash算法得到key的hash值。將hash值的低位當作Hmap結構體中buckets數組的index，找到key所在的bucket。將hash的高8位存儲在了bucket的tophash中。注意，這里高8位不是用來當作key/value在bucket內部的offset的，而是作為一個主鍵，在查找時對tophash數組的每一項進行順序匹配的。先比較hash值高位與bucket的tophash[i]是否相等，如果相等則再比較bucket的第i個的key與所給的key是否相等。如果相等，則返回其對應的value，反之，在overflow buckets中按照上述方法繼續(xù)尋找。

整個hash的存儲如下圖所示(臨時先采用了XX同學畫的圖，這個圖有點問題)：

圖2.2 HMap的存儲結構

注意一個細節(jié)是Bucket中key/value的放置順序，是將keys放在一起，values放在一起，為什么不將key和對應的value放在一起呢？如果那么做，存儲結構將變成key1/value1/key2/value2… 設想如果是這樣的一個map[int64]int8，考慮到字節(jié)對齊，會浪費很多存儲空間。不得不說通過上述的一個小細節(jié)，可以看出Go在設計上的深思熟慮。

增量擴容

大家都知道哈希表表就是以空間換時間，訪問速度是直接跟填充因子相關的，所以當哈希表太滿之后就需要進行擴容。

如果擴容前的哈希表大小為2^B，擴容之后的大小為2^(B+1)，每次擴容都變?yōu)樵瓉泶笮〉膬杀?，哈希表大小始終為2的指數倍，則有(hash mod 2^B)等價于(hash & (2^B-1))。這樣可以簡化運算，避免了取余操作。

假設擴容之前容量為X，擴容之后容量為Y，對于某個哈希值hash，一般情況下(hash mod X)不等于(hash mod Y)，所以擴容之后要重新計算每一項在哈希表中的新位置。當hash表擴容之后，需要將那些舊的pair重新哈希到新的table上(源代碼中稱之為evacuate)， 這個工作并沒有在擴容之后一次性完成，而是逐步的完成（在insert和remove時每次搬移1-2個pair），Go語言使用的是增量擴容。

為什么會增量擴容呢？主要是縮短map容器的響應時間。假如我們直接將map用作某個響應實時性要求非常高的web應用存儲，如果不采用增量擴容，當map里面存儲的元素很多之后，擴容時系統(tǒng)就會卡往，導致較長一段時間內無法響應請求。不過增量擴容本質上還是將總的擴容時間分攤到了每一次哈希操作上面。

擴容會建立一個大小是原來2倍的新的表，將舊的bucket搬到新的表中之后，并不會將舊的bucket從oldbucket中刪除，而是加上一個已刪除的標記。

正是由于這個工作是逐漸完成的，這樣就會導致一部分數據在old table中，一部分在new table中， 所以對于hash table的insert, remove, lookup操作的處理邏輯產生影響。只有當所有的bucket都從舊表移到新表之后，才會將oldbucket釋放掉。

擴容的填充因子是多少呢？如果grow的太頻繁，會造成空間的利用率很低， 如果很久才grow，會形成很多的overflow buckets，查找的效率也會下降。 這個平衡點如何選取呢(在go中，這個平衡點是有一個宏控制的(#define LOAD 6.5), 它的意思是這樣的，如果table中元素的個數大于table中能容納的元素的個數， 那么就觸發(fā)一次grow動作。那么這個6.5是怎么得到的呢？原來這個值來源于作者的一個測試程序，遺憾的是沒能找到相關的源碼，不過作者給出了測試的結果：

        LOAD    %overflow  bytes/entry     hitprobe    missprobe
        4.00         2.13        20.77         3.00         4.00
        4.50         4.05        17.30         3.25         4.50
        5.00         6.85        14.77         3.50         5.00
        5.50        10.55        12.94         3.75         5.50
        6.00        15.27        11.67         4.00         6.00
        6.50        20.90        10.79         4.25         6.50
        7.00        27.14        10.15         4.50         7.00
        7.50        34.03         9.73         4.75         7.50
        8.00        41.10         9.40         5.00         8.00

 %overflow   = percentage of buckets which have an overflow bucket
 bytes/entry = overhead bytes used per key/value pair
 hitprobe    = # of entries to check when looking up a present key
 missprobe   = # of entries to check when looking up an absent key

可以看出作者取了一個相對適中的值。

查找過程

1. 根據key計算出hash值。
2. 如果存在old table, 首先在old table中查找，如果找到的bucket已經evacuated，轉到步驟3。 反之，返回其對應的value。
3. 在new table中查找對應的value。

這里一個細節(jié)需要注意一下。不認真看可能會以為低位用于定位bucket在數組的index，那么高位就是用于key/valule在bucket內部的offset。事實上高8位不是用作offset的，而是用于加快key的比較的。

do { //對每個桶b
    //依次比較桶內的每一項存放的tophash與所求的hash值高位是否相等
    for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {
        if(b->tophash[i] == top) { 
            k2 = IK(h, k);
            t->key->alg->equal(&eq, t->key->size, key, k2);
            if(eq) { //相等的情況下再去做key比較...
                *keyp = k2;
                return IV(h, v);
            }
        }
    }
    b = b->overflow; //b設置為它的下一下溢出鏈
} while(b != nil);

插入過程分析

1. 根據key算出hash值，進而得出對應的bucket。
2. 如果bucket在old table中，將其重新散列到new table中。
3. 在bucket中，查找空閑的位置，如果已經存在需要插入的key，更新其對應的value。
4. 根據table中元素的個數，判斷是否grow table。
5. 如果對應的bucket已經full，重新申請新的bucket作為overbucket。
6. 將key/value pair插入到bucket中。

這里也有幾個細節(jié)需要注意一下。

在擴容過程中，oldbucket是被凍結的，查找時會在oldbucket中查找，但不會在oldbucket中插入數據。如果在oldbucket是找到了相應的key，做法是將它遷移到新bucket后加入evalucated標記。并且還會額外的遷移另一個pair。

然后就是只要在某個bucket中找到第一個空位，就會將key/value插入到這個位置。也就是位置位于bucket前面的會覆蓋后面的(類似于存儲系統(tǒng)設計中做刪除時的常用的技巧之一，直接用新數據追加方式寫，新版本數據覆蓋老版本數據)。找到了相同的key或者找到第一個空位就可以結束遍歷了。不過這也意味著做刪除時必須完全的遍歷bucket所有溢出鏈，將所有的相同key數據都刪除。所以目前map的設計是為插入而優(yōu)化的，刪除效率會比插入低一些。

map設計中的性能優(yōu)化

讀完map源代碼發(fā)現作者還是做了很多設計上的選擇的。本人水平有限，談不上優(yōu)劣的點評，這里只是拿出來與讀者分享。

HMap中是Bucket的數組，而不是Bucket指針的數組。好的方面是可以一次分配較大內存，減少了分配次數，避免多次調用mallocgc。但相應的缺點，其一是可擴展哈希的算法并沒有發(fā)生作用，擴容時會造成對整個數組的值拷貝(如果實現上用Bucket指針的數組就是指針拷貝了，代價小很多)。其二是首個bucket與后面產生了不一致性。這個會使刪除邏輯變得復雜一點。比如刪除后面的溢出鏈可以直接刪除，而對于首個bucket，要等到evalucated完畢后，整個oldbucket刪除時進行。

沒有重用設freelist重用刪除的結點。作者把這個加了一個TODO的注釋，不過想了一下覺得這個做的意義不大。因為一方面，bucket大小并不一致，重用比較麻煩。另一方面，下層存儲已經做過內存池的實現了，所以這里不做重用也會在內存分配那一層被重用的，

bucket直接key/value和間接key/value優(yōu)化。這個優(yōu)化做得蠻好的。注意看代碼會發(fā)現，如果key或value小于128字節(jié)，則它們的值是直接使用的bucket作為存儲的。否則bucket中存儲的是指向實際key/value數據的指針，

bucket存8個key/value對。查找時進行順序比較。第一次發(fā)現高位居然不是用作offset，而是用于加快比較的。定位到bucket之后，居然是一個順序比較的查找過程。后面仔細想了想，覺得還行。由于bucket只有8個，順序比較下來也不算過分。仍然是O(1)只不過前面系數大一點點罷了。相當于hash到一個小范圍之后，在這個小范圍內順序查找。

插入刪除的優(yōu)化。前面已經提過了，插入只要找到相同的key或者第一個空位，bucket中如果存在一個以上的相同key，前面覆蓋后面的(只是如果，實際上不會發(fā)生)。而刪除就需要遍歷完所有bucket溢出鏈了。這樣map的設計就是為插入優(yōu)化的?？紤]到一般的應用場景，這個應該算是很合理的。

作者還列了另個2個TODO：將多個幾乎要empty的bucket合并；如果table中元素很少，考慮shrink table。(畢竟現在的實現只是單純的grow)。

links

• 上一節(jié): Go語言 slice介紹
• 下一節(jié): nil的語義