您的位置: 首页  >  文章  >  如何线程安全的使用HashMap

如何线程安全的使用HashMap

分类: 文章 • 2025-04-17 20:37:22

进入正题，在周二面试时，一面的面试官有问到 HashMap 是否是线程安全的，如何在线程安全的前提下使用 HashMap,其实也就是HashMap，Hashtable，ConcurrentHashMap 和 synchronized Map 的原理和区别。当时有些紧张只是简单说了下HashMap不是线程安全的；Hashtable 线程安全，但效率低，因为是 Hashtable 是使用 synchronized 的，所有线程竞争同一把锁；而 ConcurrentHashMap 不仅线程安全而且效率高，因为它包含一个 segment 数组，将数据分段存储，给每一段数据配一把锁，也就是所谓的锁分段技术。当时忘记了 synchronized Map 和解释一下 HashMap 为什么线程不安全。面试结束后问了下面试官哪里有些不足，面试官说上面这个问题的回答算过关，但可以在深入一些或者自己动手尝试一下。so~~~虽然拿到了 offer，但还是再整理一下，不能得过且过啊。

为什么HashMap是线程不安全的

总说 HashMap 是线程不安全的，不安全的，不安全的，那么到底为什么它是线程不安全的呢？要回答这个问题就要先来简单了解一下 HashMap 源码中的使用的存储结构(这里引用的是 Java 8 的源码，与7是不一样的)和它的扩容机制。

HashMap的内部存储结构

下面是 HashMap 使用的存储结构:

 

1

2

3

4

5

6

7

8

 
 

transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

 

可以看到 HashMap 内部存储使用了一个 Node 数组(默认大小是16)，而 Node 类包含一个类型为 Node 的 next 的变量，也就是相当于一个链表，所有根据 hash 值计算的 bucket 一样的 key 会存储到同一个链表里(即产生了冲突)，大概就是下面图的样子(顺便推荐个在线画图的网站Creately)。
如何线程安全的使用HashMapHashMap内部存储结果

需要注意的是，在 Java 8 中如果 hash 值相同的 key 数量大于指定值(默认是8)时使用平衡树来代替链表，这会将get()方法的性能从O(n)提高到O(logn)。具体的可以看我的另一篇博客Java 8中HashMap和LinkedHashMap如何解决冲突。

HashMap的自动扩容机制

 

HashMap 内部的 Node 数组默认的大小是16，假设有100万个元素，那么最好的情况下每个 hash 桶里都有62500个元素，这时get(),put(),remove()等方法效率都会降低。为了解决这个问题，HashMap 提供了自动扩容机制，当元素个数达到数组大小 loadFactor 后会扩大数组的大小，在默认情况下，数组大小为16，loadFactor 为0.75，也就是说当 HashMap 中的元素超过16\0.75=12时，会把数组大小扩展为2*16=32，并且重新计算每个元素在新数组中的位置。如下图所示(图片来源，权侵删)。



如何线程安全的使用HashMap

如何线程安全的使用HashMap

从图中可以看到没扩容前，获取 EntryE 需要遍历5个元素，扩容之后只需要2次。

为什么线程不安全

个人觉得 HashMap 在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小* loadFactor ，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失。
关于 HashMap 线程不安全这一点，《Java并发编程的艺术》一书中是这样说的：

HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Node 链表形成环形数据结构，一旦形成环形数据结构，Node 的 next 节点永远不为空，就会在获取 Node 时产生死循环。

哇塞，听上去si不si好神奇，居然会产生死循环。。。。 google 了一下，才知道死循环并不是发生在 put 操作时，而是发生在扩容时。详细的解释可以看下面几篇博客：

如何线程安全的使用HashMap

了解了 HashMap 为什么线程不安全，那现在看看如何线程安全的使用 HashMap。这个无非就是以下三种方式：

  • Hashtable
  • ConcurrentHashMap
  • Synchronized Map

例子：

 

  1. //Hashtable

  2. Map<String, String> hashtable = new Hashtable<>();

  3. //synchronizedMap

  4. Map<String, String> synchronizedHashMap = Collections.synchronizedMap(new HashMap<String, String>());

  5. //ConcurrentHashMap

  6. Map<String, String> concurrentHashMap = new ConcurrentHashMap<>();

 

 

依次来看看。

Hashtable

先稍微吐槽一下，为啥命名不是 HashTable 啊，看着好难受不管了就装作它叫HashTable 吧。这货已经不常用了，就简单说说吧。HashTable 源码中是使用 synchronized 来保证线程安全的，比如下面的 get 方法和 put 方法：

 

 

  1. public synchronized V get(Object key) {

  2. // 省略实现

  3. }

  4. public synchronized V put(K key, V value) {

  5. // 省略实现

  6. }

 

所以当一个线程访问 HashTable 的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。举个例子，当一个线程使用 put 方法时，另一个线程不但不可以使用 put 方法，连 get 方法都不可以，好霸道啊！！！so~~，效率很低，现在基本不会选择它了。

ConcurrentHashMap

ConcurrentHashMap (以下简称CHM)是 JUC 包中的一个类，Spring 的源码中有很多使用 CHM 的地方。之前已经翻译过一篇关于 ConcurrentHashMap 的博客，如何在java中使用ConcurrentHashMap，里面介绍了 CHM 在 Java 中的实现，CHM 的一些重要特性和什么情况下应该使用 CHM。需要注意的是，上面博客是基于 Java 7 的，和8有区别,在8中 CHM 摒弃了 Segment（锁段）的概念，而是启用了一种全新的方式实现,利用 CAS 算法，有时间会重新总结一下。

SynchronizedMap

看了一下源码，SynchronizedMap 的实现还是很简单的。

 

  1. // synchronizedMap方法

  2. public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {

  3. return new SynchronizedMap<>(m);

  4. }

  5. // SynchronizedMap类

  6. private static class SynchronizedMap<K,V>

  7. implements Map<K,V>, Serializable {

  8. private static final long serialVersionUID = 1978198479659022715L;

  9. private final Map<K,V> m; // Backing Map

  10. final Object mutex; // Object on which to synchronize

  11. SynchronizedMap(Map<K,V> m) {

  12. this.m = Objects.requireNonNull(m);

  13. mutex = this;

  14. }

  15. SynchronizedMap(Map<K,V> m, Object mutex) {

  16. this.m = m;

  17. this.mutex = mutex;

  18. }

  19. public int size() {

  20. synchronized (mutex) {return m.size();}

  21. }

  22. public boolean isEmpty() {

  23. synchronized (mutex) {return m.isEmpty();}

  24. }

  25. public boolean containsKey(Object key) {

  26. synchronized (mutex) {return m.containsKey(key);}

  27. }

  28. public boolean containsValue(Object value) {

  29. synchronized (mutex) {return m.containsValue(value);}

  30. }

  31. public V get(Object key) {

  32. synchronized (mutex) {return m.get(key);}

  33. }

  34. public V put(K key, V value) {

  35. synchronized (mutex) {return m.put(key, value);}

  36. }

  37. public V remove(Object key) {

  38. synchronized (mutex) {return m.remove(key);}

  39. }

  40. // 省略其他方法

  41. }

 

从源码中可以看出调用 synchronizedMap() 方法后会返回一个 SynchronizedMap 类的对象，而在 SynchronizedMap 类中使用了 synchronized 同步关键字来保证对 Map 的操作是线程安全的。

性能对比

这是要靠数据说话的时代，所以不能只靠嘴说 CHM 快，它就快了。写个测试用例，实际的比较一下这三种方式的效率(源码来源)，下面的代码分别通过三种方式创建 Map 对象，使用 ExecutorService 来并发运行5个线程，每个线程添加/获取500K个元素。

 

  1. public class CrunchifyConcurrentHashMapVsSynchronizedMap {

  2. public final static int THREAD_POOL_SIZE = 5;

  3. public static Map<String, Integer> crunchifyHashTableObject = null;

  4. public static Map<String, Integer> crunchifySynchronizedMapObject = null;

  5. public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;

  6. public static void main(String[] args) throws InterruptedException {

  7. // Test with Hashtable Object

  8. crunchifyHashTableObject = new Hashtable<>();

  9. crunchifyPerformTest(crunchifyHashTableObject);

  10. // Test with synchronizedMap Object

  11. crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());

  12. crunchifyPerformTest(crunchifySynchronizedMapObject);

  13. // Test with ConcurrentHashMap Object

  14. crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();

  15. crunchifyPerformTest(crunchifyConcurrentHashMapObject);

  16. }

  17. public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {

  18. System.out.println("Test started for: " + crunchifyThreads.getClass());

  19. long averageTime = 0;

  20. for (int i = 0; i < 5; i++) {

  21. long startTime = System.nanoTime();

  22. ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);

  23. for (int j = 0; j < THREAD_POOL_SIZE; j++) {

  24. crunchifyExServer.execute(new Runnable() {

  25. @SuppressWarnings("unused")

  26. @Override

  27. public void run() {

  28. for (int i = 0; i < 500000; i++) {

  29. Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);

  30. // Retrieve value. We are not using it anywhere

  31. Integer crunchifyValue = crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));

  32. // Put value

  33. crunchifyThreads.put(String.valueOf(crunchifyRandomNumber), crunchifyRandomNumber);

  34. }

  35. }

  36. });

  37. }

  38. // Make sure executor stops

  39. crunchifyExServer.shutdown();

  40. // Blocks until all tasks have completed execution after a shutdown request

  41. crunchifyExServer.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);

  42. long entTime = System.nanoTime();

  43. long totalTime = (entTime - startTime) / 1000000L;

  44. averageTime += totalTime;

  45. System.out.println("2500K entried added/retrieved in " + totalTime + " ms");

  46. }

  47. System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");

  48. }

  49. }


测试结果：

 

 

  1. Test started for: class java.util.Hashtable

  2. 2500K entried added/retrieved in 2018 ms

  3. 2500K entried added/retrieved in 1746 ms

  4. 2500K entried added/retrieved in 1806 ms

  5. 2500K entried added/retrieved in 1801 ms

  6. 2500K entried added/retrieved in 1804 ms

  7. For class java.util.Hashtable the average time is 1835 ms

  8. Test started for: class java.util.Collections$SynchronizedMap

  9. 2500K entried added/retrieved in 3041 ms

  10. 2500K entried added/retrieved in 1690 ms

  11. 2500K entried added/retrieved in 1740 ms

  12. 2500K entried added/retrieved in 1649 ms

  13. 2500K entried added/retrieved in 1696 ms

  14. For class java.util.Collections$SynchronizedMap the average time is 1963 ms

  15. Test started for: class java.util.concurrent.ConcurrentHashMap

  16. 2500K entried added/retrieved in 738 ms

  17. 2500K entried added/retrieved in 696 ms

  18. 2500K entried added/retrieved in 548 ms

  19. 2500K entried added/retrieved in 1447 ms

  20. 2500K entried added/retrieved in 531 ms

  21. For class java.util.concurrent.ConcurrentHashMap the average time is 792 ms

https://blog.****.net/u010842515/article/details/68490245?utm_source=blogxgwz4

相关推荐