Java 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");

哈希映射工作的原理是使用哈希。

HashMap get(Key k) 方法会调用关键对象的 hashCode 方法，并将返回的哈希值应用于其自身的静态哈希函数，以查找存储为名为 Entry（Map.Entry）的嵌套类形式的键和值的桶位置（后备数组）。因此，你已经得出结论，从前面的一行中可以看出，键和值都以 Entry 对象的形式存储在桶中。因此认为只有值存储在桶中是不正确的，也不能给面试官留下良好的印象。

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

如果键为 null，则 null 键始终映射到哈希值 0，因此索引为 0。

如果键不为空，则会在键对象上调用哈希函数，参见上述方法的第 4 行即 key.hashCode()，因此在 key.hashCode() 返回哈希值后，第 4 行看起来像：

            int hash = hash(hashValue)

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

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

现在，最终的哈希值用于查找存储 Entry 对象的桶位置。Entry 对象以以下方式存储在桶中（hash、key、value、bucketindex）。

我不会详细解释HashMap的工作原理，但会通过一个例子来说明它的工作方式，以便我们可以将其与现实联系起来并记住它的工作原理。
我们有键、值、哈希码和桶。
暂时，我们将把它们分别与以下内容相关联：
- 桶 -> 一个社区 - 哈希码 -> 社区的地址（始终唯一） - 值 -> 社区中的一所房子 - 键 -> 房子的地址
使用Map.get(key)：
Stevie想去他朋友Josse的别墅拜访，这个别墅位于一个VIP社区中，假设这个社区叫JavaLovers。Josse的地址是他的社会安全号码（每个人的都不同）。维护了一个索引，根据社会安全号码找出社区的名称。这个索引可以被视为查找哈希码的算法。
- 社会安全号码 社区名称 - 92313（Josse） -- JavaLovers - 13214 -- AngularJSLovers - 98080 -- JavaLovers - 53808 -- BiologyLovers

---

1. 这个社会安全号码（key）首先给我们一个哈希码（来自索引表），它代表的是社区的名称。
2. 现在，多个房屋可以位于同一社区，因此哈希码可能是共同的。
3. 假设，两个房屋共用一个社区，我们如何确定我们要去哪个房屋？是的，通过使用（SSN）密钥，即房屋地址。

使用Map.put(key,Value)

这将通过查找哈希码为该值找到合适的社区，然后存储该值。

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

这将是一个较长的回答，请拿杯饮料慢慢阅读...

哈希是关于在内存中存储可以更快地读写的键值对。 它将键存储在数组中，将值存储在链表中。

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

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

为了存储键，我们需要一个由4个元素组成的数组。现在我该如何将这4个键中的一个映射到4个数组索引（0、1、2、3）中？

Java通过找到每个键的哈希码并将其映射到特定的数组索引来实现。哈希码公式为 -

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中。

哈希冲突- 如果您尝试使用上面描述的公式查找键“misused”和“horsemints”的hasHCode，您会发现两者都给出相同的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会快速找到它的哈希码，对其进行模运算，并开始在LinkedList对应的索引1中搜索其值。因此，我们无需搜索所有4个数组索引，从而使数据访问更快。

但是，请等一下。那个LinkedList对应的Array索引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”进行比较，当找到一个时，它只返回其值。

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

正如俗话所说，一张图片胜过千言万语。我认为：一些代码胜过千言万语。这是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 数组（“桶”数组）的大小。

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