無序容器桶的大小散列函數？

Question

爲了將一個元素放入一個無序集中，我們計算它的哈希值並將其放到相應的桶中。然而，我們通常比散列函數的值範圍少得多。如何計算桶和散列值的對應關係？似乎有些函數反映（0 ... size_t） - >（0 ... size_of_buckets - 1）。但使用這樣的函數可能會導致大量的衝突，即使對於良好的散列函數。

Answer 1

我不知道確切的std::unordered_map行爲是否被定義在標準中。然而，基本原則是這樣的：始終保持桶的數量大於容器的大小乘以一個小數字（這個小數字是1.0/load_factor）。這樣，碰撞應該很少。

對於哈希表，通常有兩種方法來計算bucket_index：被選擇

1. 數桶的是2的冪：散列計算，那麼一些用提取其較低/較高位的位操作。這種方法需要一個「好的」散列函數，其中每個位都是隨機的
2. 桶的數量被選爲質數：計算散列，然後用模操作計算bucket_index。此方法不需要「太好」散列函數

對於方法1.如果散列函數質量不好，可能會發生很多衝突。對於方法2，即使使用質量不太好的散列函數，碰撞通常也很少見。但是，方法1通常更快，因爲比特操作比mod更快（但是有技術可以使它更快），並且足夠好的質量哈希函數通常很便宜。

Answer 2

許多哈希表的構建足夠通用，以支持許多不同的哈希函數，因此大多數哈希函數不會「計算」哈希函數的範圍與存儲區數量之間的對應關係。

然而，桶的數量依賴於哈希表的內部結構（衝突解決技術等），尤其是在這個值爲load factor的值上，並且當達到負載因子限制時，實現通常會增加桶的數量由預定的常數因子決定。

你應該尋找更多的進入std::unordered_map接口和玩以下功能，以瞭解更多

http://en.cppreference.com/w/cpp/container/unordered_map/max_bucket_count http://en.cppreference.com/w/cpp/container/unordered_map/bucket_count http://en.cppreference.com/w/cpp/container/unordered_map/bucket_size ​​ http://en.cppreference.com/w/cpp/container/unordered_map/load_factor