java.util.Map是使用最广泛的Java集合之一,其实现HashMap是线程不安全的,HashTable则是基于synchronized的线程安全(效率很低),另一个完全同步的Map是Collections.sychronizedMap,它也不是很高效。如果想要线程安全并且在高并发的情况下保持高吞吐量,就需要使用java.util.concurrent.ConcurrentMap,它是从java1.5开始新增的的Map实现。
1、ConcurrentMap接口
ConcurrentMap继承了java.util.Map接口,是一个能够支持并发访问的集合接口,它提供了一种代码结构,用来指引解决数据读写时的线程安全问题。ConcurrentMap重写了Map中的很多default方法,用来实现线程安全和内存一致性的原子操作。很多的默认实现被重写,不允许使用null作为key/value。
ConcurrentMap在原有java.util.Map接口基础上又新提供了4种方法,进一步扩展了原有Map的功能:
public interface ConcurrentMap<K, V> extends Map<K, V> {
//插入元素
V putIfAbsent(K key, V value);
//移除元素
boolean remove(Object key, Object value);
//替换元素
boolean replace(K key, V oldValue, V newValue);
//替换元素
V replace(K key, V value);
}
- putIfAbsent:与原有put方法不同的是,putIfAbsent方法中如果插入的key相同,则不替换原有的value值;
- remove:与原有remove方法不同的是,新remove方法中增加了对value的判断,如果要删除的key–value不能与Map中原有的key–value对应上,则不会删除该元素;
- replace(K,V,V):增加了对value值的判断,如果key–oldValue能与Map中原有的key–value对应上,才进行替换操作;
- replace(K,V):与上面的replace不同的是,此replace不会对Map中原有的key–value进行比较,如果key存在则直接替换;
其实,对于ConcurrentMap来说,我们更关注Map本身的操作,在并发情况下是如何实现数据安全的。在java.util.concurrent包中,ConcurrentMap的实现类主要以ConcurrentHashMap为主。
2、ConcurrentHashMap
ConcurrentHashMap是一个开箱即用的ConcurrentMap的实现类,解决了使用hashMap线程不安全,使用HashTable低效的问题,是一个高效的高并发线程安全类。内部采用了分段锁的设计,有效地避免了锁的竞争压力。对于每个分段,ConcurrentHashmap采用final和内存可见修饰符volatile关键字实现。
为了获得更好的性能,它将数据分成多个bucket,放在一个数组里,数组是一张哈希表,就是以前的段,在更新的时候使用CAS(compareAndSwap)。
-
bucket是懒加载的,在第一次插入的时候。每个bucket都会被独立的锁上,锁住桶中的第一个node。读操作是不会被阻塞,并且更新的资源争夺也被限制了。
-
段的数量是由访问表的线程决定的,所以段的更新,一次只有一个线程。
-
在java8之前,段的数量是由访问的线程数量决定的,一个线程一个段。这就是为什么它的构造函数和HashMap比起来多了concurrencyLevel的参数,它就是估算的线程数量,另外两个参数和HashMap相同。从java8开始,构造函数只是为了和之前的版本兼容,保留了下来,他们只能影响初始的map的大小。
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
2.1 分段锁
锁分段技术,就是将数据分成一段一段的存储,然后给每段数据都配一把锁,当一个线程占用锁访问其中一段数据的时候,其他段的数据也能被其他线程访问。有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这就需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。这里“按顺序”是很重要的,否则极有可能出现死锁,在ConcurrentHashMap内部,段数组是final的,并且其成员变量实际上也是final的,但是,仅仅是将数组声明为final的并不保证数组成员也是final的,这需要实现上的保证。这些设计可以确保不会出现死锁,因为获得锁的顺序是固定的。
- HashTable在高并发环境下使用时会导致多个线程争抢一把锁,出现锁竞争激烈的情况,从而使得效率低下,而ConcurrentHashMap的解决方案则是将其内部使用段(segment)的概念,每个段都可以视为是一个hashTable,相当于有16把不同的锁,当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。
2.2 数据结构
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock,在ConcurrentHashMap里扮演锁的角色,HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组,Segment的结构和HashMap类似,是一种数组和链表结构, 一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素, 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得它对应的Segment锁。
两个线程给不同的区段Segment中添加元素,这种情况可以并发。所以ConcurrentHashMap可以保证线程安全(多个线程操作同一个Segment,则某个线程给此Segment加锁,另一个线程只能阻塞)并且在一定程度上提交线程并发执行效率。两个线程给同一个区段Segment中添加元素,这种情况不可以并发,在JDK1.8进行了改进。
- 底层结构依然是依靠数组+链表
- 默认初始容量是16,默认加载因子是0.75,默认扩容是增加1倍
- 底层采用了分桶锁(分段锁)机制保证并发性,在后续的版本中,在分段锁的基础上引入了读写锁的机制:
- a.读锁:允许多个线程同时读,不允许线程写
- b.写锁:允许一个线程写,不允许线程读
- 在JDK1.8中,采用了无锁算法CAS(Compare and Swap - 比较和交换)
- 在JDK1.8中,引入红黑树机制。当桶中的元素个数超过8个的时候,可能会扭转成一棵树,但实际上桶的容量大于64才转换;如果桶中元素个数不足7个,则会扭转回链表 - 扭转成红黑树的最小容量为64。
- 解决问题:桶数越多,扩容的几率就越低,桶数越多,每一个桶中的元素个数越多,使用红黑树。
JDK1.8之后的ConcurrentHashMap
JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现,采用了数组+链表+红黑树的实现方式来设计,内部大量采用CAS操作。并发控制使⽤synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;
-
JDK1.8的Nod节点中value和next都用volatile修饰,保证并发的可见性。
-
synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点,这样只要 hash 不冲突,就不会产⽣并发,效率⼜提升 N 倍。
2.3 和HashTable的区别
Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突⽽存在的。
- Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全,效率⾮常低下。当⼀个线程访问同步⽅法时,其他线程也访问同步⽅法,可能会进⼊阻塞或轮询状态,如使⽤ put 添加元素,另⼀个线程不能使⽤ put 添加元素,也不能使⽤get,竞争会越来越激烈效率越低;
- ConcurrentHashMap不论1.7还是1.8,他的执行效率都比HashTable要高的多,主要原因还是因为Hash Table使用了一种全表加锁的方式。
ConcurrentHashMap 是一个并发散列映射表,它允许完全并发的读取,并且支持给定数量的并发更新。
- ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据,但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下,效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据,期间线程B调用get,则只能get到目前为止已经顺利插入的部分数据。
HashTable和同步包装器包装的 HashMap,使用一个全局的锁来同步不同线程间的并发访问,同一时间点,只能有一个线程持有锁,也就是说在同一时间点,只能有一个线程能访问容器,这虽然保证多线程间的安全并发访问,但同时也导致对容器的访问变成串行化的了。
- Hashtable的任何操作都会把整个表锁住,是阻塞的。好处是总能获取最实时的更新,比如说线程A调用putAll写入大量数据,期间线程B调用get,线程B就会被阻塞,直到线程A完成putAll,因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队,效率较低。
我们需要根据具体的应用场景选择合适的HashMap。
2.4 主要方法
void clear()
从该映射中移除所有映射关系
boolean containsKey(Object key)
测试指定对象是否为此表中的键。
boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值,则返回 true。
Enumeration elements()
返回此表中值的枚举。
Set<Map.Entry<K,V>> entrySet()
返回此映射所包含的映射关系的 Set 视图。
V get(Object key)
返回指定键所映射到的值,如果此映射不包含该键的映射关系,则返回 null。
boolean isEmpty()
如果此映射不包含键-值映射关系,则返回 true。
Enumeration keys()
返回此表中键的枚举。
Set keySet()
返回此映射中包含的键的 Set 视图。
V put(K key, V value)
将指定键映射到此表中的指定值。
void putAll(Map<? extends K,? extends V> m)
将指定映射中所有映射关系复制到此映射中。
V putIfAbsent(K key, V value)
如果指定键已经不再与某个值相关联,则将它与给定值关联。
V remove(Object key)
从此映射中移除键(及其相应的值)。
boolean remove(Object key, Object value)
只有目前将键的条目映射到给定值时,才移除该键的条目。
V replace(K key, V value)
只有目前将键的条目映射到某一值时,才替换该键的条目。
boolean replace(K key, V oldValue, V newValue)
只有目前将键的条目映射到给定值时,才替换该键的条目。
int size()
返回此映射中的键-值映射关系数。
Collection values()
返回此映射中包含的值的 Collection 视图。
3、使用实例
示例1:
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapMain {
public static void main(String[] args) {
Map<String, String> map = new ConcurrentHashMap<String, String>();
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
// map.keySet().iterator();
Iterator<String> it = map.keySet().iterator();
while (it.hasNext()) {
String key = it.next();
System.out.println(key + ","+ map.get(key));
if (key.equals("3")) {
map.put(key + "key", "3");
}
}
}
}
示例2:
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class TestThread {
public static void main(final String[] arguments) {
Map<String,String> map = new ConcurrentHashMap<String, String>();
map.put("1", "One");
map.put("2", "Two");
map.put("3", "Three");
map.put("5", "Five");
map.put("6", "Six");
System.out.println("Initial ConcurrentHashMap: " + map);
Iterator<String> iterator = map.keySet().iterator();
try {
while(iterator.hasNext()) {
String key = iterator.next();
if(key.equals("3")) {
map.put("4", "Four");
}
}
} catch(ConcurrentModificationException cme) {
cme.printStackTrace();
}
System.out.println("ConcurrentHashMap after modification: " + map);
map = new HashMap<String, String>();
map.put("1", "One");
map.put("2", "Two");
map.put("3", "Three");
map.put("5", "Five");
map.put("6", "Six");
System.out.println("Initial HashMap: " + map);
iterator = map.keySet().iterator();
try {
while(iterator.hasNext()) {
String key = iterator.next();
if(key.equals("3")) {
map.put("4", "Four");
}
}
System.out.println("HashMap after modification: " + map);
} catch(ConcurrentModificationException cme) {
cme.printStackTrace();
}
}
}
程序执行结果
Initial ConcurrentHashMap: {1 = One, 2 = Two, 3 = Three, 5 = Five, 6 = Six}
ConcurrentHashMap after modification: {1 = One, 2 = Two, 3 = Three, 4 = Four, 5 = Five, 6 = Six}
Initial HashMap: {1 = One, 2 = Two, 3 = Three, 5 = Five, 6 = Six}
java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(Unknown Source)
at java.util.HashMap$KeyIterator.next(Unknown Source)
at TestThread.main(TestThread.java:48)
评论区