带整数键的哈希表（字典等）

我一直在困惑这几天...随时击落我的任何假设。带整数键的哈希表（字典等）

我们使用带整数键的字典。我假设在这种情况下密钥的值直接用作散列。这是否意味着（如果密钥分组在一个小范围内），密钥散列的分布（与密钥本身相同，对吧？）将会在一个相似的小范围内，因此是散列表的一个不好的选择？

它会更好，提供的是的IEqualityComparer做了与素数一些聪明和模数学的方法计算更好的分布式哈希？

来源

2009-09-07 spender

它取决于你的整数键的分布。在计算散列桶时，密钥已经被素数模块化了。 – 2009-09-07 08:59:28

为什么假设散列码与整数值相同？测试它！ – SteveD 2009-09-07 09:09:11

哈希码与整数值相同。 – spender 2009-09-07 09:57:52

，不作为直接在字典中仍然会要求其散列的关键 - 但一个Int32的哈希值是只是价值，所以你的问题的重点是相关的，是的。

我相信.NET词典作品不依赖于哈希值的方式均匀分布。它需要hash % bucketCount其中bucketCount始终是总理。（这从内存是虽然 - 我可能是错的。）

你仍然可以结束了一个低效率的一套课程的钥匙，如果他们碰巧由斗式计数间隔。这将永远是这样，但 - 哈希表将永远只能是真正 O（1），如果他们有独特的哈希值和表维护一组桶的每一个可能的散列:)在现实中，所有键它往往不成问题。如果你碰巧知道将是一个问题，那么是的，自定义IEqualityComparer<T>可以帮助。

来源

2009-09-07 08:57:55

刚刚与反射器检查...你是正确的哈希％bucketcount。知道这一切都落到了位置。谢谢乔恩。 – spender 2009-09-07 11:57:17

假设您使用的是标准库散列表实现，那么关键是而不是该散列，即使该键是整数，这正是您指出的原因。

所以当您对散列分布逻辑是正确的，你最初的假设是整数键将意味着散列=键可能不是。

如果我错了：.NET然后哦，这更多的是一个广义的答案。 :)

来源

2009-09-07 08:58:25 Amber

我认为数字类型的哈希值只是值，假设它适合哈希范围是相当常见的。 – 2009-09-07 09:00:57

您遇到的潜在问题是数字序列中的模式 - 如果模式宽度是您的bucketCount的倍数，您会遇到问题。 – Amber 2009-09-07 09:03:42

正如我的帖子提到的......但任何*散列算法都可以解决这个问题，如果你不走运。 – 2009-09-07 09:08:42

之前做一些聪明的我会测试它的速度，就是看它是否适合你。如果不是，那么尝试一下聪明的事情。但我希望最好不要放弃它;哈希不碰撞更重要，只要发生了这种情况，生活就会好起来。

来源

2009-09-07 09:02:15

带整数键的哈希表（字典等）

回答

相关问题