伙计们,我有一个数据结构,它有 25 个不同的键(整数)和一个值。我有这些对象的列表(比如 50000),我打算使用哈希表来存储/检索它们。我打算采用其中一种方法。
从这 25 个整数键创建一个整数哈希并将其存储在哈希表中。 (是啊!我有办法处理碰撞)
在各个键上进行字符串连接,并将其用作哈希表的哈希键。例如,如果键值为 1、2、4、6、7,则哈希键将为“12467”。
假设我总共有 50000 条记录,每条记录都有 25 个不同的键和一个值,那么当涉及到检索和插入记录所需的字符串比较成本时,我的第二种方法会不会有点矫枉过正?
更多信息!
- 哈希表中的每个桶都是一棵平衡二叉树。
- 我正在使用 boost 库的 hash_combine 方法从 25 个键创建散列。
最佳答案
绝对使用第一种方法,因为如果使用第二种方法,您将需要一个具有 1x10^(25m) 的哈希表,其中 x 是可用的键的最大长度
。
例如,如果键的最大数量是 9999,则 m
将为 4,并且您的表中需要 1x10^100 个槽。
解释:
哈希表背后的想法是,您可以随机访问任何元素,效率为 O(1)(不考虑冲突),因为任何元素的哈希 实际上就是它在哈希表中的位置。因此,例如,如果我散列对象 X 并返回散列 24(或一些字符串散列转换为数字,结果为 24),我只需转到表的槽 24(通常实现为数组),并且可以检索对象 X。
但是,如果您使用第二种方法(连接 25 个数字 - 我们将在这里说数字以简化事情 - 一起构成哈希),最大的哈希将是 9999999999999999999999999。因此,要从哈希表中检索该对象,您必须从位置 9999999999999999999999999 检索它 - 这意味着您的 table 必须至少有那么多点。
请记住,对于第一个 - 因为您使用的是二叉树,所以碰撞不会真的有那么大的问题。最坏的情况是 O(log(n)) 的检索/插入效率,但实际上并没有那么糟糕。
关于c++ - 选择哈希键类型的理由,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2656183/