選擇散列密鑰類型的基本原理

Question

夥計們，我有一個數據結構，它有25個不同的鍵（整數）和一個值。我有這些對象的列表（比如50000），我打算使用散列表來存儲/檢索它們。我打算採取這些方法之一。

1. 從這25個整數鍵中創建一個整數散列並將其存儲在散列表上。 （是的，我有一些手段來處理衝突）

2. 在各個鍵上進行字符串連接並將其用作散列表的散列鍵。例如，如果鍵值是1,2,4,6,7，那麼散列鍵將是「12467」。

假設我有一個總的50000記錄每次與25個不同的鍵和值，然後將我的第二個方法是矯枉過正，當涉及到它需要做檢索字符串比較和插件的成本一個記錄？

更多信息！

1. 哈希表中的每個桶都是平衡二叉樹。
2. 我使用boost庫的hash_combine方法從25個鍵創建哈希。

Answer 1

絕對使用第一種方法，因爲如果您使用第二種方法，您將需要一個具有1x10^(25m), where x is the maximum length of a key插槽可用的散列表。

例如，如果一個密鑰的最大數量可以是9999，那麼m應該是4，並且您需要表中的1x10^100個插槽。

---

說明：

哈希表背後的想法是，你可以隨意使用O（1）的效率訪問任何元素（碰撞除外），因爲任何元素的哈希是逸岸它的位置在散列表。例如，如果我散列Object X並返回24的散列（或者一些字符串散列被轉換爲數字，結果是24），我只需要到我的表的第24槽（通常實現爲數組），並可以檢索對象X.

但是，如果您使用第二種方法（連接25個數字 - 我們會說數字來簡化這裏的事情 - 一起做散列），最大的散列將是9999999999999999999999999。因此，要從哈希表中檢索該對象，您必須從位置9999999999999999999999999檢索它 - 這意味着您的表格必須至少具有多個點。

---

請記住，第一個 - 因爲您使用的是二叉樹，所以碰撞不會真的成爲一件大事。最糟糕的情況將是O（log（n））的檢索/插入效率，這實際上並不那麼糟糕。