字典/ hash_map密鑰大小

計算密鑰的哈希值併除以質數。一般來說，這是否有任何標準的素數（比如32/64位）？字典/ hash_map密鑰大小

我的理解是哈希表是不可調整大小/可調整和它的內部數組取決於此。如果我只有5個元素的散列表，那麼在關鍵空間中會有浪費嗎？

編輯：我應該更好的框架。在C++ hash_map（boost）或C＃Dictionary中使用的一般方法是什麼

2010-11-09 tvr

如果你只有5個元素，爲什麼要使用哈希表呢？ – 2010-11-09 04:17:14

所以你從來沒有使用5個元素的字典？問題是爲什麼不呢？這是一個假設性問題。或者，您建議使用什麼邊界號碼？ – tvr 2010-11-09 04:20:22

我想我已經創建了一個字典，最終只有五個元素。儘管如此，我會以更大的尺寸分配它（可能超過10個）以減少碰撞的可能性。 – 2010-11-09 16:49:37

實際上，哈希表大小可以自動調整。你可能要做的是分配一個大小爲N的數組，使用哈希模N（某個素數）來索引數組。如果你跟蹤你的分配密度，那麼當它增加到一定的閾值以上時，你可以分配一個大小爲N1的新數組（一些較大的素數），然後複製舊數組中的每個元素，將哈希函數與新模模尋找它在新的哈希表中的位置。最後，您取消分配舊數組並使用新的更大陣列。

來源

2010-11-09 04:21:16

謝謝！我應該更好地構思這一點。在C++ hash_map（boost）或C＃Dictionary中遵循的一般方法是什麼？ – tvr 2010-11-09 04:28:37

通常，素數被用作內部數組的大小。也就是說，如果有人要求一個包含100個項目的哈希表，那麼選擇大於等於100的下一個素數就是大小。在這種情況下，您的桌面尺寸爲101.

但這不是唯一的方法。

來源

2010-11-09 04:19:41

爲什麼不使用Reflector來查看C＃Dictionary或HashTable的實現？格雷格和吉姆的答案都是正確的一般性術語和C＃實現。

總之，C＃字典實現使用一個質數（大於它的容量）作爲內部桶數組的大小，並用它來分割哈希碼。每當需要調整內部陣列的大小時，它將使用現有容量的兩倍作爲新容量。

來源

2010-11-09 06:43:24 VinayC

字典/ hash_map密鑰大小

回答

相關問題