面试题：Java中的HashMap的工作原理是什么？

HashMap 是 Java 中最常用的数据结构之一，它基于哈希表实现，提供了高效的键值对存储和查找功能。以下是 HashMap 的工作原理详解：

1. 基本结构

HashMap 由数组和链表（或红黑树）组成。
数组中的每个元素称为“桶”（Bucket），每个桶存储一个链表或红黑树的头节点。
每个节点是一个 Entry（Java 8 之前）或 Node（Java 8 及以后）对象，包含键、值、哈希值以及指向下一个节点的指针。

2. 核心概念

哈希函数：
- HashMap 使用键的 hashCode() 方法计算哈希值。
- 哈希值通过进一步计算（如取模运算）映射到数组的索引位置。
桶（Bucket）：
- 数组的每个位置称为一个桶，用于存储链表或红黑树的头节点。
链表和红黑树：
- 当哈希冲突发生时（即多个键映射到同一个桶），HashMap 使用链表存储冲突的键值对。
- 当链表长度超过阈值（默认是 8）时，链表会转换为红黑树，以提高查找效率。

3. 工作原理

1. 插入元素（put 操作）

计算键的哈希值：调用键的 hashCode() 方法，并通过 HashMap 内部的哈希函数计算哈希值。
确定桶的位置：通过 (n - 1) & hash 计算索引（n 是数组长度）。
检查桶是否为空：
- 如果为空，直接插入新节点。
- 如果不为空，遍历链表或红黑树：
  - 如果找到相同的键，更新值。
  - 如果未找到相同的键，插入新节点。
如果链表长度超过阈值（默认是 8），将链表转换为红黑树。
如果数组容量超过负载因子（默认是 0.75），触发扩容（resize）。

2. 查找元素（get 操作）

计算键的哈希值。
确定桶的位置。
遍历链表或红黑树，查找键相等的节点。
如果找到，返回对应的值；否则返回 null。

3. 扩容（resize 操作）

当元素数量超过 容量 * 负载因子 时，HashMap 会扩容。
扩容时，数组长度变为原来的 2 倍，并重新计算每个元素的桶位置。
扩容是一个耗时的操作，因为需要重新哈希所有元素。

4. 关键参数

初始容量（Initial Capacity）：
- 默认是 16，可以在创建 HashMap 时指定。
负载因子（Load Factor）：
- 默认是 0.75，表示当元素数量达到容量的 75% 时触发扩容。
阈值（Threshold）：
- 链表转换为红黑树的阈值，默认是 8。
树化阈值（Treeify Threshold）：
- 当链表长度超过 8 时，链表会转换为红黑树。

5. 哈希冲突解决

链表法：
- 当多个键映射到同一个桶时，HashMap 使用链表存储冲突的键值对。
红黑树法：
- 当链表长度超过阈值时，链表会转换为红黑树，以提高查找效率（从 O(n) 提升到 O(log n)）。

6. 性能分析

平均时间复杂度：
- 插入、删除、查找操作的平均时间复杂度为 O(1)。
最坏时间复杂度：
- 如果所有键都映射到同一个桶，时间复杂度退化为 O(n)（链表）或 O(log n)（红黑树）。

7. 代码示例

import java.util.HashMap;

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

        // 插入元素
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        // 查找元素
        System.out.println("Apple: " + map.get("Apple")); // 输出 1

        // 删除元素
        map.remove("Banana");

        // 遍历元素
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

8. 总结

特性	说明
底层结构	数组 + 链表/红黑树
哈希冲突解决	链表法 + 红黑树法
插入/删除/查找	平均 O(1)，最坏 O(n) 或 O(log n)
扩容机制	当元素数量超过 `容量 * 负载因子` 时，数组长度翻倍并重新哈希
线程安全性	非线程安全，多线程环境下需使用 `ConcurrentHashMap` 或同步包装类
适用场景	需要高效键值对存储和查找的场景

THE END

Java 集合类