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

Question

根据我的理解，我认为：

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

我正确吗？

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

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

Answer 1

哈希图的工作原理如下（这有点简化，但它说明了基本机制）：

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

当您在哈希映射中查找值时，通过给它一个键，它会首先查看您提供的键的哈希码。然后，hashmap 将查找相应的存储桶，然后通过使用 equals() 进行比较，将您提供的键与存储桶中所有对的键进行比较。

现在您可以看到这对于在映射中查找键值对是如何非常有效的：通过键的哈希码，哈希映射立即知道要在哪个存储桶中查找，因此它只需测试该存储桶中的内容即可。

通过上面的机制，你也可以看出对key的hashCode()和equals()方法有什么要求：

• 如果两个key相同（当您比较它们时，equals() 返回 true），它们的 hashCode() 方法必须返回相同的数字。如果键违反了这一点，则相等的键可能会存储在不同的存储桶中，并且哈希映射将无法找到键值对（因为它将在同一个存储桶中查找）。

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

Answer 2

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

两个不相等的对象具有相同的哈希码是完全合法的。它被HashMap用作“第一遍过滤器”，以便映射可以快速找到具有指定键的可能条目。然后测试具有相同哈希码的键与指定键的相等性。

您不希望要求两个不相等的对象不能具有相同的哈希码，否则这会将您限制为 2³² 个可能的对象。 （这也意味着不同的类型甚至不能使用对象的字段来生成哈希代码，因为其他类可以生成相同的哈希值。）

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，则字段 next 引用另一个 Entry 对象。

有时可能会发生两个不同对象的哈希码相同的情况。在这种情况下，两个对象将被保存在一个桶中，并以链表的形式呈现。
入口点是最近添加的对象。该对象通过 next 字段引用另一个对象，依此类推。最后一个条目引用null。

当您使用默认构造函数创建 HashMap 时，

HashMap hashMap = new HashMap();

将创建大小为 16 且默认负载平衡为 0.75 的数组。

添加新的键值

1. 对
2. 计算键的哈希码 计算应放置元素的位置 hash % (arrayLength-1) （桶号）
3. 如果您尝试使用已存在的键添加值已保存在HashMap中，然后值被覆盖。
4. 否则元素将被添加到桶中。

如果存储桶已经至少有一个元素，则会添加一个新元素并将其放置在存储桶的第一个位置。它的 next 字段引用旧元素。

删除

1. 计算给定键的哈希码
2. 计算桶数 hash % (arrayLength-1)
3. 获取桶中第一个 Entry 对象的引用，并通过 equals 方法迭代给定桶中的所有条目。最终我们会找到正确的Entry。
   如果没有找到所需的元素，则返回null

Answer 4

您可以在 http://javarevisited.blogspot.com/2011/ 找到优秀的信息02/how-hashmap-works-in-java.html

总结一下：

HashMap 的工作原理是哈希

put(key, value): HashMap 将键和值对象存储为 Map.Entry。 Hashmap应用hashcode(key)来获取桶。如果发生碰撞，HashMap使用LinkedList来存储对象。

get(key)： HashMap 使用 Key 对象的哈希码来查找存储桶位置，然后调用keys.equals() 方法来识别 LinkedList 中正确的节点，并返回 Java HashMap 中该键的关联值对象。

Answer 5

以下是 HashMap 机制的粗略描述，适用于 Java 8 版本，（可能与 Java 6 略有不同）。

---

数据结构

• 哈希表
  哈希值是通过 key 上的 hash() 计算出来的，它决定给定 key 使用哈希表的哪个存储桶。
• 链接列表 （单个）
  当桶中的元素数量较少时，使用单链表。
• 红黑树
  当桶中的元素数量较多时，使用红黑树。

---

类（内部）

• Map.Entry
  表示映射中的单个实体，即键/值实体。

• HashMap.Node
  节点的链表版本。

  它可以代表：

  • 哈希桶。
    因为它有一个哈希属性。
  • 单链表中的一个节点，（因此也是链表的头）。
• HashMap.TreeNode
  节点的树版本。

---

字段（内部）

• Node[] 表
  桶表（链表的头部）。
  如果存储桶不包含元素，则它为空，因此只占用引用的空间。
• 设置条目集
  实体集。
• 整数大小
  实体数量。
• 浮动负载因子
  指示在调整大小之前允许哈希表的填充程度。
• 整数阈值
  下一个要调整大小的尺寸。
  公式：阈值 = 容量 * loadFactor

---

方法（内部）

• int hash(key)
  通过key计算hash。

• 如何将哈希映射到存储桶？
  使用以下逻辑：

  <块引用>

  static int hashToBucket(int tableSize, int hash) {
      返回(tableSize - 1) &哈希；
  }
  

---

关于容量

在哈希表中，容量指的是桶的数量，可以从table.length中获取。
也可以通过 threshold 和 loadFactor 计算，因此不需要定义为类字段。

获取有效容量

---

可以通过capacity()操作

• 通过key查找实体。
  首先通过哈希值找到桶，然后循环链表或搜索排序树。
• 使用键添加实体。
  首先根据key的哈希值找到bucket。
  然后尝试找到该值：
  • 如果找到，请替换该值。
  • 否则，在链表开头添加一个新节点，或插入到排序树中。
• 调整大小
  当达到threshold时，会将哈希表的容量加倍（table.length），然后对所有元素执行重新哈希以重建表。
  这可能是一项昂贵的操作。

---

性能

• 获取&把
  时间复杂度为 O(1)，因为：
  • 通过数组索引访问存储桶，因此 O(1)。
  • 每个桶中的链表长度都很小，因此可以看作O(1)。
  • 树的大小也受到限制，因为会扩展容量和存储空间。当元素计数增加时重新哈希，因此可以将其视为 O(1)，而不是 O(log N)。

Answer 6

哈希码确定哈希图要检查的存储桶。如果存储桶中存在多个对象，则执行线性搜索来查找存储桶中的哪一项等于所需的项目（使用 equals()）方法。

换句话说，如果你有一个完美的 hashcode，那么 hashmap 的访问是恒定的，你将永远不需要迭代存储桶（从技术上讲，你还必须有 MAX_INT 存储桶，Java 实现可能会在同一个存储桶中共享一些哈希码来减少空间需求）。如果你有最差的哈希码（总是返回相同的数字），那么你的哈希映射访问就会变成线性，因为你必须搜索映射中的每个项目（它们都在同一个存储桶中）才能得到你想要的东西。

大多数时候，编写良好的哈希码并不完美，但足够独特，可以为您提供或多或少的持续访问。

Answer 7

你在第三点上就错了。两个条目可以具有相同的哈希码，但不能相等。看一下 HashMap.从 OpenJdk 获取。您可以看到它检查哈希值是否相等以及键是否相等。如果第三点为真，那么就没有必要检查密钥是否相等。哈希码在键之前进行比较，因为前者的比较效率更高。

如果您有兴趣了解更多相关信息，请查看 Wikipedia 文章 Open解决冲突解决，我相信这是 OpenJdk 实现使用的机制。该机制与其他答案之一提到的“桶”方法略有不同。

Answer 8

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 方法。因为不同的哈希码保证对象中的内容不同。

    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 9

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

2个相等的对象------>他们有相同的哈希码

2 个对象具有相同的哈希码 ----xxxxx-->他们不相等

HashMap 中的 Java 8 更新 -

您在代码中执行此操作 -

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

因此，假设您的哈希码返回了两个键 "old" 和 "very -old" 是一样的。然后会发生什么。

myHashMap 是一个 HashMap，假设最初您没有指定它的容量。因此，每个 java 的默认容量是 16。所以现在，只要您使用 new 关键字初始化 hashmap，它就会创建 16 个存储桶。现在，当你执行第一个语句时 -

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

然后计算 "old" 的哈希码，并且因为哈希码也可能是非常大的整数，所以，java内部这样做 - （哈希是这里的哈希码并且>> ;> 是右移），

hash XOR hash >>> 16

因此为了给出更大的图片，它将返回一些索引，该索引介于 0 到 15 之间。现在您的键值对 "old" 和 "old -value" 将被转换Entry 对象的键和值实例变量。然后这个entry对象就会被存储到bucket中，或者你可以说在某个特定的索引处，这个entry对象会被存储。

仅供参考- Entry 是 Map 接口中的一个类 - Map.Entry，

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

当您执行下一条语句时，现在具有这些签名/定义 -

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

并且 "very-old" 给出与 "old"< 相同的哈希码/code>，所以这个新的键值对再次被发送到相同的索引或相同的桶。但由于这个桶不为空，那么 Entry 对象的 next 变量就用来存储这个新的键值对。

对于具有相同哈希码的每个对象，这将存储为链表，但 TRIEFY_THRESHOLD 指定为值 6。因此，达到此值后，链表将转换为平衡树（红黑树），其中第一个元素为根。

Answer 10

每个 Entry 对象代表键值对。如果一个桶有超过 1 个 Entry，那么 Field next 会引用其他 Entry 对象。

有时可能会发生两个不同对象的 hashCode 相同的情况。在这种情况下，2 个对象将保存在一个存储桶中，并以 LinkedList 的形式呈现。入口点是最近添加的对象。该对象引用具有下一个字段的其他对象，依此类推。最后一个条目引用 null。
当您使用默认构造函数创建 HashMap 时，

将创建大小为 16 且默认负载平衡为 0.75 的数组。

（来源）

Answer 11

哈希映射的工作原理是哈希

HashMap get(Key k) 方法在键对象上调用 hashCode 方法，并将返回的 hashValue 应用于其自己的静态哈希函数，以找到存储键和值的存储桶位置（支持数组）一个名为 Entry (Map.Entry) 的嵌套类。因此，从上一行可以得出结论，键和值都以 Entry 对象的形式存储在存储桶中。所以认为桶中只存储价值是不正确的，也不会给面试官留下好印象。

• 每当我们在 HashMap 对象上调用 get(Key k) 方法时。首先它检查 key 是否为 null 。请注意，HashMap 中只能有一个空键。

如果 key 为 null ，则 Null 键总是映射到哈希 0，因此索引 0。

如果 key 不为 null 那么，它将在 key 对象上调用 hashfunction，请参见上面方法中的第 4 行，即 key.hashCode() ，因此在 key 之后.hashCode() 返回 hashValue，第 4 行看起来像

            int hash = hash(hashValue)

现在，它将返回的 hashValue 应用到自己的哈希函数中。

我们可能想知道为什么我们要使用 hash(hashValue) 再次计算哈希值。答案是它可以防御质量较差的哈希函数。

现在，最终的哈希值用于查找存储 Entry 对象的存储桶位置。 Entry对象像这样存储在bucket中（hash,key,value,bucketindex）

Answer 12

我不会详细介绍 HashMap 的工作原理，但会给出一个示例，以便我们可以通过将其与现实联系起来来记住 HashMap 的工作原理。

我们有Key、Value、HashCode和bucket。

有时，我们会将它们与以下内容相关联：

• Bucket ->社会
• 哈希码 ->协会地址（始终唯一）
• 值 ->社会
• 钥匙中的一所房子 ->房屋地址。

使用 Map.get(key) ：

Stevie 想要去他朋友（Josse）的家，他住在 VIP 社团的别墅里，假设是 JavaLovers Society。
Josse 的地址是他的 SSN（每个人都不同）。
有一个索引，我们可以根据 SSN 找到协会的名称。
这个索引可以被认为是一种找出HashCode的算法。

• SSN 协会名称
• 92313(Josse's) -- JavaLovers
• 13214 -- AngularJSLovers
• 98080 -- JavaLovers
• 53808 -- BiologyLovers

---

1. 这个 SSN(key) 首先给我们一个 HashCode（来自索引表），它只是协会的名称。
2. 现在，多个房屋可以在同一个社会中，因此HashCode可以通用。
3. 假设，社会对于两栋房子来说是通用的，我们如何识别我们要去哪栋房子，是的，通过使用（SSN）键，它只是房子地址

使用 Map.put(key,Value)

这发现通过查找 HashCode 找到适合该 Value 的社会，然后存储该值。

我希望这会有所帮助，并且可以进行修改。

Answer 13

记住这里对 hashmap 结构的解释，也许有人可以解释 Baeldung 上的以下段落：-

Java 有几种 Map 接口的实现，每一种都有自己的特殊性。

但是，现有的 Java 核心 Map 实现都不允许 Map 处理单个键的多个值。

正如我们所见，如果我们尝试为同一个键插入两个值，第二个值将被存储，而第一个将被删除。

它还将被返回（通过 put(K key, V value) 方法的每个正确实现）：

Map<String, String> map = new HashMap<>();
assertThat(map.put("key1", "value1")).isEqualTo(null);
assertThat(map.put("key1", "value2")).isEqualTo("value1");
assertThat(map.get("key1")).isEqualTo("value2");

Answer 14

这将是一个很长的答案，喝一杯并继续阅读......

散列就是在内存中存储一​​个可以更快读取和写入的键值对。 它将键存储在数组中，将值存储在 LinkedList 中。

假设我想存储 4 个键值对 -

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

因此，为了存储键，我们需要一个包含 4 个元素的数组。现在如何将这 4 个键之一映射到 4 个数组索引 (0,1,2,3)？

因此java找到各个键的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) . 

e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

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

为什么java将它与31相乘？

这是因为，31 是一个奇素数，其形式为 2^5 – 1 。并且奇素数减少了哈希冲突的几率

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

答案是，哈希代码％（数组长度-1） 。因此，在我们的例子中，“girl” 映射到 (3173020 % 3) = 1。这是数组的第二个元素。

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

HashCollision - 如果您尝试使用描述的公式查找键 “misused” 和 “horsemints” 的 hasHCode在上面您会看到两者都给了我们相同的1069518484。哇啊！！吸取的教训——

2 个相等的对象必须具有相同的 hashCode，但不能保证是否
hashCode 匹配则对象相等。所以它应该存储
与存储桶 1 的“misused”和“horsemints”相对应的两个值
（1069518484%3）。

现在哈希映射看起来像 –

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

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

但是，等一下，等一下。该linkedList中有3个值对应数组索引1，它如何找出哪个是键“horsemints”的值？

实际上我撒谎了，当我说 HashMap 只是将值存储在 LinkedList 中时。

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

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”进行比较，当找到一个时，它只返回它的值。

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

Answer 15

俗话说，一图胜千言。我说：有些代码胜过1000字。这是HashMap的源代码。 Get方法：

/**
     * 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 数组（“桶”数组）的大小。

首先，尝试将其作为该“桶”中的第一个元素。如果已经有一个元素，则将一个新节点追加到列表中。