HashMap 是 Java 集合框架中最常用的数据结构之一，其底层实现结合了 数组、链表 和 红黑树，以提供高效的增删查改操作。以下是其核心实现原理的详细解析。
- 数据结构
数组 (Bucket Array): HashMap 使用一个数组 Node<K,V>[] table 存储键值对，每个位置称为一个“桶”。
链表 (Linked List): 当多个键的哈希值映射到同一桶时，使用链表存储冲突的键值对。
红黑树 (Red-Black Tree): 在 JDK 1.8 中，当链表长度超过 8 且数组容量 ≥ 64 时，链表会转换为红黑树以优化查询性能。
- 核心操作
插入 (Put)
计算哈希值: 调用 hashCode() 方法并通过 (h = key.hashCode()) ^ (h >>> 16) 进行二次处理，减少冲突。
定位桶位置: 使用 (n - 1) & hash 计算数组索引。
处理冲突: 如果桶为空，直接插入新节点。 如果存在冲突： 链表：遍历链表，若键已存在则覆盖值，否则尾插法添加节点。 红黑树：按红黑树规则插入节点。
扩容检查: 若元素数量超过阈值（capacity × loadFactor），触发扩容。
查询 (Get)
根据键计算哈希值和桶索引。
定位到对应桶： 若为空，返回 null。 若为链表或红黑树，逐一查找匹配的键。
- 扩容机制
当元素数量超过阈值时，创建新数组（容量为原来的两倍）。
将旧数组中的元素重新分配到新数组中，位置要么保持不变，要么移动到 i + oldCap。
- 优化设计
默认初始容量：16
默认负载因子：0.75
链表转红黑树阈值：8
红黑树退化为链表阈值：6
5. 使用建议
设置合理的初始容量以减少扩容次数：
Map<String, Object> map = new HashMap<>(1000 / 0.75 + 1);
复制
确保键对象不可变，并正确重写 hashCode() 和 equals() 方法。
多线程环境下使用线程安全的集合，如 ConcurrentHashMap。