Java HashMap 是非线程安全的。在多线程条件下,容易导致死循环,具体表现为CPU使用率100%。因此多线程环境下保证 HashMap 的线程安全性,主要有如下几种方法:
- 使用 java.util.Hashtable 类,此类是线程安全的。
- 使用 java.util.concurrent.ConcurrentHashMap,此类是线程安全的。
- 使用 java.util.Collections.synchronizedMap() 方法包装 HashMap object,得到线程安全的Map,并在此Map上进行操作。
- 自己在程序的关键方法或者代码段加锁,保证安全性,当然这是严重的不推荐。
为什么 HashMap 非线程安全, 可以参考大神陈皓(weibo账号:左耳朵耗子)在他自己技术网站Coolshell上的文章,写的非常详细。文章链接(直通车):http://coolshell.cn/articles/9606.html
这里重点分析下上面列举的几种方法实现并行安全性的原理:
(一)java.util.Hashtable类:类的主要数据结构如下:
/** * The hash table data. */ private transient Entry[] table; private static class Entry<K,V> implements Map.Entry<K,V> { int hash; K key; V value; Entry<K,V> next;
可见,Hashtable 的实现是一个数组,每个数组元素是一个LinkList结构,因此类的数据实际上保存在一个散列表中。这个实现和 HashMap 的实现是一致的。数据结构如下:
那么Hashtable如何保证线程安全性的哪?下面是 Hashtable的源码:
public synchronized V get(Object key) { Entry tab[] = table; …… //此处省略,具体的实现请参考 jdk实现 } public synchronized V put(K key, V value) { …… //具体实现省略,请参考jdk实现 } public synchronized V remove(Object key) { …… //具体实现省略,请参考jdk实现 } public synchronized void putAll(Map<? extends K, ? extends V> t) { for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) put(e.getKey(), e.getValue()); } public synchronized void clear() { …… //具体实现省略,请参考jdk实现 }
上面是 Hashtable 提供的几个主要方法,包括 get(), put(), remove() 等。注意到每个方法本身都是 synchronized 的,不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性,但是也大大的降低了执行效率。因此是不推荐的。
(二)使用 java.util.Collections.synchronizedMap(Map<K,V>) 方法进行封装。 方法源代码如下:
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { return new SynchronizedMap<K,V>(m); } private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable { // use serialVersionUID from JDK 1.2.2 for interoperability private static final long serialVersionUID = 1978198479659022715L; private final Map<K,V> m; // Backing Map final Object mutex; // Object on which to synchronize SynchronizedMap(Map<K,V> m) { if (m==null) throw new NullPointerException(); this.m = m; mutex = this; } SynchronizedMap(Map<K,V> m, Object mutex) { this.m = m; this.mutex = mutex; } public int size() { synchronized(mutex) {return m.size();} } public boolean isEmpty(){ synchronized(mutex) {return m.isEmpty();} } public boolean containsKey(Object key) { synchronized(mutex) {return m.containsKey(key);} }
从实现源代码可以发现,其封装的本质和 Hashtable 的实现是完全一致的,即对原Map本身的方法进行加锁,加锁的对象或者为外部指定共享对象mutex,或者为包装后的线程安全的Map本身。Hashtable 可以理解为 SynchronizedMap mutex=null 时候的特殊情况。因此这种同步方式的执行效率也是很低的。
既然已经有了Hashtable, 为什么还需要Collections 提供的这种静态方法包装哪?很简单,这种包装是Java Collection Framework提供的统一接口,除了用于 HashMap 外,还可以用于其他的Map。当然 除了对Map进行封装,Collections工具类还提供了对 Collection(比如Set,List)的线程安全实现封装方法,具体请参考 java.util.Colletions 实现,其原理和 SynchronizedMap 是一致的。
(三) 使用 java.util.concurrent.ConcurrentHashMap 类。并发编程大师 Doug Lea 出品,绝对精品。这是 HashMap 的线程安全版,同 Hashtable 相比,ConcurrentHashMap 不仅保证了访问的线程安全性,而且在效率上有较大的提高。
ConcurrentHashMap的数据结构如下(引用图片地址http://www.yupoo.com/photos/goldendoc/81556254/):
可以看出,相对 HashMap 和 Hashtable, ConcurrentHashMap 增加了Segment 层,每个Segment 原理上等同于一个 Hashtable, ConcurrentHashMap 为 Segment 的数组。下面是 ConcurrentHashMap 的 put 和 get 方法:
final Segment<K,V> segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask]; } public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); } public V get(Object key) { int hash = hash(key.hashCode()); return segmentFor(hash).get(key, hash); }
向 ConcurrentHashMap 中插入数据或者读取数据,首先都要讲相应的 Key 映射到对应的 Segment,因此不用锁定整个类, 只要对单个的 Segment 操作进行上锁操作就可以了。理论上如果有 n 个 Segment,那么最多可以同时支持 n 个线程的并发访问,从而大大提高了并发访问的效率。另外 rehash() 操作也是对单个的 Segment 进行的,所以由 Map 中的数据量增加导致的 rehash 的成本也是比较低的。
单个 Segment 的进行数据操作的源码如下:
V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c = count; if (c++ > threshold) // ensure capacity rehash(); …… // 代码省略,具体请查看源码 } finally { unlock(); } } V replace(K key, int hash, V newValue) { lock(); try { HashEntry<K,V> e = getFirst(hash); …… // 代码省略,具体请查看源码 } finally { unlock(); } }
可见对 单个的 Segment 进行的数据更新操作都是 加锁的,从而能够保证线程的安全性。
ConcurrentHashMap 的更具体实现和分析见(直通车) http://www.iteye.com/topic/1103980, 非常详细。
几种线程同步实现方法的效率比较,可以参考(直通车) http://blog.sina.com.cn/s/blog_734a77160100yku1.html
相关推荐
HashMap是Java编程中常用的数据结构,它是一种基于哈希表实现的键值对存储容器,遵循Map接口。HashMap内部使用了“链表散列”的数据结构,即将数组和链表结合,以解决哈希冲突问题。 HashMap的实现原理是通过哈希...
在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...
1. **非同步**:`HashMap`不是线程安全的,因此在多线程环境下不建议直接使用,可以考虑使用`Collections.synchronizedMap()`方法将其包装为同步的,或者使用`ConcurrentHashMap`。 2. **无序性**:`HashMap`中的...
- 集合框架:掌握ArrayList、LinkedList、HashMap、HashSet等容器的使用及其原理。 - 泛型:了解泛型的作用,如何使用泛型类和泛型方法。 - I/O流:理解流的概念,学习字节流和字符流,以及缓冲流的使用。 2. **...
1. 非线程安全:HashMap不是线程安全的,这意味着在多线程环境下,不推荐在未进行同步控制的情况下直接使用HashMap。如果需要线程安全的数据结构,可以考虑使用ConcurrentHashMap。 2. 可变容量:HashMap的容量可以...
- 线程安全:Java中的HashMap不是线程安全的,如果在多线程环境下使用,需要考虑同步机制,如使用`Collections.synchronizedMap()`或者使用`ConcurrentHashMap`。 - 空值处理:键或值为null的情况需要特殊处理,...
- **实现方法**: - 使用`synchronized`关键字标记方法或代码块。 - 使用`ReentrantLock`等显式锁。 ##### 5. Java线程的管理 - **线程调度**: - 系统自动调度线程,根据线程优先级和系统负载决定执行顺序。 - **...
首先,`HashMap`是Java中最基本的非线程安全的散列映射容器。它基于哈希表实现,提供O(1)的平均时间复杂度进行插入、删除和查找操作。在Java 7中,`HashMap`内部由数组和链表构成,当多个键映射到同一个哈希桶时,会...
1. 线程安全:HashMap不是线程安全的,而HashTable是线程安全的。 2. 性能:HashMap的性能比HashTable好,因为HashMap使用数组和链表来存储键值对,而HashTable使用链表来存储键值对。 3. null键:HashMap允许存放...
而ConcurrentHashMap是线程安全的HashMap实现,它在Java 7中采用了分段锁(Segment)的设计,每个Segment实际上是一个小型的HashMap,通过锁来确保并发安全。put过程包括: 1. 确保Segment初始化,如果需要则创建新...
5. **集合框架**:学习ArrayList、LinkedList、HashMap等数据结构,了解它们的工作原理和应用场景。 6. **IO流**:Java的输入输出流系统是处理文件和网络数据的重要工具,包括文件流、字符流、对象流和网络流等。 ...
Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 在Java集合中,HashMap是一个常用的数据结构,它基于Map接口实现,元素以键值对的方式存储,并且允许使用null键和null值。由于key不允许...
HashMap支持键和值为null,同时是非线程安全的,即其方法不是同步的。 2. HashMap存储结构 JDK 7.0中的HashMap使用数组加链表的存储结构。数组中的每个元素对应一个链表,链表用于解决哈希冲突。但是当链表长度过大...
在Java编程语言中,`HashMap`和`TreeMap`是两种常见的`Map`接口实现,它们各自具有不同的特性和用途。这两个数据结构都是用来存储键值对的数据结构,但它们的内部实现机制和性能特点有所不同。 HashMap是基于哈希表...
4. **集合框架**:Java集合框架包括List、Set和Map接口,以及ArrayList、LinkedList、HashSet、HashMap等实现类。熟练掌握它们的特性和使用场景能提高代码效率。 5. **输入/输出流**:I/O流用于处理数据的读写,...
HashMap 是 Java 中最常用的集合类之一,它是基于哈希表数据结构实现的,提供快速的存取操作。在深入理解 HashMap 的实现原理之前,我们先要明白哈希表的基本概念。哈希表是一种通过哈希函数将键(Key)映射到数组...
总的来说,理解HashMap的工作原理,特别是putVal()方法中的hash计算和对象作为Key的要求,对于优化Java程序的性能和避免并发问题至关重要。在实际开发中,我们需要根据具体需求来合理设计Key的hashCode()和equals()...
如果需要在并发环境中使用,可以考虑使用ConcurrentHashMap,它是Java并发包提供的线程安全的哈希表实现。 6. 空键值对:HashMap允许键或值为null,但最多只能有一个键为null,且null键映射的值没有特定的位置,...
- **Map**:HashMap、TreeMap、LinkedHashMap的工作机制,特别是HashMap的线程不安全问题及其解决方案。 - **集合接口与实现**:了解Collection、Iterable、List、Set、Map等接口,以及它们各自的实现类。 3. **...