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

根据我的理解，我认为：

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

我对么？

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

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

Answer 1

哈希映射就像这样（这有点简化了，但它说明了基本的机制）：

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

你可以在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中关键字的相关值对象。

Answer 5

下面是对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得到，也可以通过threshold和loadFactor来计算，因此不需要定义为类字段。

capacity() ：获得有效容量。

---

性能

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

---

手术

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

我们知道

• 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))) { } 

Answer 9

 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. 

Answer 10

散列图的工作原理是哈希

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）

Answer 11

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

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

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

（资源）

Answer 12

我不会详细讨论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一个合适的社会。

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

Answer 13

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

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

Answer 14

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

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.因此，在到达之后，链表被转换为平衡树（红黑树），其中第一个元素为根。

Answer 15

据说，一张图片胜过千言万语。 我说：有些代码优于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是新元素将被放置（或它是“桶”）的索引。 n是tab数组的大小（“桶”的数组）。

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

Answer 16

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

哈希就是将一个键值对存储在内存中，可以更快地读取和写入。 它将一个数组中的键和值存储在一个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一个时，它只返回它的值。

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