Java集合 - HashMap

HashMap 是 Java 集合框架中的一个重要类，位于 java.util 包中。它实现了 Map 接口，基于哈希表的数据结构来存储键值对（key-value pairs）。HashMap 允许使用 null 作为键和值，并且是非同步的（非线程安全的），null键在HashMap中只能存在一个。

1. 主要特点

键值对存储：HashMap 存储的是键值对，每个键对应一个值。
无序：HashMap 不保证元素的顺序，即插入顺序和遍历顺序不一定一致。
允许 null 键和 null 值：HashMap 允许一个 null 键和多个 null 值。
非线程安全：HashMap 不是线程安全的，如果在多线程环境中使用，需要外部同步。
基于哈希表：HashMap 使用哈希表来存储数据，通过哈希函数计算键的哈希值，并将其映射到表中的某个位置。

2. 核心方法

put(K key, V value)：将指定的键值对插入到 HashMap 中。如果键已经存在，则更新对应的值。
get(Object key)：返回指定键所映射的值，如果键不存在则返回 null。
remove(Object key)：删除指定键对应的键值对。
containsKey(Object key)：判断 HashMap 中是否包含指定的键。
containsValue(Object value)：判断 HashMap 中是否包含指定的值。
keySet()：返回 HashMap 中所有键的集合。
values()：返回 HashMap 中所有值的集合。
entrySet()：返回 HashMap 中所有键值对的集合。

import java.util.HashMap;
import java.util.Map;public class HashMapExample {public static void main(String[] args) {// 创建一个HashMapMap<String, Integer> map = new HashMap<>();// 添加键值对map.put("Alice", 25);map.put("Bob", 30);map.put("Charlie", 35);// 获取值System.out.println("Alice's age: " + map.get("Alice")); // 输出: 25// 遍历HashMapfor (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " is " + entry.getValue() + " years old.");}// 删除键值对map.remove("Bob");System.out.println("After removing Bob: " + map);// 判断是否包含键System.out.println("Contains key 'Alice': " + map.containsKey("Alice")); // 输出: true// 判断是否包含值System.out.println("Contains value 35: " + map.containsValue(35)); // 输出: true}
}

3. 底层原理

HashMap的底层使用hash表,即散列表数据结构(数组 + 链表或红黑树)

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标

2. 存储时，如果出现hash值相同的key，此时有两种情况。

a. 如果key相同，则覆盖原始值；

b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中

3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

当两个键的哈希值映射到同一个桶时，会发生哈希冲突。HashMap通过以下方式解决冲突：

链表：在 Java 8 之前，冲突的键值对以链表形式存储。
红黑树：在 Java 8 及以后，当链表长度超过阈值（默认是 8）时，链表会转换为红黑树，以提高查找效率。

在 Java 8 中，HashMap 引入了红黑树来优化性能。当链表长度超过阈值（默认是 8）时，链表会转换为红黑树；当红黑树的节点数减少到一定阈值（默认是 6）时，红黑树会退化为链表。

3.1 为什么引入红黑树？

链表的时间复杂度是 O(n)，而红黑树的时间复杂度是 O(log n)。
当哈希冲突严重时，红黑树可以显著提高查找效率。

4. 扩容机制

HashMap的容量是动态调整的，当元素数量超过当前容量与负载因子的乘积时，会触发扩容（resize）。

4.1 负载因子

负载因子（load factor）是一个浮点数，默认是 0.75。
它表示 HashMap 在扩容之前可以达到的填充比例。例如，默认容量是 16，负载因子是 0.75，则当元素数量超过 16 * 0.75 = 12 时，会触发扩容。

4.2 扩容过程

创建一个新的数组，容量是原数组的 2 倍。
将原数组中的键值对重新哈希到新数组中。
重新哈希时，键值对可能会被分配到新的位置。

5. 线程安全

HashMap是非线程安全的(相对比线程安全的HashTable)，如果要在线程安全的情况下使用HashMap，有下面几种方式。

1. 使用`Collections的方法synchronizedMap`

Java 提供了 Collections.synchronizedMap 方法，可以将 HashMap 包装成一个线程安全的 Map。

// 创建一个普通的HashMap
Map<String, Integer> map = new HashMap<>();// 使用Collections.synchronizedMap包装HashMap
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);

Collections.synchronizedMap 返回一个同步的 Map，内部通过一个全局锁（mutex）来保证线程安全。所有对 Map 的操作（如 put、get、remove 等）都会被同步。

2. 使用 `ConcurrentHashMap`

ConcurrentHashMap 是 Java 提供的线程安全的哈希表实现，专门为高并发场景设计。

// 创建一个ConcurrentHashMap
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

ConcurrentHashMap 使用分段锁（Java 7）或 CAS + synchronized（Java 8 及以后）来实现线程安全。在 Java 8 中，ConcurrentHashMap 采用了更细粒度的锁机制，每个桶（bucket）独立加锁，减少了锁竞争。

3. 手动加锁

如果需要对 HashMap 进行更灵活的控制，可以手动加锁（ReentrantLock 或 synchronized）。

private final Map<String, Integer> map = new HashMap<>();
private final Lock lock = new ReentrantLock();public void put(String key, Integer value) {lock.lock();try {map.put(key, value);} finally {lock.unlock();}
}public Integer get(String key) {lock.lock();try {return map.get(key);} finally {lock.unlock();}
}