Go中的map在底層是用哈希表實(shí)現(xiàn)的,你可以在 $GOROOT/src/pkg/runtime/hashmap.goc 找到它的實(shí)現(xiàn)。
哈希表的數(shù)據(jù)結(jié)構(gòu)中一些關(guān)鍵的域如下所示:
struct Hmap
{
uint8 B; // 可以容納2^B個(gè)項(xiàng)
uint16 bucketsize; // 每個(gè)桶的大小
byte *buckets; // 2^B個(gè)Buckets的數(shù)組
byte *oldbuckets; // 前一個(gè)buckets,只有當(dāng)正在擴(kuò)容時(shí)才不為空
};
上面給出的結(jié)構(gòu)體只是Hmap的部分的域。需要注意到的是,這里直接使用的是Bucket的數(shù)組,而不是Bucket*指針的數(shù)組。這意味著,第一個(gè)Bucket和后面溢出鏈的Bucket分配有些不同。第一個(gè)Bucket是用的一段連續(xù)的內(nèi)存空間,而后面溢出鏈的Bucket的空間是使用mallocgc分配的。
這個(gè)hash結(jié)構(gòu)使用的是一個(gè)可擴(kuò)展哈希的算法,由hash值mod當(dāng)前hash表大小決定某一個(gè)值屬于哪個(gè)桶,而hash表大小是2的指數(shù),即上面結(jié)構(gòu)體中的2^B。每次擴(kuò)容,會(huì)增大到上次大小的兩倍。結(jié)構(gòu)體中有一個(gè)buckets和一個(gè)oldbuckets是用來(lái)實(shí)現(xiàn)增量擴(kuò)容的。正常情況下直接使用buckets,而oldbuckets為空。如果當(dāng)前哈希表正在擴(kuò)容中,則oldbuckets不為空,并且buckets大小是oldbuckets大小的兩倍。
具體的Bucket結(jié)構(gòu)如下所示:
struct Bucket
{
uint8 tophash[BUCKETSIZE]; // hash值的高8位....低位從bucket的array定位到bucket
Bucket *overflow; // 溢出桶鏈表,如果有
byte data[1]; // BUCKETSIZE keys followed by BUCKETSIZE values
};
其中BUCKETSIZE是用宏定義的8,每個(gè)bucket中存放最多8個(gè)key/value對(duì), 如果多于8個(gè),那么會(huì)申請(qǐng)一個(gè)新的bucket,并將它與之前的bucket鏈起來(lái)。
按key的類(lèi)型采用相應(yīng)的hash算法得到key的hash值。將hash值的低位當(dāng)作Hmap結(jié)構(gòu)體中buckets數(shù)組的index,找到key所在的bucket。將hash的高8位存儲(chǔ)在了bucket的tophash中。注意,這里高8位不是用來(lái)當(dāng)作key/value在bucket內(nèi)部的offset的,而是作為一個(gè)主鍵,在查找時(shí)對(duì)tophash數(shù)組的每一項(xiàng)進(jìn)行順序匹配的。先比較hash值高位與bucket的tophash[i]是否相等,如果相等則再比較bucket的第i個(gè)的key與所給的key是否相等。如果相等,則返回其對(duì)應(yīng)的value,反之,在overflow buckets中按照上述方法繼續(xù)尋找。
整個(gè)hash的存儲(chǔ)如下圖所示(臨時(shí)先采用了XX同學(xué)畫(huà)的圖,這個(gè)圖有點(diǎn)問(wèn)題):
圖2.2 HMap的存儲(chǔ)結(jié)構(gòu)
注意一個(gè)細(xì)節(jié)是Bucket中key/value的放置順序,是將keys放在一起,values放在一起,為什么不將key和對(duì)應(yīng)的value放在一起呢?如果那么做,存儲(chǔ)結(jié)構(gòu)將變成key1/value1/key2/value2… 設(shè)想如果是這樣的一個(gè)map[int64]int8,考慮到字節(jié)對(duì)齊,會(huì)浪費(fèi)很多存儲(chǔ)空間。不得不說(shuō)通過(guò)上述的一個(gè)小細(xì)節(jié),可以看出Go在設(shè)計(jì)上的深思熟慮。
大家都知道哈希表表就是以空間換時(shí)間,訪問(wèn)速度是直接跟填充因子相關(guān)的,所以當(dāng)哈希表太滿(mǎn)之后就需要進(jìn)行擴(kuò)容。
如果擴(kuò)容前的哈希表大小為2^B,擴(kuò)容之后的大小為2^(B+1),每次擴(kuò)容都變?yōu)樵瓉?lái)大小的兩倍,哈希表大小始終為2的指數(shù)倍,則有(hash mod 2^B)等價(jià)于(hash & (2^B-1))。這樣可以簡(jiǎn)化運(yùn)算,避免了取余操作。
假設(shè)擴(kuò)容之前容量為X,擴(kuò)容之后容量為Y,對(duì)于某個(gè)哈希值hash,一般情況下(hash mod X)不等于(hash mod Y),所以擴(kuò)容之后要重新計(jì)算每一項(xiàng)在哈希表中的新位置。當(dāng)hash表擴(kuò)容之后,需要將那些舊的pair重新哈希到新的table上(源代碼中稱(chēng)之為evacuate), 這個(gè)工作并沒(méi)有在擴(kuò)容之后一次性完成,而是逐步的完成(在insert和remove時(shí)每次搬移1-2個(gè)pair),Go語(yǔ)言使用的是增量擴(kuò)容。
為什么會(huì)增量擴(kuò)容呢?主要是縮短map容器的響應(yīng)時(shí)間。假如我們直接將map用作某個(gè)響應(yīng)實(shí)時(shí)性要求非常高的web應(yīng)用存儲(chǔ),如果不采用增量擴(kuò)容,當(dāng)map里面存儲(chǔ)的元素很多之后,擴(kuò)容時(shí)系統(tǒng)就會(huì)卡往,導(dǎo)致較長(zhǎng)一段時(shí)間內(nèi)無(wú)法響應(yīng)請(qǐng)求。不過(guò)增量擴(kuò)容本質(zhì)上還是將總的擴(kuò)容時(shí)間分?jǐn)偟搅嗣恳淮喂2僮魃厦妗?/p>
擴(kuò)容會(huì)建立一個(gè)大小是原來(lái)2倍的新的表,將舊的bucket搬到新的表中之后,并不會(huì)將舊的bucket從oldbucket中刪除,而是加上一個(gè)已刪除的標(biāo)記。
正是由于這個(gè)工作是逐漸完成的,這樣就會(huì)導(dǎo)致一部分?jǐn)?shù)據(jù)在old table中,一部分在new table中, 所以對(duì)于hash table的insert, remove, lookup操作的處理邏輯產(chǎn)生影響。只有當(dāng)所有的bucket都從舊表移到新表之后,才會(huì)將oldbucket釋放掉。
擴(kuò)容的填充因子是多少呢?如果grow的太頻繁,會(huì)造成空間的利用率很低, 如果很久才grow,會(huì)形成很多的overflow buckets,查找的效率也會(huì)下降。 這個(gè)平衡點(diǎn)如何選取呢(在go中,這個(gè)平衡點(diǎn)是有一個(gè)宏控制的(#define LOAD 6.5), 它的意思是這樣的,如果table中元素的個(gè)數(shù)大于table中能容納的元素的個(gè)數(shù), 那么就觸發(fā)一次grow動(dòng)作。那么這個(gè)6.5是怎么得到的呢?原來(lái)這個(gè)值來(lái)源于作者的一個(gè)測(cè)試程序,遺憾的是沒(méi)能找到相關(guān)的源碼,不過(guò)作者給出了測(cè)試的結(jié)果:
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
可以看出作者取了一個(gè)相對(duì)適中的值。
這里一個(gè)細(xì)節(jié)需要注意一下。不認(rèn)真看可能會(huì)以為低位用于定位bucket在數(shù)組的index,那么高位就是用于key/valule在bucket內(nèi)部的offset。事實(shí)上高8位不是用作offset的,而是用于加快key的比較的。
do { //對(duì)每個(gè)桶b
//依次比較桶內(nèi)的每一項(xiàng)存放的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設(shè)置為它的下一下溢出鏈
} while(b != nil);
這里也有幾個(gè)細(xì)節(jié)需要注意一下。
在擴(kuò)容過(guò)程中,oldbucket是被凍結(jié)的,查找時(shí)會(huì)在oldbucket中查找,但不會(huì)在oldbucket中插入數(shù)據(jù)。如果在oldbucket是找到了相應(yīng)的key,做法是將它遷移到新bucket后加入evalucated標(biāo)記。并且還會(huì)額外的遷移另一個(gè)pair。
然后就是只要在某個(gè)bucket中找到第一個(gè)空位,就會(huì)將key/value插入到這個(gè)位置。也就是位置位于bucket前面的會(huì)覆蓋后面的(類(lèi)似于存儲(chǔ)系統(tǒng)設(shè)計(jì)中做刪除時(shí)的常用的技巧之一,直接用新數(shù)據(jù)追加方式寫(xiě),新版本數(shù)據(jù)覆蓋老版本數(shù)據(jù))。找到了相同的key或者找到第一個(gè)空位就可以結(jié)束遍歷了。不過(guò)這也意味著做刪除時(shí)必須完全的遍歷bucket所有溢出鏈,將所有的相同key數(shù)據(jù)都刪除。所以目前map的設(shè)計(jì)是為插入而優(yōu)化的,刪除效率會(huì)比插入低一些。
讀完map源代碼發(fā)現(xiàn)作者還是做了很多設(shè)計(jì)上的選擇的。本人水平有限,談不上優(yōu)劣的點(diǎn)評(píng),這里只是拿出來(lái)與讀者分享。
HMap中是Bucket的數(shù)組,而不是Bucket指針的數(shù)組。好的方面是可以一次分配較大內(nèi)存,減少了分配次數(shù),避免多次調(diào)用mallocgc。但相應(yīng)的缺點(diǎn),其一是可擴(kuò)展哈希的算法并沒(méi)有發(fā)生作用,擴(kuò)容時(shí)會(huì)造成對(duì)整個(gè)數(shù)組的值拷貝(如果實(shí)現(xiàn)上用Bucket指針的數(shù)組就是指針拷貝了,代價(jià)小很多)。其二是首個(gè)bucket與后面產(chǎn)生了不一致性。這個(gè)會(huì)使刪除邏輯變得復(fù)雜一點(diǎn)。比如刪除后面的溢出鏈可以直接刪除,而對(duì)于首個(gè)bucket,要等到evalucated完畢后,整個(gè)oldbucket刪除時(shí)進(jìn)行。
沒(méi)有重用設(shè)freelist重用刪除的結(jié)點(diǎn)。作者把這個(gè)加了一個(gè)TODO的注釋?zhuān)贿^(guò)想了一下覺(jué)得這個(gè)做的意義不大。因?yàn)橐环矫?,bucket大小并不一致,重用比較麻煩。另一方面,下層存儲(chǔ)已經(jīng)做過(guò)內(nèi)存池的實(shí)現(xiàn)了,所以這里不做重用也會(huì)在內(nèi)存分配那一層被重用的,
bucket直接key/value和間接key/value優(yōu)化。這個(gè)優(yōu)化做得蠻好的。注意看代碼會(huì)發(fā)現(xiàn),如果key或value小于128字節(jié),則它們的值是直接使用的bucket作為存儲(chǔ)的。否則bucket中存儲(chǔ)的是指向?qū)嶋Hkey/value數(shù)據(jù)的指針,
bucket存8個(gè)key/value對(duì)。查找時(shí)進(jìn)行順序比較。第一次發(fā)現(xiàn)高位居然不是用作offset,而是用于加快比較的。定位到bucket之后,居然是一個(gè)順序比較的查找過(guò)程。后面仔細(xì)想了想,覺(jué)得還行。由于bucket只有8個(gè),順序比較下來(lái)也不算過(guò)分。仍然是O(1)只不過(guò)前面系數(shù)大一點(diǎn)點(diǎn)罷了。相當(dāng)于hash到一個(gè)小范圍之后,在這個(gè)小范圍內(nèi)順序查找。
插入刪除的優(yōu)化。前面已經(jīng)提過(guò)了,插入只要找到相同的key或者第一個(gè)空位,bucket中如果存在一個(gè)以上的相同key,前面覆蓋后面的(只是如果,實(shí)際上不會(huì)發(fā)生)。而刪除就需要遍歷完所有bucket溢出鏈了。這樣map的設(shè)計(jì)就是為插入優(yōu)化的??紤]到一般的應(yīng)用場(chǎng)景,這個(gè)應(yīng)該算是很合理的。
作者還列了另個(gè)2個(gè)TODO:將多個(gè)幾乎要empty的bucket合并;如果table中元素很少,考慮shrink table。(畢竟現(xiàn)在的實(shí)現(xiàn)只是單純的grow)。
更多建議: