我已经查看了这个维基百科页面,但我仍然不明白。有人可以帮助我笨拙的头脑理解散列、散列表/散列图和散列函数的概念吗?一些例子真的很有帮助。
8 回答
Wikipedia 文章将包含大量技术信息,但哈希的简单视图如下所示。
想象一下,有一个神奇的函数可以给任何对象一个数字。给定相同的对象,它总是返回相同的数字。
现在你有一个快速的方法来测试两个对象是否相同:向这个函数询问它们的数字并进行比较。如果它们不同,那么它们就不一样了。
但是如果他们有相同的号码呢?两个不同的物体可以有相同的数字吗?
是的,这在大多数情况下都是可能的。例如,假设该函数只能给出 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 together。
您可能还会看到有关编写“良好”或“分布良好”的哈希码的参考资料。这与前面关于 hashcode 和 equals 的陈述相反的事实是不正确的。更具体地说a.hashCode() == b.hashCode() 并不一定意味着 a.equals(b)所以一个好的哈希码的想法是你减少 a.hashCode() == b.hashCode() 的可能性a.equals(b) 是假的。您可能已经看到这被称为散列函数的冲突。
回到哈希图/表。这些基于键/值对。因此,当您添加或检索一个值时,您将提供一个键。所以地图要做的第一件事就是寻找密钥,这意味着找到 .equals() 你提供的密钥的东西。但正如我们上面讨论的,.equals() 可能非常慢,这意味着通过首先检查哈希码可以大大加快比较速度。因为当哈希码分布良好时,您应该很快知道 x 何时肯定是 != y。
现在除了比较哈希图/表之外,实际上使用哈希码来组织数据的内部存储,但是我认为这超出了您目前想要了解的范围。
散列函数:散列函数采用一组字符(称为键)并将其映射到一定长度的值(称为散列值或散列)。哈希值代表原始字符串,但通常小于原始字符串。哈希用于索引和定位数据库中的项目,因为找到较短的哈希值比找到较长的字符串更容易。散列也用于加密。这个术语也称为散列算法或消息摘要函数。
HASH MAP:- HashMap 是一个集合类,旨在将元素存储为键值对。地图提供了一种根据另一件事的价值查找一件事的方法。
一种查找表,旨在有效地存储在其字母或数字序列中可能有很大间隙的非连续键(帐号、部件号等)。
哈希表:- 哈希表是使用一种算法创建的,该算法将键存储到哈希桶中,其中包含键值对。由于不同的键可能散列到同一个桶中,因此哈希表设计的目标是使键值对均匀分布,每个桶包含尽可能少的键值对。当查找一个项目时,它的键被散列以找到合适的桶,然后比较桶以找到正确的键值对。
哈希表基本上是一种将任何内容存储在数组中并检索它几乎与通过索引在数组中查找内容一样快的方法,而不会浪费太多空间。
哈希函数的工作是(在此上下文中)根据对象的内容计算将存储对象的数组索引。这意味着,它必须始终为同一个对象返回相同的结果,并且应该尽可能地为不同的对象返回不同的结果。当两个不同的对象具有相同的哈希值时,这称为“冲突”,您必须特殊处理这些情况,这会使整个事情变慢。
将键映射到哈希表的索引称为哈希函数。哈希函数包含两部分
Hash Code Map:它将键转换为任何范围的整数。
压缩映射:它将这些整数转换(带来)到哈希表的键范围。
散列函数:如果你将同一个对象多次传递给这个函数,无论是文本、二进制还是数字,你总是得到相同的输出。出于哈希表的目的,使用了返回整数的哈希函数。
上面的功能是调用散列。
哈希表:以恒定时间或 O(1) 返回搜索结果的计算机科学奇迹数据结构。它基于上述哈希的概念。因此,它比链表、二叉搜索树等具有更好的访问时间。
为什么接近 O(1):它在内部使用数组作为其基本结构来存储对象,并且由于数组具有恒定的访问时间,因此哈希表也是如此。
[基本内部]:所以,它在内部使用一个固定大小的数组,当你插入一个 (Key, Value) 对时,它会计算 key 的哈希值并使用这个哈希值作为索引来将 (Key,Value) 对存储在数组中. 接下来,当您使用相同的键搜索对象时,它再次使用该键的哈希作为索引来搜索数组中的键。现在,两个对象可以具有相同的哈希值,因此,在将这些对象插入哈希表时会发生冲突。有两种解决冲突的方法。您可以参考此链接以获取有关此主题的足够详细的讨论。
HashCode()
函数返回一个整数值,用于HashMap
查找正确的存储桶。