logo标签列表

什么是Java中的哈希函数？

javahashmaphashhash-function
7
我查看了这个Wikipedia页面，但我仍然不理解。请有人帮助我理解哈希、哈希表/映射和哈希函数的概念吗？举一些例子会很有帮助。
3
你不明白维基百科的哪些内容？否则我们只会重复相同的信息。 - polygenelubricants
1
这篇文章对我来说似乎很清晰，所以一般情况下我会很难提出其他的解释。你能否更具体地说明你在那篇文章中不理解的是什么？ - Péter Török
一个示例或代码样本至少会有所帮助。 - Mohit Deshpande
8个回答
26

维基百科文章可能包含大量技术信息，但散列的简单视图如下。

想象一下有一个神奇的函数可以为任何对象提供一个数字。给定相同的对象，它总是返回相同的数字。

现在您立即有了一种快速测试两个对象是否相同的方法：询问此函数获取它们的数字，然后进行比较。如果它们不同，则它们不相同。

但是如果它们有相同的数字呢？不同的对象能否具有相同的数字？

是的，在大多数情况下是可能的。例如，假设该函数只能给出1到10之间的数字，并且有100个不同的对象。那么当然会有一些不同的对象必须具有相同的数字。这就是所谓的“碰撞”。 “碰撞”使我们的快速相等性测试不太有用，因此我们尽可能地希望将其最小化。一个好的神奇函数是尝试最小化“碰撞”的数量。

那么您还可以用这个数字做什么呢？嗯，您可以使用它来索引一个数组。给定一个对象，您可以将其放置在由来自此神奇函数的数字给出的索引处。这个数组本质上就是散列表，这个神奇函数就是哈希函数。

6
哈希函数是一种创建任意数量数据的紧凑表示方式。在Java中，使用hashCode方法意味着以某种方式描述对象的状态（无论多大）为一个int（4个字节）。并且通常会尽量编写成较快的方式，如下所述。
简化来说，在哈希表/哈希映射中，hashCode类似于cheap equals。假设有两个类型为Foo的对象a和b，要确定a.equals(b)需要500毫秒，而计算a（高效的）hashCode只需要10毫秒。因此，如果我们想知道a.equals(b)，首先我们会查看hashcodes并询问a.hashCode() == b.hashCode()是否成立。请注意，在我们的示例中，这将仅花费20毫秒。
由于hashCode的API定义，我们知道如果a的hashCode不等于b，则a.equals(b)永远不应该为true。因此，在上面的测试中，如果我们发现hashcodes不相等，则永远不需要执行更长的.equals()测试，这就是为什么你应该总是同时覆盖hashCode和equals的原因。
您还可以看到关于编写“好”的或“分布良好”的hashCode的参考资料。这与有关hashCode和equals的先前语句的反向性质有关。更具体地说，a.hashCode() == b.hashCode()不一定意味着a.equals(b)。因此，好的hashCode的概念是在a.equals(b)为false时减少a.hashCode() == b.hashCode()的可能性。您可能已经看到这被称为哈希函数的冲突。
回到哈希映射/表。它们基于键/值对。因此，当您添加或检索值时，将提供一个键。因此，地图必须首先查找键，这意味着要找到与您提供的键.equals()的内容。但是，正如我们上面讨论的那样，.equals()可能非常慢，这意味着通过首先检查hashcodes可以大大加快比较速度。由于当hashcodes分布良好时，您应该很快知道x肯定!= y。
现在，除了比较之外，哈希映射/表实际上还使用hashCode来组织其数据的内部存储，但我认为这超出了您想要理解的范围。
3
哈希函数：哈希函数将一组字符（称为键）映射到特定长度的值（称为哈希值或哈希）。哈希值代表原始字符的字符串，但通常比原始字符串小。哈希是用于索引和定位数据库中的项目，因为找到较短的哈希值比较长的字符串更容易。哈希也用于加密。这个术语也被称为哈希算法或消息摘要函数。
哈希映射：HashMap是一个集合类，旨在将元素存储为键值对。 Map提供了一种根据另一个值查找某个东西的方法。
查找表被设计为有效地存储非连续键（帐号，零件编号等），这些键可能在它们的字母或数字序列中有宽间隔。
哈希表：哈希表是使用算法创建的，该算法将键存储到哈希桶中，哈希桶包含键值对。由于不同的键可能哈希到同一个桶中，因此哈希表设计的目标是尽可能平均地分布键值对，使得每个桶包含尽可能少的键值对。当查找项时，其键被哈希以找到适当的桶，然后将桶与正确的键值对进行比较。
1

这本书（以及支持的视频讲座）提供了一些关于算法和数据结构的很好的解释。其中有一些关于哈希函数的讲座（1，2）。我推荐阅读。

Cormen
（来源：mit.edu）

另外，只是提供信息，hashCode() 在 Object 类的实例上调用时返回该特定实例在内存中的地址。 但正如 polygenelubricants 在评论中指出的那样，这并不完全正确。

你的FYI只是半真半假。来自http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode%28%29 - 将对象的内部地址转换成整数/这种实现技术不是必需的。 - polygenelubricants
我很感兴趣。你能具体说明一下吗？ :) - George
但这不是针对覆盖此方法的类的建议吗？相反，我正在谈论Object类本身的实例。 - George
1
请阅读整个句子。该引用直接与Object.hashCode有关。 因此，有两件事情：（i）它不是地址，而是从地址转换的（ii）这只是典型的，并非强制实施。请记住，由于垃圾回收和虚拟机等因素，对象也可以在地址空间中移动，因此肯定存在几层抽象。 - polygenelubricants
0

哈希表基本上是一种将任何东西存储在数组中并几乎像通过索引查找数组中的内容一样快速检索它的方法，而不浪费太多空间。

哈希函数的工作（在此上下文中）是根据对象的内容计算存储对象的数组索引。这意味着它必须始终为相同的对象返回相同的结果，并尽可能为不同的对象返回不同的结果。当两个不同的对象具有相同的哈希时，称为“冲突”，您必须特别处理这些情况，这使整个过程变慢。

0

哈希表中键到索引的映射称为哈希函数。 哈希函数包含两个部分

哈希码映射：它将键转换为任意范围的整数。

压缩映射：它将这些整数转换（带入）到哈希表具有的键范围内。

摘自http://coder2design.com/hashing/

0

哈希函数：如果您将相同的对象多次传递给此函数，无论是文本、二进制还是数字，您总是会得到相同的输出。为了哈希表的目的，使用返回整数的哈希函数。

上述功能称为哈希。

哈希表：计算机科学的奇迹数据结构，以常数时间或O(1)返回搜索结果。它基于上述哈希概念。因此，它比链表、二叉搜索树等具有更好的访问时间。

为什么近似于O(1)：它在内部使用数组作为其基本结构来存储对象，而数组具有恒定的访问时间，因此哈希表也具有恒定的访问时间。

[基本内部]: 因此，它在内部使用固定大小的数组，当您插入（键，值）对时，它计算键的哈希并使用此哈希值作为索引将（键，值）对存储在数组中。接下来，当您使用相同的键搜索对象时，它再次使用键的哈希作为索引在数组中搜索键。 现在，两个对象可以具有相同的哈希值，因此，在将这些对象插入哈希表时会发生冲突。有两种解决冲突的方法。您可以参考link以获取关于此主题的足够详细的讨论。

-1

HashCode() 函数返回一个整数值，被 HashMap 用来找到正确的桶。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接