底層數據結構-哈希表

go語言map的底層數據結構是哈希表：通過哈希表來存儲鍵值對，通過hash函數把鍵值對散列到一個個桶(bucket)中。

什么是哈希表？

• 在順序結構以及平衡樹中，元素與其的存儲位置之間沒有對應關系，因此查找一個元素時，必須進行多次比較。所以順序查找的時間復雜度為O(N)，而平衡樹中則為樹的高度O(log2N)。
• 為了減少搜素時元素比較的次數，是否有一種方法可以不經過任何比較，通過元素的存儲位置與它的關鍵碼以O(1)的時間復雜度直接找到該元素呢？
• 哈希表就是通過某種函數(hash)來使元素的存儲位置和其元素值之間建立一一映射的關系，那么就可以通過這種關系快速找到該元素。(數組就是一種簡單的哈希表)

如何處理哈希沖突？

• 當兩個或多個健具有相同的哈希值，即為出現了哈希沖突，它們會被存放在同一個桶中。go采用拉鏈法來解決哈希沖突的問題，即在同一個桶內部通過鏈接(鏈表)存儲所有沖突的鍵值對。
• 不過拉鏈法在當哈希沖突出現的次數相當頻繁時，會將常數級的時間復雜度上升甚至到線性級。加載因子的出現就是為了避免過多的哈希沖突導致哈希表的退化。

無序性

• 由于go語言的map是通過哈希表來實現的，由于哈希函數的特性，是無法依據一定的順序來存儲的。因此go的map是無序的。

map的擴容機制

在哈希表中，當元素達到一定的數量(超過加載因子設定的比例)，為了保持操作的效率，需要對哈希表進行擴容。擴容通常需要創建一個更大的哈希表，并將現有元素重新映射到新表中。

底層實現

type hmap struct {count     int    // 元素的個數B         uint8  // buckets 數組的長度就是 2^B 個overflow uint16 // 溢出桶的數量buckets    unsafe.Pointer // 2^B個桶對應的數組指針oldbuckets unsafe.Pointer  // 發生擴容時，記錄擴容前的buckets數組指針extra *mapextra //用于保存溢出桶的地址
}type mapextra struct {overflow    *[]*bmapoldoverflow *[]*bmapnextOverflow *bmap
}type bmap struct {tophash [bucketCnt]uint8
}//在編譯期間會產生新的結構體
type bmap struct {tophash [8]uint8 //存儲哈希值的高8位data    byte[1]  //key value數據:key/key/key/.../value/value/value...overflow *bmap   //溢出bucket的地址
}

在go的map實現中，它的底層結構體是hmap，hmap里維護著若干個bucket數組 (即桶數組)。每個桶中保存了8個鍵值對，如果8個滿了，又來了一個kv到了這個桶中，會使用overflow連接下一個桶，即桶溢出。

• 對于哈希沖突：當兩個不同的key落到了同一個桶中就是發生了哈希沖突，則會采用拉鏈法，從前往后找一個空位進行插入。如果桶滿了，當前桶就會連接到下一個溢出桶。

擴容基本步驟

1. 觸發擴容：
   • 當向map中添加新元素時，如果元素數量超過了當前哈希表容量和加載因子的乘積，就會觸發擴容。加載因子是一個決定性能與內存使用之間的閾值，防止哈希表的退化。
2. 分配新表
   • go在運行是會創建一個新的哈希表，其容量為原來的兩倍。這樣做可以減少再次擴容的可能，并提供足夠的空間來避免過多的哈希沖突。
3. 數據遷移
   • 將舊哈希表中的現有元素遷移到新表中。每個元素的哈希中將根據新表的大小容量重新計算，來確定它們在新表的位置。
   • 當map非常大的情況下，每次遷移所有的元素，會出現長時間的暫停。在go1.8版本之后，這個步驟是漸進式的：每次向map`添加新元素或查找時，都會遷移一小部分元素，避免長時間的暫停。
4. 更新引用
   • 當所有元素都遷移到新的哈希表中后，原來的哈希表將會被丟棄，map的內部引用將指向新表。

總結

1. 要提供合適的初始容量。
   由于每次擴容時，需要重新計算所有元素的哈希值并將它們分配到新的桶中，這是一個相當花時間的操作。因此，如果我們事先知道map大約會存儲多少數據，可以實現在創建map時通過提供合適的初始容量來減少擴容次數，從而提高map的性能:
   myMap := make(map[string]int, initialCapacity)