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

#1 楼

哈希图的工作方式如下（略微简化了一点，但它说明了基本机制）：

它具有多个“存储桶”，用于存储键值对。每个存储桶有一个唯一的数字-这就是识别存储桶的方式。当您将键值对放入地图时，哈希图将查看键的哈希码，并将该对存储在其标识符为键的哈希码的存储桶中。例如：密钥的哈希码是235->该对存储在存储区编号235中。（请注意，一个存储区可以存储多于一对的键值对）。

查找一个哈希图中的值，通过给它一个键，它将首先查看您提供的键的哈希码。哈希图随后将查看相应的存储桶，然后将您提供的密钥与存储桶中所有对的密钥进行比较，方法是将它们与equals()进行比较。

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

通过上述机制，您还可以了解对hashCode()和equals()的键方法有什么要求：


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

#2 楼

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

两个不相等的对象具有相同的哈希码是完全合法的。 HashMap将其用作“首过过滤器”，以便地图可以使用指定的键快速找到可能的条目。然后测试具有相同哈希码的键与指定键的相等性。

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

#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对象代表一个键值对。如果存储桶有多个next，则字段Entry会引用另一个Entry对象。有时，两个不同对象的哈希码是相同的。在这种情况下，两个对象将保存在一个存储桶中，并显示为链接列表。
入口点是最近添加的对象。该对象引用带有next字段的另一个对象，依此类推。最后一个条目是null。

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

HashMap hashMap = new HashMap();

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

添加新的键值对


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

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

删除


计算给定键的哈希码
计算存储桶号hash % (arrayLength-1)

获取存储桶中第一个Entry对象的引用，并通过equals方法遍历给定存储桶中的所有条目。最终，我们将找到正确的Entry。
如果找不到所需的元素，请返回null

#4 楼

您可以在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 Object的哈希码找出存储区位置，然后调用keys.equals（）方法在LinkedList中标识正确的节点，并在Java HashMap中返回该键的关联值对象。

#5 楼

这是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)。

#6 楼

哈希码确定要检查哈希图的存储桶。如果存储桶中有多个对象，则将执行线性搜索以找到存储桶中哪个项目等于所需的项（使用equals()）方法。换句话说，如果您有一个完美的哈希码，则哈希映射访问是恒定的，您将不必遍历存储桶（从技术上讲，您还必须具有MAX_INT存储桶​​，Java实现可以在同一存储桶中共享一些哈希码以减少空间需求）。如果您拥有最差的哈希码（总是返回相同的数字），那么您的哈希图访问将变为线性，因为您必须搜索地图中的每个项目（它们都在同一个存储桶中）才能获得所需的内容。

在大多数情况下，编写良好的哈希码并不完美，但其唯一性足以使您或多或少地获得恒定的访问权限。

#7 楼

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

如果您想了解更多有关此的知识，请查看Wikipedia上有关“开放式寻址冲突解决”的文章，我相信这是OpenJdk实现使用的机制。该机制与其他答案之一提到的“存储桶”方法有细微的区别。

#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方法。因为对象中的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. 

#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对象的键和值实例变量。然后该入口对象将存储在存储桶中，或者可以说在特定索引处将存储该入口对象。
FYI- Entry是Map接口Map.Entry中的类，具有这些签名/ definition

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指定。因此，到达此列表后，链表将转换为以第一个元素为根的平衡树（红黑树）。

#10 楼

每个Entry对象代表键/值对。如果存储桶中有多个Entry，则next字段将引用其他Entry对象。

有时可能会发生两个不同对象的hashCode相同的情况。在这种情况下，将2个对象保存在一个存储桶中，并显示为LinkedList。入口点是最近添加的对象。该对象引用具有下一个字段的其他对象，因此也称为一个。最后一个条目指的是null。
使用默认构造函数创建HashMap时，会创建大小为16且默认负载均衡为0.75的数组。



（来源）

#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）计算hashvalue。答案是：它可以防止质量差的哈希函数。

现在，最终哈希值用于查找存储Entry对象的存储桶位置。入口对象像这样存储在存储桶中（哈希，键，值，bucketindex）

#12 楼

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

我们有Key，Value，HashCode和bucket。

有时，我们会将它们与以下各项相关：


桶->社团
哈希码->社团的地址（始终唯一）
值->社会中的房屋
钥匙->房屋地址。

使用Map.get（key）：

Stevie想要进入他的朋友（Josse）的房子住在VIP协会的别墅里，那就叫JavaLovers Society。
Josse的地址是他的SSN（每个人的地址都不同）。
维护了一个索引，我们在其中基于SSN找出协会的名称。
该索引可以被认为是一种算法找出HashCode。


SSN协会名称
92313（Josse's）-JavaLovers
13214-AngularJSLovers
53808-BiologyLovers




此SSN（键）首先给我们提供了一个HashCode（来自索引表），它不过是协会的名字。
现在，多个房屋可以在同一个社会中，因此HashCode可以是常见的。
假设，该社会对于两所房屋是相同的，那么我们如何通过使用（ SSN）钥匙，不过是房屋地址

使用Map.put（key，Value）

这可以通过找到HashCode，然后找到值已存储。

我希望这对您有所帮助，开放修改。

#13 楼

答案很长，请喝一杯然后继续阅读...

散列就是将键值对存储在内存中，以便可以更快地进行读写。它将键存储在数组中，将值存储在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形式的奇数素数。而且奇质数减少了哈希冲突的可能性


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

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

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

HashCollision-如果尝试使用公式查找键hasHCode和“misused”中的“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 – 

现在，如果有人试图找到键“horsemints”的值，则Java会迅速找到它的hashCode，对其进行模块化，然后开始在对应的index 1的LinkedList中搜索它的值。因此，通过这种方式，我们无需搜索所有4个数组索引，从而可以更快地访问数据。

，等等，一秒钟。在该linkedList对应的数组索引1中有3个值，它如何找出键“ 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”进行比较，当找到一个键时只是返回它的值。

希望您在阅读它时很开心:)

#14 楼

据说一张图片值1000字。我说：有些代码胜过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数组（“存储桶”的数组）的大小。

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