c++ - 选择哈希键类型的理由

Question

伙计们，我有一个数据结构，它有 25 个不同的键(整数)和一个值。我有这些对象的列表(比如 50000)，我打算使用哈希表来存储/检索它们。我打算采用其中一种方法。

1. 从这 25 个整数键创建一个整数哈希并将其存储在哈希表中。 (是啊!我有办法处理碰撞)

2. 在各个键上进行字符串连接，并将其用作哈希表的哈希键。例如，如果键值为 1、2、4、6、7，则哈希键将为“12467”。

假设我总共有 50000 条记录，每条记录都有 25 个不同的键和一个值，那么当涉及到检索和插入记录所需的字符串比较成本时，我的第二种方法会不会有点矫枉过正？

更多信息!

1. 哈希表中的每个桶都是一棵平衡二叉树。
2. 我正在使用 boost 库的 hash_combine 方法从 25 个键创建散列。

Answer 1

绝对使用第一种方法，因为如果使用第二种方法，您将需要一个具有 1x10^(25m) 的哈希表，其中 x 是可用的键的最大长度。

例如，如果键的最大数量是 9999，则 m 将为 4，并且您的表中需要 1x10^100 个槽。

---

解释:

哈希表背后的想法是，您可以随机访问任何元素，效率为 O(1)(不考虑冲突)，因为任何元素的哈希 实际上就是它在哈希表中的位置。因此，例如，如果我散列对象 X 并返回散列 24(或一些字符串散列转换为数字，结果为 24)，我只需转到表的槽 24(通常实现为数组)，并且可以检索对象 X。

但是，如果您使用第二种方法(连接 25 个数字 - 我们将在这里说数字以简化事情 - 一起构成哈希)，最大的哈希将是 9999999999999999999999999。因此，要从哈希表中检索该对象，您必须从位置 9999999999999999999999999 检索它 - 这意味着您的 table 必须至少有那么多点。

---

请记住，对于第一个 - 因为您使用的是二叉树，所以碰撞不会真的有那么大的问题。最坏的情况是 O(log(n)) 的检索/插入效率，但实际上并没有那么糟糕。