解释一下HashMap的put方法的执行逻辑

八股文_Java集合面试题 0 82

参考回答**

在 HashMap 中，put 方法的核心逻辑是将一个键值对插入到 HashMap 中。其执行流程主要包括以下步骤：

计算键的哈希值
根据 hashCode() 方法计算键的哈希值，然后通过哈希值定位键值对应该存储的桶（bucket）。
定位桶位置
使用哈希值对数组的长度取模，确定键值对存储的位置。
检查冲突（是否有相同哈希值的键）
- 如果桶为空，直接插入键值对。
- 如果桶中已有元素（发生哈希冲突），遍历桶中的链表或树结构：
  - 如果找到相同的键（通过 equals 方法判断），则替换旧值为新值。
  - 如果未找到相同的键，则将键值对插入到链表末尾或树中。
树化检查
如果链表长度超过阈值（默认 8），链表会转换为红黑树以提高性能。
扩容检查
如果插入新键值对后，HashMap 的实际元素数量超过了负载因子阈值（loadFactor），会触发扩容（默认将容量翻倍）。

详细讲解与拓展

为了更清楚理解 put 方法的执行逻辑，以下是 HashMap 的源码解析和示例代码。

1. 源码解析

HashMap 的 put 方法主要逻辑在以下几个部分：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

通过 hash() 方法计算哈希值，避免直接使用 key.hashCode() 导致的性能问题（如哈希冲突集中）。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希值扰动函数：h ^ (h >>> 16)，目的是减少哈希冲突，均匀分布哈希值。

然后核心逻辑在 putVal() 方法中：

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;
        // 如果哈希值相等并且 key 相等，更新值
        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) 
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果 key 存在，替换旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果超过扩容阈值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

2. 分步详细解释

计算桶的位置
```
i = (n - 1) & hash
```
Java
使用 (n-1) & hash 来定位键值对在数组中的位置，这种方式比取模运算更高效。
插入元素

如果桶为空，直接在该位置插入新节点。
如果桶中已有元素，则遍历链表或树：
- 如果找到相同键，直接更新值。
- 如果没有相同键，插入新节点到链表末尾，或者按红黑树规则插入。

树化

当链表长度超过 TREEIFY_THRESHOLD（默认为 8），会将链表转化为红黑树，提升查询和插入效率。

扩容

当插入后实际元素数量超过阈值 threshold 时（threshold = capacity * loadFactor），会触发扩容。
默认情况下，loadFactor = 0.75。

3. 示例代码

以下代码展示了 HashMap 的 put 方法的典型使用：

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();

        // 插入键值对
        map.put("key1", "value1");
        map.put("key2", "value2");

        // 更新值
        map.put("key1", "newValue1");

        // 获取值
        System.out.println("key1 -> " + map.get("key1")); // 输出: key1 -> newValue1
        System.out.println("key2 -> " + map.get("key2")); // 输出: key2 -> value2

        // 插入 null 键
        map.put(null, "nullValue");
        System.out.println("null -> " + map.get(null)); // 输出: null -> nullValue
    }
}

4. 扩展知识

链表到红黑树的转换
- 默认链表长度超过 8 时转换为红黑树，减少链表查找时间复杂度（从 O(n) 降到 O(log n)）。
扩容机制
- 扩容时，容量翻倍，原数组中的键值对会被重新分配到新的桶中。扩容会消耗大量性能，因此建议在初始化时尽量设置合适的容量。
哈希冲突的处理
- HashMap 使用链表和红黑树处理哈希冲突。
- 一个好的哈希函数能显著减少冲突，提高性能。
线程安全问题
- HashMap 是非线程安全的。如果在多线程环境下使用，建议使用 ConcurrentHashMap 或加锁机制。