映射 map

什么是 map

map 是由一組鍵值對(duì)組成的抽象數(shù)據(jù)結(jié)構(gòu)，并且鍵只會(huì)出現(xiàn)一次讼育。

map 通常是用哈希查找表（Hash table）或者搜索樹（Search tree）實(shí)現(xiàn)的。

哈希查找表用一個(gè)哈希函數(shù)將 key 分配到不同的桶（bucket饥瓷，也就是數(shù)組的不同 index）忧饭。這樣词裤，開銷主要在哈希函數(shù)的計(jì)算以及數(shù)組的常數(shù)訪問時(shí)間鳖宾。在很多場(chǎng)景下鼎文，哈希查找表的性能很高。

哈希查找表一般會(huì)存在“碰撞”的問題周偎，就是說不同的 key 被哈希到了同一個(gè) bucket蓉坎。一般有兩種應(yīng)對(duì)方法：鏈表法和開放地址法胡嘿。鏈表法將一個(gè) bucket 實(shí)現(xiàn)成一個(gè)鏈表衷敌，落在同一個(gè) bucket 中的 key 都會(huì)插入這個(gè)鏈表。開放地址法則是碰撞發(fā)生后助琐，通過一定的規(guī)律面氓，在數(shù)組的后面挑選“空位”侧但，用來放置新的 key。

搜索樹法一般采用自平衡搜索樹屁药，包括：AVL 樹酿箭，紅黑樹。自平衡搜索樹法的最差搜索效率是 O(logN)缔御，而哈希查找表最差是 O(N)耕突。當(dāng)然评架，哈希查找表的平均查找效率是 O(1)，如果哈希函數(shù)設(shè)計(jì)的很好上祈，最壞的情況基本不會(huì)出現(xiàn)登刺。

兩種實(shí)現(xiàn)方案還有一點(diǎn)區(qū)別嗡呼，遍歷自平衡搜索樹晤锥，返回的 key 序列一般是從小到大的順序序列矾瘾；而哈希查找表是亂序的。

Go 語言中的 map 使用哈希查找表實(shí)現(xiàn)的蛉迹，并且使用鏈表解決哈希沖突放妈。

底層原理

參考《深度解密Go語言之map》

map 內(nèi)存模型

在源碼中芜抒，表示 map 的結(jié)構(gòu)體是 hmap，它是 hashmap 的“縮寫”攘宙。

// A header for a Go map.
type hmap struct {
    // 元素個(gè)數(shù)蹭劈，調(diào)用 len(map) 時(shí)，直接返回此值
    count     int
    flags     uint8
    // buckets 的對(duì)數(shù) log_2
    B         uint8
    // overflow 的 bucket 近似數(shù)
    noverflow uint16
    // 計(jì)算 key 的哈希的時(shí)候會(huì)傳入哈希函數(shù)
    hash0     uint32
    // 指向 buckets 數(shù)組多矮，大小為 2^B塔逃，如果元素個(gè)數(shù)為0前酿，就為 nil
    buckets    unsafe.Pointer
    // 二倍擴(kuò)容的時(shí)候罢维，buckets 長(zhǎng)度會(huì)是 oldbuckets 的兩倍
    oldbuckets unsafe.Pointer
    // 指示擴(kuò)容進(jìn)度肺孵，小于此地址的 buckets 遷移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

buckets 指針指向大小為 2^B 的 bucket 數(shù)組颜阐，每個(gè) bucket 里存儲(chǔ)了 key 和 value凳怨。bucket 的結(jié)構(gòu)體名稱為 bmap，就是“桶”紫新，桶里面有 8 個(gè) cell芒率，最多裝 8 個(gè) key篙顺。

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

不同 key 之所以會(huì)落入同一個(gè)桶德玫，是因?yàn)樗麄兘?jīng)過哈希計(jì)算后，哈希結(jié)果屬于同一類材彪。在桶內(nèi)查刻，又會(huì)根據(jù) key 計(jì)算出來的哈希值的高 8 位來判斷 key 落入桶中的那個(gè)位置穗泵。

hmap 的內(nèi)存模型如下：

圖片

bmap 的內(nèi)存模型如下：

圖片

每個(gè) bucket 設(shè)計(jì)成最多只能放 8 個(gè) key-value 對(duì)佃延，如果有第 9 個(gè) key-value 落入當(dāng)前的 bucket，那就需要再構(gòu)建一個(gè) bucket 仔沿，通過 overflow 指針連接起來封锉。

注意到 key 和 value 是各自放在一起的膘螟，并不是 key/value/key/value/... 這樣的形式荆残。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段内斯，節(jié)省內(nèi)存空間。

哈希函數(shù)

map 的一個(gè)關(guān)鍵點(diǎn)在于潭苞，哈希函數(shù)的選擇备徐。在程序啟動(dòng)時(shí)蜜猾，會(huì)檢測(cè) cpu 是否支持 aes蹭睡，如果支持，則使用 aes hash脊串，否則使用 memhash琼锋。

hash 函數(shù)，有加密型和非加密型怖侦。加密型的一般用于加密數(shù)據(jù)匾寝、數(shù)字摘要等荷腊，典型代表就是 md5女仰、sha1董栽、sha256、aes256 這種；非加密型的一般就是查找擒抛。在 map 的應(yīng)用場(chǎng)景中补疑，用的是查找莲组。選擇 hash 函數(shù)主要考察的是兩點(diǎn)：性能锹杈、碰撞概率。

key 定位過程

key 經(jīng)過哈希計(jì)算后得到哈希值邪码，共 64 個(gè) bit 位闭专，計(jì)算它到底要落在哪個(gè)桶時(shí)，只會(huì)用到最后 B 個(gè) bit 位画髓。B 是 上文中 hmap 結(jié)構(gòu)體的一個(gè)字段雀扶。如果 B = 5愚墓，那么桶的數(shù)量昂勉，也就是 buckets 數(shù)組的長(zhǎng)度是 2^5 = 32岗照。

例如攒至，現(xiàn)在有一個(gè) key 經(jīng)過哈希函數(shù)計(jì)算后，得到的哈希結(jié)果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 個(gè) bit 位库菲，也就是 01010熙宇，值為 10烫止，也就是 10 號(hào)桶戳稽。這個(gè)操作實(shí)際上就是取余操作惊奇，但是取余開銷太大，所以代碼實(shí)現(xiàn)上用的位操作代替吨铸。

再用哈希值的高 8 位诞吱，找到此 key 在 bucket 中的位置房维，這是在尋找已有的 key咙俩。若桶內(nèi)沒有該 key，新加入的 key 會(huì)找到第一個(gè)空位膜蛔，放入皂股，若沒有空位命黔，需要在 bucket 后面掛上 overflow bucket呜呐，放入 overflow bucket。

bucket 編號(hào)就是桶編號(hào)悍募，當(dāng)兩個(gè)不同的 key 落在同一個(gè)桶中蘑辑，也就是發(fā)生了哈希沖突。沖突的解決手段是用鏈表法：在 bucket 中坠宴，從前往后找到第一個(gè)空位洋魂。這樣，在查找某個(gè) key 時(shí)啄踊，先找到對(duì)應(yīng)的桶，再去遍歷 bucket 中的 key颠通。

圖片

上圖中，假定 B = 5膀懈，所以 bucket 總數(shù)就是 2^5 = 32顿锰。首先計(jì)算出待查找 key 的哈希，使用低 5 位 00110启搂，找到對(duì)應(yīng)的 6 號(hào) bucket硼控，使用高 8 位 10010111，對(duì)應(yīng)十進(jìn)制 151胳赌，在 6 號(hào) bucket 中尋找 tophash 值（HOB hash）為 151 的 key牢撼，找到了 2 號(hào)槽位，再對(duì) 2 號(hào)槽位的 key 做哈希疑苫，如果與待查找 key 的哈希相等熏版，這樣整個(gè)查找過程就結(jié)束了纷责。

如果在 bucket 中沒找到，并且 overflow 不為空撼短，還要繼續(xù)去 overflow bucket 中尋找再膳，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket曲横。如果 hmap 中沒有此 key，那就會(huì)返回一個(gè) key 相應(yīng)類型的零值。

遍歷 bucket 和它所有的 overflow bucket十酣，相當(dāng)于遍歷一個(gè) bucket 鏈表馅闽。而里層循環(huán)就是遍歷這個(gè) bucket 里所有的 cell，或者說所有的槽位熙参。

擴(kuò)容

使用哈希表的目的就是要快速查找到目標(biāo) key艳吠，然而，隨著向 map 中添加的 key 越來越多尊惰，key 發(fā)生碰撞的概率也越來越大讲竿。bucket 中的 8 個(gè) cell 會(huì)被逐漸塞滿，查找弄屡、插入题禀、刪除 key 的效率也會(huì)越來越低。最理想的情況是很多 bucket膀捷，一個(gè) bucket 只裝一個(gè) key迈嘹，這樣，就能達(dá)到 O(1) 的效率全庸，但這樣空間消耗太大秀仲，用空間換時(shí)間的代價(jià)太高。

Go 語言采用一個(gè) bucket 里裝載 8 個(gè) key壶笼，定位到某個(gè) bucket 后神僵，還需要再定位到具體的 key，這實(shí)際上又用了時(shí)間換空間覆劈。當(dāng)然保礼，這樣做要有一個(gè)度，不然所有的 key 都落在了同一個(gè) bucket 里责语，直接退化成了鏈表炮障，各種操作的效率直接降為 O(n)。因此坤候，需要有一個(gè)指標(biāo)來衡量前面描述的情況胁赢，這就是裝載因子。Go 源碼里這樣定義裝載因子：

loadFactor := count / (2^B)

count 就是 map 的元素個(gè)數(shù)白筹，2^B 表示 bucket 數(shù)量智末。

再來說觸發(fā) map 擴(kuò)容的時(shí)機(jī)谅摄。在向 map 插入新 key 的時(shí)候，會(huì)進(jìn)行條件檢測(cè)吹害，符合下面這 2 個(gè)條件螟凭，就會(huì)觸發(fā)擴(kuò)容：

1. 裝載因子超過閾值，源碼里定義的閾值是 6.5它呀。
2. overflow 的 bucket 數(shù)量過多：當(dāng) B 小于 15螺男，也就是 bucket 總數(shù) 2^B 小于 2^15 時(shí)，如果 overflow 的 bucket 數(shù)量超過 2^B纵穿；當(dāng) B >= 15下隧，也就是 bucket 總數(shù) 2^B 大于等于 2^15，如果 overflow 的 bucket 數(shù)量超過 2^15谓媒。

第 1 點(diǎn)：我們知道淆院，每個(gè) bucket 有 8 個(gè)空位，在沒有溢出句惯，且所有的桶都裝滿了的情況下土辩，裝載因子算出來的結(jié)果是 8。因此當(dāng)裝載因子超過 6.5 時(shí)抢野，表明很多 bucket 都快要裝滿了拷淘，查找效率和插入效率都變低了。在這個(gè)時(shí)候進(jìn)行擴(kuò)容是有必要的指孤。

第 2 點(diǎn)：是對(duì)第 1 點(diǎn)的補(bǔ)充启涯。就是說在裝載因子比較小的情況下，這時(shí)候 map 的查找和插入效率也很低恃轩，而第 1 點(diǎn)識(shí)別不出來這種情況结洼。表面現(xiàn)象就是計(jì)算裝載因子的分子比較小，即 map 里元素總數(shù)少叉跛，但是 bucket 數(shù)量多（真實(shí)分配的 bucket 數(shù)量多松忍，包括大量的 overflow bucket）。

造成這種情況的原因是不停地插入筷厘、刪除元素挽铁。先插入很多元素，導(dǎo)致創(chuàng)建了很多 bucket敞掘，但是裝載因子達(dá)不到第 1 點(diǎn)的臨界值，未觸發(fā)擴(kuò)容來緩解這種情況楣铁。之后玖雁，刪除元素降低元素總數(shù)量，再插入很多元素盖腕，導(dǎo)致創(chuàng)建很多的 overflow bucket赫冬，但就是不會(huì)觸犯第 1 點(diǎn)的規(guī)定浓镜。overflow bucket 數(shù)量太多，導(dǎo)致 key 會(huì)很分散劲厌，查找插入效率低得嚇人膛薛，因此有第 2 點(diǎn)規(guī)定。這就像是一座空城补鼻，房子很多哄啄，但是住戶很少，都分散了风范，找起人來很困難咨跌。

對(duì)于命中條件 1，2 的限制硼婿，都會(huì)發(fā)生擴(kuò)容锌半。但是擴(kuò)容的策略并不相同，畢竟兩種條件應(yīng)對(duì)的場(chǎng)景不同寇漫。

對(duì)于條件 1刊殉，元素太多，而 bucket 數(shù)量太少州胳，很簡(jiǎn)單：將 B 加 1记焊，bucket 最大數(shù)量（2^B）直接變成原來 bucket 數(shù)量的 2 倍。于是陋葡，就有新老 bucket 了亚亲。注意，這時(shí)候元素都在老 bucket 里腐缤，還沒遷移到新的 bucket 來捌归，只是新 bucket 最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量的 2 倍。

對(duì)于條件 2岭粤，其實(shí)元素沒那么多惜索，但是 overflow bucket 數(shù)特別多，說明很多 bucket 都沒裝滿剃浇。解決辦法就是開辟一個(gè)新 bucket 空間巾兆，將老 bucket 中的元素移動(dòng)到新 bucket，使得同一個(gè) bucket 中的 key 排列地更緊密虎囚。這樣角塑，原來在 overflow bucket 中的 key 可以移動(dòng)到 bucket 中來。結(jié)果是節(jié)省空間淘讥，提高 bucket 利用率圃伶，map 的查找和插入效率自然就會(huì)提升。

再來看擴(kuò)容的具體實(shí)現(xiàn)。由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址窒朋，如果有大量的 key/value 需要搬遷搀罢，會(huì)非常影響性能。因此 Go map 的擴(kuò)容采取了一種稱為“漸進(jìn)式”的方式侥猩，原有的 key 并不會(huì)一次性搬遷完畢榔至，每次最多只會(huì)搬遷 2 個(gè) bucket。所以當(dāng)檢測(cè)符合擴(kuò)容條件欺劳，只是分配新的 buckets唧取，并將老的 buckets 掛到了 oldbuckets 字段上。在后續(xù)每次插入杰标、修改或刪除操作時(shí)兵怯，在執(zhí)行具體操作前，都會(huì)嘗試進(jìn)行搬遷腔剂，即檢查如果 oldbuckets 不為空媒区，說明還沒有搬遷完畢，就開始搬掸犬，然后再執(zhí)行插入袜漩、修改或刪除操作。

在執(zhí)行搬遷時(shí)湾碎，遍歷此 bucket 的所有的 cell宙攻，將有值的 cell copy 到新的地方。bucket 還會(huì)鏈接 overflow bucket介褥，它們同樣需要搬遷座掘。

對(duì)于條件 1，要重新計(jì)算 key 的哈希柔滔，才能決定它到底落在哪個(gè) bucket溢陪。例如，原來 B = 5睛廊，計(jì)算出 key 的哈希后形真，只用看它的低 5 位，就能決定它落在哪個(gè) bucket超全。擴(kuò)容后咆霜，B 變成了 6，因此需要多看一位嘶朱，它的低 6 位決定 key 落在哪個(gè) bucket蛾坯。這稱為 rehash。

對(duì)于條件 2疏遏，從老的 buckets 搬遷到新的 buckets偿衰，由于 bucktes 數(shù)量不變挂疆，因此可以按序號(hào)來搬，比如原來在 0 號(hào) bucktes下翎，到新的地方后，仍然放在 0 號(hào) buckets宝当。

因此视事，某個(gè) key 在搬遷前后 bucket 序號(hào)可能和原來相等，也可能是相比原來加上 2^B（原來的 B 值）庆揩，取決于 hash 值 第 6 bit 位是 0 還是 1俐东。

這也解釋了為什么遍歷 map 是無序的。因?yàn)?map 在擴(kuò)容后订晌，會(huì)發(fā)生 key 的搬遷虏辫，而遍歷的過程，就是按順序遍歷 bucket锈拨，同時(shí)按順序遍歷 bucket 中的 key砌庄。

當(dāng)然，如果我就一個(gè)硬編碼的 map奕枢，我也不會(huì)向 map 進(jìn)行插入刪除的操作娄昆，按理說每次遍歷這樣的 map 都會(huì)返回一個(gè)固定順序的 key/value 序列。但是 Go 杜絕了這種做法缝彬，因?yàn)檫@樣會(huì)給新手程序員帶來誤解萌焰，以為這是一定會(huì)發(fā)生的事情，在某些情況下谷浅，可能會(huì)釀成大錯(cuò)扒俯。所以 Go 在我們?cè)诒闅v map 時(shí)，并不是固定地從 0 號(hào) bucket 開始遍歷一疯，每次都是從一個(gè)隨機(jī)值序號(hào)的 bucket 開始遍歷撼玄，并且是從這個(gè) bucket 的一個(gè)隨機(jī)序號(hào)的 cell 開始遍歷。這樣违施，即使你是一個(gè)寫死的 map互纯，僅僅只是遍歷它，也不太可能會(huì)返回一個(gè)固定序列的 key/value 對(duì)了磕蒲×袅剩“迭代 map 的結(jié)果是無序的”這個(gè)特性是從 go 1.0 開始加入的。

map 的遍歷

因?yàn)橛袛U(kuò)容的過程辣往，而擴(kuò)容不是一個(gè)原子的操作兔院，所以在很長(zhǎng)時(shí)間里，map 的狀態(tài)都是處于一個(gè)中間態(tài)：有些 bucket 已經(jīng)搬遷到新家站削，而有些 bucket 還待在老地方坊萝。因此，map 的遍歷并不是簡(jiǎn)單地遍歷所有的 bucket 以及它后面掛的 overflow bucket，然后挨個(gè)遍歷 bucket 中的所有 cell十偶，從有 key 的 cell 中取出 key 和 value菩鲜。

遍歷如果發(fā)生在擴(kuò)容的過程中，就會(huì)涉及到遍歷新老 bucket 的過程惦积，這時(shí)需判斷當(dāng)前 bucket 是否已經(jīng)搬遷接校。如已搬遷，則遍歷新 bucket 里的數(shù)據(jù)狮崩。否則蛛勉，遍歷舊 bucket 里在擴(kuò)容裂變后將會(huì)分配到新 bucket 中的數(shù)據(jù)。

所以 map 遍歷的核心在于理解 2 倍擴(kuò)容時(shí)睦柴，老 bucket 會(huì)分裂到 2 個(gè)新 bucket 中去诽凌。而遍歷操作，會(huì)按照新 bucket 的序號(hào)順序進(jìn)行坦敌，碰到老 bucket 未搬遷的情況時(shí)侣诵，要在老 bucket 中找到將來要搬遷到新 bucket 來的 key。

map 的賦值

關(guān)鍵在于定位 key 要安置的地址恬试。先對(duì) key 做哈希定位到所在 bucket窝趣，然后找到 key 安置在整個(gè) bucket 中的位置。在找 key 在整個(gè) bucket 中的位置時(shí)训柴，如果遍歷 bucket 沒有找到此 key哑舒，意味著是插入新 key，那 key 的安置地址就是第一次發(fā)現(xiàn)的“空位”幻馁，如果這個(gè) bucket 的 key 都已經(jīng)放置滿了洗鸵，需要在 bucket 后面掛上 overflow bucket。如果遍歷 bucket 找到了此 key仗嗦，意味著是更新舊 key膘滨，那 key 的安置地址就是 key 現(xiàn)有位置。

map 的刪除

核心還是找到 key 的具體位置稀拐。找到對(duì)應(yīng)位置后火邓，對(duì) key 和 value 進(jìn)行“清零”操作：

創(chuàng)建與初始化

make 函數(shù)創(chuàng)建

m := make(map[keyType]valueType)

map 的 key 必須是可以使用 == 運(yùn)算符做比較的類型，map 的 value 沒有類型限制德撬。

字面量創(chuàng)建

month := map[string]int{"January":1,"February":2,"March":3}

map 創(chuàng)建的底層原理

實(shí)際底層調(diào)用的是 makemap 函數(shù)铲咨，主要做的工作就是初始化 hmap 結(jié)構(gòu)體的各種字段，例如計(jì)算 B 的大小蜓洪，設(shè)置哈希種子 hash0 等纤勒。

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap

注意，這個(gè)函數(shù)返回的結(jié)果是 *hmap隆檀，是一個(gè)指針摇天，而創(chuàng)建切片底層調(diào)用的 makeslice 函數(shù)返回的是 slice 結(jié)構(gòu)體：

func makeslice(et *_type, len, cap int) slice

slice 的結(jié)構(gòu)體定義粹湃，結(jié)構(gòu)體內(nèi)部包含底層的數(shù)據(jù)指針。

// runtime/slice.go
type slice struct {
    array unsafe.Pointer // 元素指針
    len   int   // 長(zhǎng)度
    cap   int   // 容量
}

makemap 和 makeslice 的區(qū)別泉坐，帶來一個(gè)不同點(diǎn)：當(dāng) map 和 slice 作為函數(shù)參數(shù)時(shí)为鳄，在函數(shù)參數(shù)內(nèi)部對(duì) map 的操作會(huì)影響 map 自身，而對(duì) slice 卻不會(huì)坚冀。原因是一個(gè)是指針（*hmap）济赎，一個(gè)是結(jié)構(gòu)體（slice）。

nil map 和空 map

nil map

var month map[string]int    // 聲明了一個(gè) nil map
fmt.Println(month == nil)   // 輸出：true

map 的零值是 nil记某。

nil map 是不能存取鍵值對(duì)的，會(huì)報(bào) panic 錯(cuò)誤构捡。

空 map

// month := make(map[string]int)    // make 函數(shù)創(chuàng)建空 map
month := map[string]int{}       // 字面量創(chuàng)建空 map
fmt.Println(month)              // 輸出：map[]

map 的兩種 get 操作

Go 語言中讀取 map 有兩種語法液南。

value := map[key]   // 當(dāng)key不存在，返回value類型的零值

value, ok := map[key]   // 增加bool型變量返回勾徽，提示key是否存在

這兩種語法的實(shí)現(xiàn)是編譯器在背后做的工作：分析代碼后滑凉，將兩種語法對(duì)應(yīng)到底層兩個(gè)不同的函數(shù)。

// src/runtime/hashmap.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

根據(jù) key 的不同類型喘帚，編譯器還會(huì)將查找畅姊、插入、刪除的函數(shù)用更具體的函數(shù)替換吹由，以優(yōu)化效率若未。

其他

• 使用 len 函數(shù)返回 map 中鍵值對(duì)的數(shù)量。
• 可以通過內(nèi)建函數(shù)delete(map, key) 刪除鍵值對(duì)倾鲫。當(dāng) map 不存在的相應(yīng)的 key 時(shí)粗合，不報(bào)錯(cuò)，相當(dāng)于沒操作乌昔。
• 要得到一個(gè)不共享底層數(shù)據(jù)的 map 副本隙疚，可以創(chuàng)建新的空 map，迭代舊 map 給新 map 賦值磕道。
• map 不是并發(fā)安全的供屉，并發(fā)操作會(huì)導(dǎo)致 panic，要加上讀寫鎖溺蕉。也可以使用 sync 包下并發(fā)安全的 map伶丐。
• 定義 map 時(shí)，當(dāng) value 是自定義結(jié)構(gòu)體時(shí)：
  1. 不推薦map[string]Student焙贷，map 的 value Student 的屬性是不可以修改的撵割。
  2. 推薦map[string]*Student，map 的 value Student 的屬性是可以修改的辙芍，且效率高啡彬。
• map 的遍歷是亂序的羹与，要順序輸出，可使用 slice 額外保存順序的 key庶灿，再通過 slice 去讀取纵搁。

并發(fā)安全 map

sync 包下的 map 是并發(fā)安全的。此外往踢，可以自定義加鎖的map結(jié)構(gòu)腾誉。

《談Go語言中并發(fā)Map的使用》

集合 Set

Go 語言里面沒有集合這種數(shù)據(jù)結(jié)構(gòu)【唬可以使用 map 實(shí)現(xiàn)集合 Set利职，map 中的 key 都是唯一的。

type Set struct {
    m map[string]bool
}

func NewSet() Set {
    m := make(map[string]bool)
    return Set{m: m}
}

func (s *Set) Contains(val string) bool {
    _, ok := s.m[val]
    return ok
}

func (s *Set) Add(val string) {
    s.m[val] = true
}

func (s *Set) Remove(val string) {
    delete(s.m, val)
}

使用 map 作為集合的底層數(shù)據(jù)結(jié)構(gòu)的好處在于瘦癌，map 基于 hash 表實(shí)現(xiàn)猪贪，鍵值查找效率高，還可以少寫很多代碼讯私。