Go map實現原理
深入Go的Map使用和實現原理
go 中的 map 也是 hashmap，由哈和(bucket)數組組成，每個 bucket 可以存放若幹元素(默認8個)，當超過 8 個元素後，hmap會使用extra中的overflow指向新的 bucket 來拓展該bucket；
bucket 數組 tophash 數組 data字節數組 overflow 鏈表
哈希沖突後的數據結構：
overflow 表示溢出的意思
負載因子用於表示哈希沖突的情況 = 鍵數量 / bucket 的數量
哈希因子需要控制在合適的大小，超過闕值後需要 rehash
* 哈希因子過小，說明空間利用率低
* 哈希因子過大，說明沖突嚴重，存取效率低
每個 hash 表的實現對負載因子的容忍程度不同，redis 中負載因子為 1 時就會觸發 rehash，因為 redis 的每個 bucket 只能存儲壹個鍵值對。而 go 的能存儲 8 個，負載因子為 6.5；
4.1 擴容的前提條件
為保證訪問效率，當新元素要添加時，都會檢查是否需要擴容，擴容實際是空間換時間；
4.2 增量擴容
負載因子超過闕值後，新建壹個 buckets，長度為原來的2倍，舊 buckets 的數量逐漸搬遷至新的 buckets 中。
如果數據量較大，采取漸進式hash， 每次訪問 map 都會觸發壹次搬遷 ，每次搬遷2個鍵值對，搬遷完成後將會刪除 oldbuckets；
4.3 縮容
通過不斷地刪除，鍵值對集中在壹小部分地 bucket 中，overflow 中大部分是空的，經過重新組織後 bucket 的數量會減少，提高訪問效率；