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

Question

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

javahashmaphashcodehash-function

266

根据我的理解：

两个对象拥有相同的哈希码是完全合法的。
如果两个对象使用equals()方法得出相等的结果，则它们具有相同的哈希码。
如果两个对象不相等，则它们不能拥有相同的哈希码。

我的理解正确吗？

如果我的理解正确，那么我有以下问题： HashMap在内部使用对象的哈希码。那么，如果两个对象可以拥有相同的哈希码，那么HashMap如何跟踪它所使用的键呢？

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

- akshay

43

记录一下：#1和#2是正确的，#3是错误的：两个不相等的对象可能具有相同的哈希码。 - Joachim Sauer

8

1号和3号相互矛盾。 - Delfic

实际上，如果不遵循第二点，则equals()的实现（或者可以说是hashCode()）是不正确的。 - Joachim Sauer

15个回答

99

你的第三个断言是错误的。

两个不相等的对象具有相同的哈希码是完全合法的。这被HashMap用作“第一次筛选”，以便该映射可以快速找到具有指定键的可能条目。然后，使用相同哈希码的键将与指定键进行相等性测试。

如果要求两个不相等的对象不能具有相同的哈希码，那么这将限制您只能拥有2³²个可能的对象。（这也意味着不同类型甚至无法使用对象的字段生成哈希码，因为其他类可以生成相同的哈希码。）

- Jon Skeet

7

你是怎么得出有2^32种可能的对象的？ - Geek

13

我晚了，但对于那些仍在疑惑的人：Java中的哈希码是一个整数，而一个整数有2^32个可能的值。 - xeruf

86

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 对象表示一个键值对。如果一个 bucket 中有多个 Entry，则字段 next 将指向另一个 Entry 对象。

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

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

HashMap hashMap = new HashMap();

该数组的大小为16，负载均衡默认为0.75。

添加一个新的键值对

计算键的哈希码
计算元素应该放置的位置（桶编号）hash % (arrayLength-1)
如果尝试添加已经存在于HashMap中的键的值，则该值会被覆盖。
否则，元素将添加到桶中。

如果桶已经有至少一个元素，新元素将被添加并放置在桶的第一位置。它的 next 字段指向旧元素。

删除

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

- Sergii Shevchyk

4

这个错误的部分是 hash % (arrayLength-1) ，正确的应该是 hash % arrayLength。但实际上在 Java 中，它是 hash & (arrayLength-1)。这是因为 Java 使用二的幂次方(2^n)作为数组长度，取最低的 n 位来计算哈希值。 - weston

我认为这不是一个实体对象数组，而是一个LinkedList/Tree数组。每个树内部都有实体对象。 - Mudit bhaintwal

@shevchyk 为什么我们要存储键和哈希值？它们有什么用处？这样不是浪费内存吗？ - roottraveller

HashSet 内部使用 HashMap。HashMap 的添加和删除规则是否适用于 HashSet？ - overexchange

2

@weston 不仅如此，hashCode是一个int类型的变量，当然可以是负数，在负数上进行模运算将会得到一个负数。 - Eugene

41

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

总结：

HashMap基于哈希原理工作。 put(key, value)：HashMap将key和value对象都存储为Map.Entry。HashMap应用hashcode(key)获取桶。如果发生冲突，HashMap会使用LinkedList存储对象。

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

- Abhijit Gaikwad

4

我觉得Jasper提供的答案更好，我感觉这篇博客更偏向于应对面试，而不是理解概念。 - Narendra N

@NarendraN 我同意你的观点。 - Abhijit Gaikwad

23

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

数据结构

哈希表
通过在键上执行hash()来计算哈希值，并决定对于给定的键使用哈希表的哪个桶。
链表 （单向）
当一个桶中的元素数量很少时，使用单向链表。
红黑树
当一个桶中的元素数量很大时，使用红黑树。

类（内部）

Map.Entry
表示映射中的单个实体，即键/值实体。
HashMap.Node
节点的链表版本。

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

字段（内部）

Node[] table
哈希桶表，（链表头）。
如果一个桶不包含元素，则为null，因此只占用参考空间。
Set<Map.Entry> entrySet 实体的集合。
int size
实体数量。
float loadFactor
指示允许哈希表在调整大小之前填满多少比例。
int threshold
下一次调整大小的大小。
公式：threshold = capacity * loadFactor

方法（内部）

int hash(key)
通过键计算哈希。

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

static int hashToBucket(int tableSize, int hash) {
    return (tableSize - 1) & hash;
}

关于容量

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

可以通过capacity()获取有效容量。

操作

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

性能

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

- Eric

请举一个例子说明时间复杂度为O(1)。 - jsingh

@jsroyal 这可能更清楚地解释了复杂性：https://en.wikipedia.org/wiki/Hash_table。但简而言之：找到目标桶是O(1)，因为您可以通过数组中的索引找到它；然后，在一个桶内，元素数量很少且平均情况下是一个常数，尽管整个哈希表中的元素总数很多，因此在桶内查找目标元素也是O(1)；因此，O(1) + O(1) = O(1)。 - Eric

16

哈希码（hashcode）决定了哈希表中要检查哪个桶。如果一个桶里有多个对象，那么就会执行线性查找来找到与所需对象相等的项（使用 equals() 方法）。

换句话说，如果你拥有完美的哈希码，则哈希表访问是恒定的，你永远不必遍历桶（严格来说，你还需要有 MAX_INT 个桶，Java 实现可能会在同一个桶中共享一些哈希码以减少空间需求）。如果您的哈希码最差（始终返回相同的数字），则哈希表访问变为线性，因为您必须搜索映射中的每个项目（它们都位于同一个桶中）才能获得所需内容。

大部分情况下，好的哈希码并不完美，但足够唯一，可以给您提供或多或少恒定的访问。

- Pace

11

你在第三个观点上有误。两个条目可以拥有相同的哈希码，但不相等。看一下OpenJdk中HashMap.get的实现。你会发现它检查哈希值和键是否相等。如果第三个观点是正确的，那么检查键是否相等就是不必要的。哈希码比键更有效率，所以先进行哈希码比较。

如果你对此感兴趣，可以查看开放地址冲突解决的维基百科文章，我认为这是OpenJdk实现使用的机制。这种机制与其他答案提到的“桶”方法略有不同。

- Leif Wickland

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方法将为这两个对象生成不同的哈希码(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.

- Tajinder Singh

6

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

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

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

Java 8中HashMap的更新-

你可以在你的代码中执行以下操作-

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

假设您的哈希码对于两个键 "old" 和 "very-old" 返回相同。那么会发生什么。

myHashMap 是一个 HashMap，假设最初您没有指定其容量。因此，默认容量为 16。因此，当您使用 new 关键字初始化 hashmap 时，它创建了 16 个桶。现在当您执行第一条语句时-

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

然后计算"old"的哈希码，由于哈希码可能是非常大的整数，所以Java内部执行了以下操作 - （这里的hash是哈希码，>>>是右移）

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"的哈希值相同，因此这个新的键值对再次被发送到相同的索引或桶中。但由于此桶不为空，因此Entry对象的next变量用于存储此新的键值对。

对于每个具有相同哈希码的对象，它们都将被存储为链接列表，但指定了TRIEFY_THRESHOLD的值为6。因此在达到此值后，将把链接列表转换为平衡树（红黑树），其中第一个元素作为根节点。

- anubhs

很棒的答案 (y) - Sudhanshu Gaur

2

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

有时候，两个不同对象的哈希码相同。在这种情况下，这两个对象将保存在一个桶中，并被表示为LinkedList。最近添加的对象是entry point。该对象引用其他对象的next字段，以此类推。最后一个entry引用null。当您使用默认构造函数创建HashMap时，

数组的大小为16，并且默认负载平衡为0.75。

enter image description here

（来源）

- Premraj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jesper · Accepted Answer

一个哈希表的工作原理如下（稍微简化了一些，但它揭示了基本机制）：

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

当你通过给它一个键来在哈希表中查找一个值时，它首先会查看你给出的键的哈希码。然后哈希表将查找相应的桶，然后通过使用equals()方法将你给出的键与桶中所有对的键进行比较。

现在你可以看到，这对于在映射中查找键值对非常高效：通过键的哈希码，哈希表立即知道在哪个桶中查找，因此它只需要针对该桶中的内容进行测试。

从上面的机制可以看出，键的hashCode()和equals()方法需要满足什么要求：

- 如果两个键相同（equals()将它们比较返回true），则它们的hashCode()方法必须返回相同的数字。如果键违反此规则，则相等的键可能存储在不同的桶中，哈希表将无法找到键值对（因为它会查找同一个桶）。 - 如果两个键不同，那么它们的哈希码是否相同并不重要。如果它们的哈希码相同，它们将存储在同一个桶中，在这种情况下，哈希表将使用equals()方法来区分它们。

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

添加一个新的键值对

删除

数据结构

类 （内部）

字段 （内部）

方法 （内部）

关于容量

操作

性能

类（内部）

字段（内部）

方法（内部）