Moh*_*nde 6 java hash hash-function hashmap
我已经查看了这个维基百科页面,但我仍然不明白.有人可以帮助我笨拙的头脑理解散列,散列表/散列映射和散列函数的概念吗？一些例子真的会有所帮助.
pol*_*nts 22
维基百科的文章将提供大量技术信息,但哈希的简单视图如下所示.
想象一下,有一个神奇的功能,可以给任何对象一个数字.给定相同的对象,它总是返回相同的数字.
现在,您可以快速测试两个对象是否相同:询问此函数的数字并进行比较.如果它们不同,那么它们就不一样了.
但如果他们有相同的号码怎么办？两个不同的对象可以有相同的数字吗？
是的,这在大多数情况下是可行的.假设该函数只能给出介于1..10之间的数字,并且有100个不同的对象.当然,一些不同的对象必须具有相同的数字.这就是所谓的"碰撞"."碰撞"使我们的快速相等测试不那么有用,因此我们尽可能地将其发生的最小化.一个好的魔法功能是试图最小化"碰撞"的数量.
那么你还能用这个号码做什么呢？好吧,你可以用它来索引一个数组.给定一个对象,你可以将它放在由这个神奇函数中的数字给出的索引处.这个数组本质上是一个哈希表; 这个神奇的函数是一个哈希函数.
散列函数是一种创建任意大量数据的紧凑表示的方法。在带有 hashcode 方法的 java 中，这意味着以 int（4 个字节）以某种方式描述对象的状态（无论有多大）。并且通常写得相当快，如下所述。
为了简化哈希表/哈希映射，哈希码充当一种廉价的等号。以 Foo 类型的两个对象 a 和 b 来计算 a.equals(b) 是否需要 500 毫秒，而计算一个（有效的）哈希码只需要 10 毫秒。因此，如果我们想知道是否 a.equals(b) 而不是直接这样做，我们将查看哈希码并询问是否 a.hashCode() == b.hashCode()。请注意，在我们的示例中，这将只需要 20 毫秒。
由于哈希码的 API 定义，我们知道如果 a的哈希码不等于 b，则 a.equals(b) 永远不应该为真。所以在我们上面的测试中，如果我们看到哈希码不相等，那么我们永远不需要做更长的 .equals() 测试，这就是为什么你应该总是覆盖 hashCode 和 equals 在一起。
您可能还会看到有关编写“良好”或“分布良好”哈希码的参考资料。这与之前关于 hashcode 和 equals 的陈述的逆是不正确的事实有关。更具体地说a.hashCode() == b.hashCode() 并不一定意味着 a.equals(b)所以一个好的哈希码的想法是你减少 a.hashCode() == b.hashCode() 当a.equals(b) 是假的。您可能已经看到这称为散列函数的冲突。
回到哈希映射/表。这些基于键/值对。因此，当您添加或检索一个值时，您将提供一个键。所以地图必须做的第一件事就是寻找键，这意味着找到 .equals() 你提供的键。但是正如我们上面讨论的， .equals() 可能非常慢，这意味着通过首先检查哈希码可以大大加快比较速度。因为当哈希码分布良好时，您应该很快知道 x 肯定是 != y。
现在除了比较哈希图/表之外，实际上还使用哈希码来组织数据的内部存储，但是我认为这超出了您此时想要了解的范围。