為什麼unordered_map源碼中的need_rehash函數只是將桶容量擴到下一個最小的素數？

剛剛看stl中unordered_map的源碼里need_rehash這部分。它採用的方式是如果發現桶個數&<最大條目數/最大裝載因子就擴容到滿足條件的最小的素數，並進行一次rehash。

但我看java和c#中hashmap中就是直接將桶個數擴容到原來的二倍。想問一下為什麼c++ stl中要這樣設計呢?感覺這樣比直接擴容二倍要多rehash很多次。謝謝

你看的是哪一個版本的 unordered_map？

gcc 的做法是按 growth_factor (=2) 來擴容，並非「只是將桶容量擴到下一個最小的素數」。實際上 gcc 選的 buckets 數比「直接將桶個數擴容到原來的二倍」更大，「這樣比直接擴容二倍要多rehash很多次」是你理解錯了。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/src/c%2B%2B11/hashtable_c%2B%2B0x.cc#L104

再次強調，不存在「stl中unordered_map的源碼」，只存在「某個實現的STL中xxxe的源碼」。你不說哪個實現，就跟什麼都沒說一樣。

MSVC的STL實現來自於Dinkumware，裡面的unordered並非最佳，尤其是初始的時候。gcc的libstdc++是按照兩倍來長。這就已經有不同的特性了。

考慮到隨機插入本來就要移動很多東西，如果內部實現是一個數組的話，長遠看來，擴容兩倍刀擴容到下一個素數的區別是很小的。但是如果不是一個數組，擴容太大就會做很多多餘的事情，allocate很多個不連續空間，以後還要反覆擦洗。

hash table的大小是素數時碰撞的概率小（有證明）。若直接擴大為兩倍反而可能性能惡化。

另外隨著size變大，素數的密度會下降得足夠小，也不至於反覆擴容。

（非嚴格）證明參考：

大意:

相當多情況下（包括Java），人們生成hash是用公式（其中k是一個提前選定的常數）生成一個integer：

hashVal = (first needHashVal) + k * (second needHashVal) + k^2 * (third needHashVal) + ...


比如Java中對

class Foo{
int a;
int b;
int c;
}


的一個instance計算 hashValue = a + k * b + k^2 * c

接下來 hashValue % bucketSize來分配位置。

根據實驗+經驗，若是k和bucketSize互質，則衝突概率最小，為1/bucketSize。若是有一個公約數n，則衝突概率變為n/bucketSize。(n&>=2)

理論上互質就可以，但是因為k的選擇和bucketSize的選擇是一前一後相互獨立的。於是為了保險起見選質數最好。

題主是不是記反了？

我怎麼記得是C#的實現中，預先存了一張素數表，然後擴容按素數表來擴的呢？