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) {
// 创建一个HashMap
Map<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
// 遍历HashMap
for (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();
}
}
4. 使用 Hashtable
Hashtable
是 Java 早期提供的线程安全的哈希表实现。Hashtable
的所有方法都是同步的(使用 synchronized
关键字)。但是HashTable性能较差,因为所有操作都需要竞争同一把锁。已经过时,不推荐使用。
小结
在实际开发中,ConcurrentHashMap
是最推荐的方式,因为它既能保证线程安全,又能提供优异的性能。如果并发需求不高,可以使用 Collections.synchronizedMap
。