选择散列密钥类型的基本原理

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））的检索/插入效率，这实际上并不那么糟糕。