Java HashMap如何处理具有相同哈希代码的不同对象?

根据我的理解,我认为:

  1. 两个对象具有相同的哈希码是完全合法的。
  2. 如果两个对象相等(使用equals()方法),那么它们具有相同的哈希码。
  3. 如果两个对象不相等,则它们不能具有相同的哈希码

我对么?

现在,如果正确,我有以下问题: HashMap内部使用该对象的哈希码。 因此,如果两个对象可以具有相同的哈希码,那么HashMap如何跟踪它使用的密钥呢?

有人可以解释HashMap如何在内部使用对象的哈希码吗?

哈希映射就像这样(这有点简化了,但它说明了基本的机制):

它有许多“桶”,它用来存储键值对。每个桶都有唯一的编号 – 这就是标识桶的标识。 当你把一个键值对放到map中时,hashmap会查看key的哈希码,并把它存储在标识符是哈希码的桶中。 例如:密钥的哈希码是235 – >该对存储在桶号235中。(请注意,一个桶可以存储多于一个键值对)。

当你在hashmap中查找一个值时,通过给它一个键,它将首先查看你给出的键的哈希码。 然后,hashmap将查看相应的存储桶,然后通过将它与equals()进行比较,将它与存储桶中所有对的关键字进行比较。

现在你可以看到这对查找映射中的键值对非常有效:哈希映射通过哈希码的哈希码立即知道在哪个桶中查找,因此只需要testing该桶中的内容。

看一下上面的机制,你也可以看到key的hashCode()equals()方法需要什么要求:

  • 如果两个键相同( equals()在比较时返回true ),它们的hashCode()方法必须返回相同的数字。 如果密钥违反了这一点,那么相同的密钥可能会被存储在不同的桶中,并且hashmap将无法find键值对(因为它将看起来在同一个桶中)。

  • 如果两个密钥不同,那么它们的哈希码是否相同并不重要。 如果它们的哈希码相同,它们将被存储在同一个桶中,在这种情况下,哈希映射将使用equals()来区分它们。

你的第三个断言是不正确的。

两个不相等的对象具有相同的哈希码是完全合法的。 它被HashMap用作“第一遍filter”,以便地图可以使用指定的键快速find可能的条目。 然后testing具有相同散列码的密钥与指定密钥的相等性。

你不希望两个不等于的对象不能有相同的哈希代码,否则会限制你2 32个可能的对象。 (这也意味着不同的types甚至不能使用对象的字段来生成哈希码,因为其他类可能会生成相同的哈希)。

HashMap结构图

HashMap是一个Entry对象的数组。

考虑HashMap只是一个对象数组。

看看这个Object是什么:

 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; … } 

每个Entry对象表示一个键值对。 如果一个存储桶有多个Entry则下一个字段将引用另一个Entry对象。

有时可能会发生2个不同对象的散列码相同。 在这种情况下,两个对象将被保存在一个存储桶中,并将作为链接列表呈现。 入口点是最近添加的对象。 这个对象引用next字段的另一个对象,依此类推。 最后一项是null

当你用默认的构造函数创build一个HashMap

 HashMap hashMap = new HashMap(); 

数组创build时的大小为16,默认为0.75。

添加一个新的键值对

  1. 计算密钥的哈希码
  2. 计算位置hash % (arrayLength-1)应放置元素的位置(存储区编号)
  3. 如果尝试使用已经保存在HashMap的键添加值,则会覆盖值。
  4. 否则元素被添加到存储桶中。

如果存储桶已经有至less一个元素,则添加一个新元素并将其放置在存储桶的第一个位置。 其next字段是指旧元素。

删除

  1. 计算给定密钥的哈希码
  2. 计算桶号hash % (arrayLength-1)
  3. 获取对存储区中第一个Entry对象的引用,并通过equals方法遍历给定存储区中的所有条目。 最终我们会find正确的Entry 。 如果找不到所需的元素,则返回null

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.htmlfind很好的信息。;

总结:

HashMap的工作原理是哈希

put(key,value): HashMap将key和value对象存储为Map.Entry。 散列表应用散列码(key)来获取存储桶。 如果发生冲突,HashMap使用LinkedList来存储对象。

get(key): HashMap使用Key Object的哈希码来查找桶的位置,然后调用keys.equals()方法在LinkedList中标识正确的节点,并返回Java HashMap中关键字的相关值对象。

下面是对Java 8版本的HashMap机制的粗略描述(可能与Java 6稍有不同)


内部类

  • Map.Entry
    在地图中表示单个实体,键/值实体,
  • HashMap.Node
    链接列表版本的节点,

    它可以代表:

    • 哈希桶,
      因为它有一个散列属性,
    • 单链表中的节点(因此也是链表的头部)
  • HashMap.TreeNode
    节点的树版本。

数据结构

  • 哈希表
    哈希值是通过key hash()上的hash()来计算的,它决定了哪个hashtable用于给定的key。
  • 链接列表 (单独)
    当一个桶中的元素计数很小时,使用一个单链表。
  • 红黑树
    当一个桶中的元素数很大时,使用红黑树。

HashMap字段

  • Node[] table
    桶表(链表的头)。
    如果一个桶不包含元素,那么它是空的,因此只占用一个引用的空间,
  • Set<Map.Entry> entrySet实体集合,
  • int size
    实体数量,
  • float loadFactor
    指出哈希表是如何被允许的,
  • int threshold
    resize的下一个大小, threshold = capacity * loadFactor

内部方法

  • int hash(key)
    图散列,
  • 将散列映射到存储区
    使用以下逻辑
 static int hashToBucket(int tableSize, int hash) { return (tableSize - 1) & hash; } 

容量

容量,是指哈希表的桶数,可以从table.length得到,也可以通过thresholdloadFactor来计算,因此不需要定义为类字段。

capacity() :获得有效容量。


性能

  • 得到和放
    具有时间复杂性O(1),因为:
    • 桶通过索引访问。
    • 每个桶中的链表长度很小,
    • 树的大小也是有限的,因为当元素数量增加时会扩展容量和重新散列,所以可以把它看作O(1)而不是O(log N),

手术

  • 通过密钥查找实体
    首先通过散列值查找桶,然后循环链表或searchsorting树。
  • 用键添加实体首先根据键的哈希值查找桶。
    然后尝试find值:
    • 如果find,则replace该值。
    • 否则,在链表的开始处添加一个新的节点,或插入到已sorting的树中。
  • 调整
    当达到threshold时,将哈希表的容量加倍( table.lenght ),然后对所有元素执行重新哈希以重build表。 这可能是一个昂贵的操作。

散列码确定散列图检查哪个存储桶。 如果桶中有多个对象,则执行线性search以查找桶中的哪个项目等于所需的项目(使用equals() )方法。

换句话说,如果你有一个完美的散列码,那么散列表访问是不变的,你将永远不需要遍历一个存储桶(从技术上讲,你也必须有MAX_INT桶,Java实现可以在同一个桶中共享一些散列码减less空间需求)。 如果你有最糟糕的散列码(总是返回相同的数字),那么你的散列表访问就变成线性了,因为你必须search地图中的每个项目(它们都在同一个桶中)才能得到你想要的结果。

大部分时间,一个写得好的散列码并不完美,但是足够独特,可以给你提供更多或更less的常量访问。

你在第三点弄错了。 两个条目可以具有相同的哈希码,但不相等。 看看OpenJdk中HashMap.get的实现 。 你可以看到它检查哈希是否相等,键是相等的。 如果第三点是真的,那么就没有必要检查键是否相等。 在密钥之前比较哈希码,因为前者是更有效的比较。

如果你有兴趣了解更多这方面的知识,可以看一下维基百科关于Open Addressing碰撞parsing的文章,我相信这是OpenJdk实现使用的机制。 这个机制与其他答案提到的“桶”方法略有不同。

对于我们中的很多人来说,这是一个最令人困惑的问题,但并不那么复杂。

我们知道

  • HashMap在Map.Entry中存储键值对 (我们都知道)

  • HashMap在散列algorithm上工作, 在put()和get()方法中使用hashCode()和equals()方法。 (即使我们知道这一点)

  • When we call put method by passing key-value pair, HashMap uses Key **hashCode()** with hashing to **find out the index** to store the key-value pair. (this is important)

  • The Entry is **stored in the LinkedList**, so if there are already existing entry, it uses **equals() method to check if the passed key already exists** (even this is important)

  • 如果是,则覆盖该值,否则它将创build一个新条目并存储该键值条目。

  • 当我们通过传递Key调用get方法时 ,它再次使用hashCode()来查找数组中的索引 ,然后使用equals()方法find正确的Entry并返回它的值。 (现在这很明显)

这个图像将帮助你了解:

编辑九月2017:在这里我们看到哈希值如果与我们一起使用时发现桶。

 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { } 

在这里输入图像说明

 import java.util.HashMap; public class Students { String name; int age; Students(String name, int age ){ this.name = name; this.age=age; } @Override public int hashCode() { System.out.println("__hash__"); final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { System.out.println("__eq__"); if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Students other = (Students) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } public static void main(String[] args) { Students S1 = new Students("taj",22); Students S2 = new Students("taj",21); System.out.println(S1.hashCode()); System.out.println(S2.hashCode()); HashMap<Students,String > HM = new HashMap<Students,String > (); HM.put(S1, "tajinder"); HM.put(S2, "tajinder"); System.out.println(HM.size()); } } Output: __ hash __ 116232 __ hash __ 116201 __ hash __ __ hash __ 2 

所以在这里我们看到,如果对象S1和S2有不同的内容,那么我们很确定我们重写的Hashcode方法将为这两个对象生成不同的Hashcode(116232,11601)。 现在因为有不同的哈希码,所以它甚至不会打扰EQUALS方法。 因为不同的Hashcode保证对象中的不同内容。

  public static void main(String[] args) { Students S1 = new Students("taj",21); Students S2 = new Students("taj",21); System.out.println(S1.hashCode()); System.out.println(S2.hashCode()); HashMap<Students,String > HM = new HashMap<Students,String > (); HM.put(S1, "tajinder"); HM.put(S2, "tajinder"); System.out.println(HM.size()); } } Now lets change out main method a little bit. Output after this change is __ hash __ 116201 __ hash __ 116201 __ hash __ __ hash __ __ eq __ 1 We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally calls Equal method to verify this. Conclusion If hashcode is different , equal method will not get called. if hashcode is same, equal method will get called. Thanks , hope it helps. 

散列图的工作原理是哈希

HashMap get(Key k)方法在键对象上调用hashCode方法,并将返回的hashValue应用到其自己的静态哈希函数中,以find一个桶位置(backing array),其中键和值以嵌套类Entry(Map。条目)。 所以你已经得出结论,从上一行,键和值都存储在桶中作为一个Entry对象的forms。 所以认为只有价值存储在桶里是不正确的,不会给面试官留下好印象。

  • 每当我们调用HashMap对象的get(Key k)方法。 首先检查密钥是否为空。 请注意,HashMap中只能有一个空键。

如果key为null,那么Null键总是映射到散列0,因此索引为0。

如果key不为null,那么它将调用关键对象的散列函数,见上面方法的第4行,即key.hashCode(),所以在key.hashCode()返回hashValue之后,第4行看起来像

  int hash = hash(hashValue) 

现在,它将返回的hashValue应用到它自己的散列函数中。

我们可能想知道为什么我们使用hash(hashValue)再次计算散列值。 答案是它防范低质量的散列函数。

现在使用最终的哈希值来查找Entry对象的存储位置。 入口对象像这样存储在存储桶中(hash,key,value,bucketindex)

每个Entry对象表示键值对。 如果一个桶具有多于1个Entry,则字段next引用其他Entry对象。

有时可能会发生,2个不同对象的hashCodes是相同的。 在这种情况下,2个对象将被保存在一个桶中,并将被呈现为LinkedList。 入口点是最近添加的对象。 这个对象引用其他对象与下一个领域等等。 最后一项是空的。 当你用默认的构造函数创buildHashMap的时候

arrays获得创build与大小16和默认0.75负载平衡。

在这里输入图像说明

(资源)

我不会详细讨论HashMap是如何工作的,但会举一个例子,让我们记住HashMap是如何工作的。

我们有Key,Value,HashCode和bucket。

有一段时间,我们将把它们分别与以下内容联系起来:

  • 斗 – >一个社会
  • HashCode – >社会地址(永远唯一)
  • 价值 – >社会之家
  • 键 – >房屋地址。

使用Map.get(key):

Stevie想要find住在贵宾社区别墅的朋友(Josse)家,让它成为JavaLovers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引,我们根据SSN找出协会的名字。 这个索引可以被认为是查找HashCode的algorithm。

  • SSN协会的名字
  • 92313(Josse's) – JavaLovers
  • 13214 – AngularJSLovers
  • 98080 – JavaLovers
  • 53808 – 生物学家

  1. 这个SSN(key)首先给了我们一个HashCode(来自索引表),它只是Society的名字。
  2. 现在,多房子可以在同一个社会,所以HashCode可以是常见的。
  3. 假设,这个社团是两个房子的共同点,我们怎么去确定我们要去哪个房子,是的,通过使用只是房子地址的(SSN)键

使用Map.put(key,Value)

通过查找HashCode,然后存储值,为此Valuefind一个合适的社会。

我希望这有帮助,这是开放的修改。

哈希映射如何在java中工作的一个总结forms?

HashMap的工作原理是哈希,我们有put()和get()方法来存储和检索HashMap中的对象。 当我们传递key和value来存放HashMap的方法时,它使用key对象的hashcode()方法来计算hashcode,并且通过在hashcode上应用散列来标识存储value对象的bucket位置。 在检索时,它使用键对象的equals方法来找出正确的键值对和与该键相关联的返回值对象。 在碰撞的情况下,HashMap使用链表,对象将被存储在链表的下一个节点。 另外HashMap在链表的每个节点都存储key + value元组。

两个对象是相等的,意味着它们具有相同的哈希码,但是反之亦然

Java 8更新HashMap-

你在你的代码中执行这个操作 –

 myHashmap.put("old","key-value-pair"); myHashMap.put("very-old","old-key-value-pair"); 

所以,假设你的hashcode返回的键"old""very-old"是一样的。 那么会发生什么。

myHashMap是一个HashMap,假设你最初没有指定它的容量。 所以默认的容量是java。所以现在只要你用new关键字初始化hashmap,它就创build了16个桶。 现在当你执行第一个陈述时 –

 myHashmap.put("old","key-value-pair"); 

那么计算"old"的散列码,因为散列码也可能是非常大的整数,所以,Java内部做到了这一点 – (散列是散列码,>>>是右移)

 hash XOR hash >>> 16 

所以给出一个更大的画面,它会返回一个索引,这个值在0到15之间。现在你的键值对"old""key-value-pair"将被转换为Entry对象的键和值实例variables。 然后这个入口对象将被存储在存储桶中,或者你可以说在一个特定的索引处,这个入口对象将被存储。

FYI-Entry是Map接口Map.Entry中的一个类,带有这些签名/定义

 class Entry{ final Key k; value v; final int hash; Entry next; } 

现在当你执行下一个陈述时 –

 myHashmap.put("very-old","old-key-value-pair"); 

"very-old"给出了与"old"相同的散列码,所以这个新的键值对再次被发送到相同的索引或相同的桶。 但是由于这个桶不是空的,因此Entry对象的nextvariables用来存储这个新的键值对。

这将被存储为具有相同散列码的每个对象的链表,但是TRIEFY_THRESHOLD被指定为值6.因此,在到达之后,链表被转换为平衡树(红黑树),其中第一个元素为根。

据说,一张图片胜过千言万语。 我说:有些代码优于1000字。 这是HashMap的源代码。 获取方法:

 /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } 

所以很明显,使用散列来查找“桶”,并且第一个元素总是在该桶中被检查。 如果不是,则使用键的equals来查找链表中的实际元素。

让我们看看put()方法:

  /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

它稍微复杂一些,但是很明显,新的元素被放在基于散列计算的位置的标签中:

i = (n - 1) & hash在这里, i是新元素将被放置(或它是“桶”)的索引。 ntab数组的大小(“桶”的数组)。

首先,试图把它作为“桶”中的第一个元素。 如果已经有一个元素,那么附加一个新的节点到列表中。

这将是一个长时间的答案,喝一杯,然后阅读…

哈希就是将一个键值对存储在内存中,可以更快地读取和写入。 它将一个数组中的键和值存储在一个LinkedList中。

让我们说我想存储4个键值对 –

 { “girl” => “ahhan” , “misused” => “Manmohan Singh” , “horsemints” => “guess what”, “no” => “way” } 

所以要存储这些键,我们需要一个4元素的数组。 现在如何将这4个键之一映射到4个数组索引(0,1,2,3)?

所以javafind了各个键的hashCode,并将它们映射到一个特定的数组索引。 哈希码公式是 –

 1) reverse the string. 2) keep on multiplying ascii of each character with increasing power of 31 . then add the components . 3) So hashCode() of girl would be –(ascii values of l,r,i,g are 108, 114, 105 and 103) . eg girl = 108 * 31^0 + 114 * 31^1 + 105 * 31^2 + 103 * 31^3 = 3173020 

哈希和女孩! 我知道你在想什么 你对这个狂野的二重奏的迷恋可能会让你错过一件重要的事情。

为什么Java与31乘?

这是因为,31是2 ^ 5 – 1forms的奇素数。 奇素减less了哈希碰撞的机会

现在这个哈希代码如何映射到数组索引?

答案是, Hash Code % (Array length -1) 。 所以在我们的例子中, “girl”被映射为(3173020 % 3) = 1 。 这是数组的第二个元素。

并且值“ahhan”被存储在与数组索引1相关联的LinkedList中。

HashCollision – 如果您尝试使用上述公式find键“misused” “horsemints”“horsemints”“horsemints” ,则会看到两者都给予相同的1069518484 。 哇! 学习到教训了 –

2个相同的对象必须有相同的hashCode,但是不能保证hashCode是否匹配,那么这些对象是相等的。 所以它应该存储对应于“misused”和“horsemints”两个值的桶1(1069518484%3)。

现在哈希映射看起来像 –

 Array Index 0 – Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”) Array Index 2 – LinkedList (“way”) Array Index 3 – 

现在,如果有人试图find关键字“horsemints”的值,java很快就会find它的hashCode,对它进行模块化并开始在LinkedList中find它对应的index 1 。 所以这样我们不需要search所有4个数组索引,从而使数据访问更快。

但等一下 那LinkedList中有3个对应的数组索引1,它是如何找出哪一个是关键“horsemints”的值?

其实我说谎,当我说HashMap只是在LinkedList中存储值。

它将两个键值对都存储为映射条目。 所以实际上地图看起来像这样。

 Array Index 0 – Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>) Array Index 2 – LinkedList (<”no” => “way”>) Array Index 3 – 

现在你可以看到在遍历与ArrayIndex1对应的linkedList时,它实际上将该LinkedList的每个条目的关键字与“horsemints”进行比较,当它find一个时,它只返回它的值。

希望你在阅读时玩得开心:)