【Java】HashMap
HashMap 是 Java 中最常用的集合之一，它是一种键值对存储的数据结构，可以根据键来快速访问对应的值。以下是对 HashMap 的总结：
- HashMap 采用
数组+链表/红黑树的存储结构，能够在O(1)的时间复杂度内实现元素的添加、删除、查找等操作。 - HashMap 是线程不安全的，因此在多线程环境下需要使用ConcurrentHashMap来保证线程安全。
- HashMap 的扩容机制是通过扩大数组容量和重新计算 hash 值来实现的，扩容时需要重新计算所有元素的 hash 值，因此在元素较多时扩容会影响性能。
- 在 Java 8 中，HashMap 的实现引入了拉链法、树化等机制来优化大量元素存储的情况，进一步提升了性能。
- HashMap 中的 key 是唯一的，如果要存储重复的 key，则后面的值会覆盖前面的值。
- HashMap 的初始容量和加载因子都可以设置，初始容量表示数组的初始大小，加载因子表示数组的填充因子。一般情况下，初始容量为 16，加载因子为 0.75。
- HashMap 在遍历时是无序的，因此如果需要有序遍历，可以使用TreeMap。
HashMap 是 Java 中最常用的数据结构之一，它是一个 基于哈希表（Hash Table）实现的键值对映射（Map），属于 Java 集合框架中的 java.util.Map 接口的实现类。
介绍：
HashMap是一个可以存储键值对、通过键快速查找值的容器，允许null键和null值，不保证顺序。
基本特点：
| 特性 | 说明 |
|---|---|
| 键值对存储 | 每个元素是一个 (key, value) 映射。 |
| 键唯一 | 每个键只能出现一次，值可以重复。 |
| 基于哈希表实现 | 通过 key.hashCode() 决定数据在数组中的位置。 |
| 访问速度快 | 理论上查找、插入都是常数时间 O(1)。 |
| 线程不安全 | 多线程场景下需用 ConcurrentHashMap 或加锁。 |
| 不保证顺序 | 插入顺序可能和遍历顺序不一致。 |
| 允许 null 键和值 | 键最多只能有一个 null，值可以有多个 null。 |
内部结构（JDK 8 之后）：
HashMap 的核心结构是一个数组 + 链表 + 红黑树：
- 每个桶（bucket）是一个
Node链表或红黑树。 - 当多个键的哈希值落在同一个桶中（即哈希冲突），它们会组成一个链表。
- 当链表长度超过 8 且数组长度 >= 64，链表会转为红黑树，提高查找效率。
工作原理（简化流程）：
-
计算键的 hash 值：
每一个对象都直接或者间接的继承了Object类，所以每个对象都有Object父类的方法，在计算hash值时使用了hashcode()方法。int hash = key.hashCode(); -
定位桶位置（数组索引）：
index = (n - 1) & hash; // n 是数组长度 -
处理冲突（链表或树）：
- 如果该位置已经有元素，使用
equals()判断是否是同一个键：- 是：覆盖旧值。
- 否：挂在后面（链表或树中）。
- 如果该位置已经有元素，使用
示例代码：
import java.util.HashMap;public class Demo {public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<>();map.put("apple", 3);map.put("banana", 2);map.put("orange", 5);System.out.println(map.get("apple")); // 输出 3map.put("apple", 10); // 覆盖旧值System.out.println(map.get("apple")); // 输出 10}
}
常用方法：
| 方法 | 说明 |
|---|---|
put(K key, V value) | 添加或更新键值对 |
get(Object key) | 获取指定键的值 |
remove(Object key) | 删除指定键值对 |
containsKey(Object key) | 是否包含某个键 |
containsValue(Object value) | 是否包含某个值 |
keySet() | 获取所有键 |
values() | 获取所有值 |
entrySet() | 获取所有键值对 |
线程安全注意：
HashMap 本身是线程不安全的，如果你在多线程环境中使用，推荐：
ConcurrentHashMap（高性能并发替代品）Collections.synchronizedMap(map)（包装成线程安全）
原因：
- 多线程下扩容会死循环
- 多线程下put会导致元素消失，同时出现put操作，后来的覆盖旧的。
- put和get并发导致get到null
很好，这个问题问得深入了：HashMap 是怎么具体存放 key 和 value 的？
元素存放
在 HashMap 中，每一个键值对（K 和 V）被封装成一个内部类对象 Node（或 Entry），并存放在数组中的“桶”里，桶内部可能是链表或红黑树结构。
具体数据结构（JDK 8）：
transient Node<K,V>[] table;
这个 table 就是核心数据结构 —— 哈希桶数组，每个元素是一个 Node<K, V> 对象，或链表/红黑树的头节点。
Node<K, V> 源码结构（JDK 8）：
static class Node<K,V> implements Map.Entry<K,V> {final int hash; // 计算好的 hash 值，避免重复计算final K key; // 键V value; // 值Node<K,V> next; // 指向下一个节点（链表）
}
所以每个节点（键值对）都包含：
| 字段 | 作用 |
|---|---|
hash | 键的哈希值，用于定位桶索引和快速比较 |
key | 键 |
value | 值 |
next | 链表指针（用于处理哈希冲突） |
存放流程示意：
比如你调用：
map.put("apple", 100);
- 计算
"apple"的哈希值：hash = "apple".hashCode()。 - 计算索引位置（桶位置）：
index = (n - 1) & hash。 - 如果该桶为空，直接存一个
Node。 - 如果该桶已有节点：
- 判断 key 是否重复（用
equals()比较）：- 是：覆盖
value。 - 否：加到链表后（或红黑树中）。
- 是：覆盖
- 判断 key 是否重复（用
链表 / 红黑树结构：
当哈希冲突（多个 key 落到同一个桶）严重时：
- 如果桶中节点数 ≤ 8：使用链表。
- 如果 > 8 且数组长度 ≥ 64：转成红黑树（提升查询效率 O(log n)）。
- 如果冲突减少、数量下降，会退化回链表。
举个例子：
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
在内存中可能是：
table[4] -> Node("a", 1) -> Node("c", 3)
table[7] -> Node("b", 2)
说明：
"a"和"c"发生哈希冲突，挂在同一个桶（索引 4）中，用链表串起来。"b"没有冲突，直接存到桶 7。
小细节：
Node是静态内部类，不会持有外部 HashMap 的引用，避免内存泄漏。value是可变的；key和hash一旦确定不可变（作为定位依据）。
总结：
HashMap 内部通过一个数组
Node<K,V>[]存放所有键值对，Node包含 key、value、hash、next，用链表/红黑树处理冲突，确保查找和插入效率。
是否想让我用图示来直观展示哈希冲突和存储结构？