维基百科文章可能包含大量技术信息,但散列的简单视图如下。
想象一下有一个神奇的函数可以为任何对象提供一个数字。给定相同的对象,它总是返回相同的数字。
现在您立即有了一种快速测试两个对象是否相同的方法:询问此函数获取它们的数字,然后进行比较。如果它们不同,则它们不相同。
但是如果它们有相同的数字呢?不同的对象能否具有相同的数字?
是的,在大多数情况下是可能的。例如,假设该函数只能给出1到10之间的数字,并且有100个不同的对象。那么当然会有一些不同的对象必须具有相同的数字。这就是所谓的“碰撞”。 “碰撞”使我们的快速相等性测试不太有用,因此我们尽可能地希望将其最小化。一个好的神奇函数是尝试最小化“碰撞”的数量。
那么您还可以用这个数字做什么呢?嗯,您可以使用它来索引一个数组。给定一个对象,您可以将其放置在由来自此神奇函数的数字给出的索引处。这个数组本质上就是散列表,这个神奇函数就是哈希函数。
Object
类本身的实例。 - GeorgeObject.hashCode
有关。 因此,有两件事情:(i)它不是地址,而是从地址转换的(ii)这只是典型的,并非强制实施。请记住,由于垃圾回收和虚拟机等因素,对象也可以在地址空间中移动,因此肯定存在几层抽象。 - polygenelubricants哈希表基本上是一种将任何东西存储在数组中并几乎像通过索引查找数组中的内容一样快速检索它的方法,而不浪费太多空间。
哈希函数的工作(在此上下文中)是根据对象的内容计算存储对象的数组索引。这意味着它必须始终为相同的对象返回相同的结果,并尽可能为不同的对象返回不同的结果。当两个不同的对象具有相同的哈希时,称为“冲突”,您必须特别处理这些情况,这使整个过程变慢。
哈希表中键到索引的映射称为哈希函数。 哈希函数包含两个部分
哈希码映射:它将键转换为任意范围的整数。
压缩映射:它将这些整数转换(带入)到哈希表具有的键范围内。
哈希函数:如果您将相同的对象多次传递给此函数,无论是文本、二进制还是数字,您总是会得到相同的输出。为了哈希表的目的,使用返回整数的哈希函数。
上述功能称为哈希。
哈希表:计算机科学的奇迹数据结构,以常数时间或O(1)返回搜索结果。它基于上述哈希概念。因此,它比链表、二叉搜索树等具有更好的访问时间。
为什么近似于O(1):它在内部使用数组作为其基本结构来存储对象,而数组具有恒定的访问时间,因此哈希表也具有恒定的访问时间。
[基本内部]: 因此,它在内部使用固定大小的数组,当您插入(键,值)对时,它计算键的哈希并使用此哈希值作为索引将(键,值)对存储在数组中。接下来,当您使用相同的键搜索对象时,它再次使用键的哈希作为索引在数组中搜索键。 现在,两个对象可以具有相同的哈希值,因此,在将这些对象插入哈希表时会发生冲突。有两种解决冲突的方法。您可以参考link以获取关于此主题的足够详细的讨论。
HashCode()
函数返回一个整数值,被 HashMap
用来找到正确的桶。