当前位置:   article > 正文

第十五章Java并发集合

java并发集合

目录

第一代线程安全集合类 

HashTable与HashMap对比

第二代线程非安全集合类

第三代线程安全集合类

ConcurrentHashMap结构

JDK1.7

JDK1.8

          JDK8中的ConcurrentHashMap为什么使用synchronized来进行加锁?

第一代线程安全集合类 

  • Vector、Hashtable
  • 是怎么保证线程安排的: 使用synchronized修饰方法*
  • 缺点:效率低下

  • 直接用synchronized来修饰方法,这相当于直接针对 Hashtable 对象本身加锁.
  • 如果多线程访问同一个 Hashtable 就会直接造成锁冲突.
  • size 属性也是通过 synchronized 来控制同步, 也是比较慢的.,一旦触发扩容, 就由该线程完成整个扩容过程. 这个过程会涉及到大量的元素拷贝, 效率会非常低.

  •  HashTable容器使用Synchronized保证多线程安全,但在线程竞争激烈的情况下HashTable的效率十分低下,是因为当一个线程访问HashTable的同步方法时,其他线程也会访问HashTable的同步方法,会进入阻塞或轮询状态,所以已经被废弃了

HashTable与HashMap对比

(1)线程安全:HashMap是线程不安全的类,多线程下会造成并发冲突,但单线程下运行效率较高;HashTable是线程安全的类,很多方法都是用synchronized修饰,但同时因为加锁导致并发效率低下,单线程环境效率也十分低;

(2)插入null:HashMap允许有一个键为null,允许多个值为null;但HashTable不允许键或值为null;

(3)容量:HashMap底层数组长度必须为2的幂,这样做是为了hash准备,默认为16;而HashTable底层数组长度可以为任意值,这就造成了hash算法散射不均匀,容易造成hash冲突,默认为11;

(4)Hash映射:HashMap的hash算法通过非常规设计,将底层table长度设计为2的幂,使用位与运算代替取模运算,减少运算消耗;而HashTable的hash算法首先使得hash值小于整型数最大值,再通过取模进行散射运算;

  1. // HashMap
  2. static final int hash(Object key) {
  3. int h;
  4. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5. }
  6. // 下标index运算
  7. int index = (table.length - 1) & hash(key)
  8. // HashTable
  9. int hash = key.hashCode();
  10. int index = (hash & 0x7FFFFFFF) % tab.length;

(5)扩容机制:HashMap创建一个为原先2倍的数组,然后对原数组进行遍历以及rehash;HashTable扩容将创建一个原长度2倍+1的数组,再使用头插法将链表进行反序;

(6)结构区别:HashMap是由数组+链表形成,在JDK1.8之后链表长度大于8时转化为红黑树;而HashTable一直都是数组+链表;

(7)继承关系:HashTable继承自Dictionary类;而HashMap继承自AbstractMap类;

第二代线程非安全集合类

  • ArrayList、HashMap
  • 线程不安全,但是性能好,用来替代Vector、Hashtable            

使用ArrayList、HashMap,需要线程安全怎么办呢?

  • 自己使用同步机制 (synchronized 或者 ReentrantLock)
  • Collections.synchronizedList(new ArrayList); Collections.synchronizedMap(new HashMap)

源代码

  1. static class SynchronizedList<E>
  2. extends SynchronizedCollection<E>
  3. implements List<E> {
  4. private static final long serialVersionUID = -7754090372962971524L;
  5. final List<E> list;
  6. SynchronizedList(List<E> list) {
  7. super(list);
  8. this.list = list;
  9. }
  10. SynchronizedList(List<E> list, Object mutex) {
  11. super(list, mutex);
  12. this.list = list;
  13. }
  14. public boolean equals(Object o) {
  15. if (this == o)
  16. return true;
  17. synchronized (mutex) {return list.equals(o);}
  18. }
  19. public int hashCode() {
  20. synchronized (mutex) {return list.hashCode();}
  21. }
  22. public E get(int index) {
  23. synchronized (mutex) {return list.get(index);}
  24. }
  25. public E set(int index, E element) {
  26. synchronized (mutex) {return list.set(index, element);}
  27. }
  28. public void add(int index, E element) {
  29. synchronized (mutex) {list.add(index, element);}
  30. }
  31. public E remove(int index) {
  32. synchronized (mutex) {return list.remove(index);}
  33. }
  34. public int indexOf(Object o) {
  35. synchronized (mutex) {return list.indexOf(o);}
  36. }
  37. public int lastIndexOf(Object o) {
  38. synchronized (mutex) {return list.lastIndexOf(o);}
  39. }
  40. public boolean addAll(int index, Collection<? extends E> c) {
  41. synchronized (mutex) {return list.addAll(index, c);}
  42. }
  43. public ListIterator<E> listIterator() {
  44. return list.listIterator(); // Must be manually synched by user
  45. }
  46. public ListIterator<E> listIterator(int index) {
  47. return list.listIterator(index); // Must be manually synched by user
  48. }
  49. public List<E> subList(int fromIndex, int toIndex) {
  50. synchronized (mutex) {
  51. return new SynchronizedList<>(list.subList(fromIndex, toIndex),
  52. mutex);
  53. }
  54. }
  55. @Override
  56. public void replaceAll(UnaryOperator<E> operator) {
  57. synchronized (mutex) {list.replaceAll(operator);}
  58. }
  59. @Override
  60. public void sort(Comparator<? super E> c) {
  61. synchronized (mutex) {list.sort(c);}
  62. }
  63. private Object readResolve() {
  64. return (list instanceof RandomAccess
  65. ? new SynchronizedRandomAccessList<>(list)
  66. : this);
  67. }
  68. }
  1. private static class SynchronizedMap<K,V>
  2. implements Map<K,V>, Serializable {
  3. // use serialVersionUID from JDK 1.2.2 for interoperability
  4. private static final long serialVersionUID = 1978198479659022715L;
  5. private final Map<K,V> m; // Backing Map
  6. final Object mutex; // Object on which to synchronize
  7. SynchronizedMap(Map<K,V> m) {
  8. if (m==null)
  9. throw new NullPointerException();
  10. this.m = m;
  11. mutex = this;
  12. }
  13. SynchronizedMap(Map<K,V> m, Object mutex) {
  14. this.m = m;
  15. this.mutex = mutex;
  16. }
  17. public int size() {
  18. synchronized(mutex) {return m.size();}
  19. }
  20. public boolean isEmpty(){
  21. synchronized(mutex) {return m.isEmpty();}
  22. }
  23. public boolean containsKey(Object key) {
  24. synchronized(mutex) {return m.containsKey(key);}
  25. }
  26. public boolean containsValue(Object value){
  27. synchronized(mutex) {return m.containsValue(value);}
  28. }
  29. public V get(Object key) {
  30. synchronized(mutex) {return m.get(key);}
  31. }
  32. public V put(K key, V value) {
  33. synchronized(mutex) {return m.put(key, value);}
  34. }
  35. public V remove(Object key) {
  36. synchronized(mutex) {return m.remove(key);}
  37. }
  38. public void putAll(Map<? extends K, ? extends V> map) {
  39. synchronized(mutex) {m.putAll(map);}
  40. }
  41. public void clear() {
  42. synchronized(mutex) {m.clear();}
  43. }
  44. private transient Set<K> keySet = null;
  45. private transient Set<Map.Entry<K,V>> entrySet = null;
  46. private transient Collection<V> values = null;
  47. public Set<K> keySet() {
  48. synchronized(mutex) {
  49. if (keySet==null)
  50. keySet = new SynchronizedSet<K>(m.keySet(), mutex);
  51. return keySet;
  52. }
  53. }
  54. public Set<Map.Entry<K,V>> entrySet() {
  55. synchronized(mutex) {
  56. if (entrySet==null)
  57. entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
  58. return entrySet;
  59. }
  60. }
  61. public Collection<V> values() {
  62. synchronized(mutex) {
  63. if (values==null)
  64. values = new SynchronizedCollection<V>(m.values(), mutex);
  65. return values;
  66. }
  67. }
  68. public boolean equals(Object o) {
  69. if (this == o)
  70. return true;
  71. synchronized(mutex) {return m.equals(o);}
  72. }
  73. public int hashCode() {
  74. synchronized(mutex) {return m.hashCode();}
  75. }
  76. public String toString() {
  77. synchronized(mutex) {return m.toString();}
  78. }
  79. private void writeObject(ObjectOutputStream s) throws IOException {
  80. synchronized(mutex) {s.defaultWriteObject();}
  81. }
  82. }
  83. SynchronizedMap
  • SynchronizedMap 是一个实现了Map接口的代理类,该类中对Map接口中的方法使用synchronized 同步关键字来保证对Map的操作是线程安全的。
  • 底层使用synchronized代码块锁 虽然也是锁住了所有的代码,但是锁在方法里边,并所在方法外边性能可以理解为稍有提高吧。毕竟进方法本身就要分配资源的
  • Collections.synchronizedMap他是一个大锁(重量级锁),在用它包裹起来的集合,该集合所有的数据都会被上锁,类似的还有Collections.synchronizedList等集合,他们都是一种情况
  • Mutex在构造时默认赋值为this,即所有方法都用的同一个锁,m就是我们传入的map。

第三代线程安全集合类

大量并发情况下如何提高集合的效率和安全呢?

  • java.util.concurrent.*
  • ConcurrentHashMap:
  • CopyOnWriteArrayList :
  • CopyOnWriteArraySet:   注意 不是CopyOnWriteHashSet*
  • 底层大都采用Lock锁(1.8的ConcurrentHashMap不使用Lock锁),保证安全的同时,性能也很高。      
  • 在并发编程的情况下,使用HashMap可能会导致程序死循环,而使用线程安全的HashTable效率又十分低下,所以大名鼎鼎的Doug Lea写出了伟大的并发安全的ConcurrentHashMap

 ConcurrentHashMap结构


JDK1.7

  • JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现
  • 在JDK1.7中,ConcurrentHashMap是由Segment数组和Entry数组组成,Segment是一种可重入锁,在源码中直接继承的ReentrantLock 
  • JDK7中ConcurrentHashMap是通过ReentrantLock+分段思想来保证的并发安全的,ConcurrentHashMap的put方法会通过CAS的方式,把一个Segment对象存到Segment数组中,一个Segment内部存在一个HashEntry数组,相当于分段的HashMap,Segment继承了ReentrantLock,每段put开始会加锁。get方法无需加锁,用volatile来保证数据的正确性
  • 对于元素查询,第一次是在hash到对应的segment段,第二次是hash到对应的数组索引
  1. static class Segment<K,V> extends ReentrantLock implements Serializable {
  2. private static final long serialVersionUID = 2249069246763182397L;
  3. final float loadFactor;
  4. Segment(float lf) { this.loadFactor = lf; }
  5. }
  • 每一个Segment就类似一个HashMap,也就是数组+链表,一个Segment中包含一个HashEntry数组,数组中每个元素就对应一条链表,每个Segment守护着一个HashEntry数组中的元素,当对HashEntry中的元素进行修改时,就必须要获得该HashEntry数组对应的Segment锁
  • 所以1.7ConcurrentHashMap的并发度就是段的个数,段的个数就是支持同时多少个线程操作,锁的段,但是不会影响其他段的操作
  • 因为1.7是基于segment,相当于每个segment是一个hashmap,所以扩容也是针对于segment的内部进行扩容,不会影响其他segment,

JDK1.8

JDK1.8的实现已经抛弃了Segment分段锁机制,利用CAS+Synchronized来保证并发更新的安全,底层采用数组+链表+红黑树的存储结构

  • 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑
    树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对
    synchronized锁做了很多优化)
  • 读操作没有加锁(但是使用了 volatile 保证从内存读取结果), 只对写操作进行加锁. 加锁的方式仍然是是用 synchronized, 但是不是锁整个对象, 而是 "锁桶" (用每个链表的头结点作为锁对象), 大大降低了锁冲突的概率
  • 查找赋值操作使用CAS锁,读操作无锁,Node的val和next来使用volatile修饰,数组也是用volatile,为了能够发现多线程下有线程在扩容
  • 锁的是链表的head节点,不影响其他元素的读写,但是扩容的时候,会阻塞所有的读写操作,并发扩容(多个线程进行扩容),当某个线程在进行put的时候,如果发现正在进行扩容,那么该线程会进行扩容(一个线程在put的时候,如果发现没有进行扩容,在将元素插入到ConcurrentHashMap中,如果超过阈值,则进行扩容)
  • 在扩容也先生成一个新的数组,在转移元素的时候,先将数组进行分组,将每组分别交给不同的线程来进行元素的转移,每个线程负责一组或者多组的元素的转移

  1. public V put(K key, V value) {
  2. return putVal(key, value, false);
  3. }
  4. final V putVal(K key, V value, boolean onlyIfAbsent) {
  5. //ConcurrentHashMap的key不能为null
  6. if (key == null || value == null) throw new NullPointerException();
  7. //得到hash值
  8. int hash = spread(key.hashCode());
  9. //用于记录相应链表的长度
  10. int binCount = 0;
  11. for (Node<K,V>[] tab = table;;) {
  12. Node<K,V> f; int n, i, fh;
  13. //数组为空则初始化
  14. if (tab == null || (n = tab.length) == 0)
  15. tab = initTable();
  16. //通过hash值找到对应的数组下标f,并且该数组中还没有元素
  17. else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  18. //使用CAS操作将新值放入table中
  19. // 成功则退出循环
  20. // 失败则表示有并发操作,进入下一次循环
  21. if (casTabAt(tab, i, null,
  22. new Node<K,V>(hash, key, value, null)))
  23. break; // no lock when adding to empty bin
  24. }
  25. else if ((fh = f.hash) == MOVED)
  26. //扩容导致数据迁移
  27. tab = helpTransfer(tab, f);
  28. //找到数组下标后,数组中已经有元素了,f是头结点
  29. else {
  30. V oldVal = null;
  31. //获得头结点f的监视器锁
  32. synchronized (f) {
  33. if (tabAt(tab, i) == f) {
  34. //头结点f的哈希值大于0,说明是链表
  35. if (fh >= 0) {
  36. //用于累加,记录链表长度
  37. binCount = 1;
  38. for (Node<K,V> e = f;; ++binCount) {
  39. K ek;
  40. //如果该节点的hash值等于待put的key的hash并且key值与节点key值“相等”则覆盖value
  41. if (e.hash == hash &&
  42. ((ek = e.key) == key ||
  43. (ek != null && key.equals(ek)))) {
  44. oldVal = e.val;
  45. if (!onlyIfAbsent)
  46. e.val = value;
  47. break;
  48. }
  49. Node<K,V> pred = e;
  50. //如果到了链表末尾,则将新值插入链表最后
  51. if ((e = e.next) == null) {
  52. pred.next = new Node<K,V>(hash, key,
  53. value, null);
  54. break;
  55. }
  56. }
  57. }
  58. //红黑树
  59. else if (f instanceof TreeBin) {
  60. Node<K,V> p;
  61. binCount = 2;
  62. //调用红黑树的方法插入节点
  63. if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  64. value)) != null) {
  65. oldVal = p.val;
  66. if (!onlyIfAbsent)
  67. p.val = value;
  68. }
  69. }
  70. }
  71. }
  72. if (binCount != 0) {
  73. if (binCount >= TREEIFY_THRESHOLD)
  74. //链表长度大于8转为红黑树
  75. treeifyBin(tab, i);
  76. if (oldVal != null)
  77. return oldVal;
  78. break;
  79. }
  80. }
  81. }
  82. addCount(1L, binCount);
  83. return null;
  84. }
  1. public V get(Object key) {
  2. Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3. int h = spread(key.hashCode());
  4. if ((tab = table) != null && (n = tab.length) > 0 &&
  5. (e = tabAt(tab, (n - 1) & h)) != null) {
  6. //判断头节点是否就是要查找的元素
  7. if ((eh = e.hash) == h) {
  8. if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  9. return e.val;
  10. }
  11. //hash值小于0,说明链表已经转为红黑树
  12. else if (eh < 0)
  13. return (p = e.find(h, key)) != null ? p.val : null;
  14. //遍历链表获得value
  15. while ((e = e.next) != null) {
  16. if (e.hash == h &&
  17. ((ek = e.key) == key || (ek != null && key.equals(ek))))
  18. return e.val;
  19. }
  20. }
  21. return null;
  22. }

区别

  1. JDK8中新增了红黑树
  2. JDK7中使用的是头插法,JDK8中使用的是尾插法
  3. JDK7中使用了分段锁,而JDK8中没有使用分段锁了
  4. JDK7中使用了ReentrantLock,JDK8中没有使用ReentrantLock了,而使用了Synchronized
  5. JDK7中的扩容是每个Segment内部进行扩容,不会影响其他Segment,而JDK8中的扩容和HashMap的扩容类似,只不过支持了多线程扩容,并且保证了线程安全

JDK8中的ConcurrentHashMap为什么使用synchronized来进行加锁?

JDK8中使用synchronized加锁时,是对链表头结点和红黑树根结点来加锁的,而ConcurrentHashMap会保证,数组中某个位置的元素一定是链表的头结点或红黑树的根结点,所以JDK8中的ConcurrentHashMap在对某个桶进行并发安全控制时,只需要使用synchronized对当前那个位置的数组上的元素进行加锁即可,对于每个桶,只有获取到了第一个元素上的锁,才能操作这个桶,不管这个桶是一个链表还是红黑树。

想比于JDK7中使用ReentrantLock来加锁,因为JDK7中使用了分段锁,所以对于一个ConcurrentHashMap对象而言,分了几段就得有几个ReentrantLock对象,表示得有对应的几把锁。而JDK8中使用synchronized关键字来加锁就会更节省内存,并且jdk也已经对synchronized的底层工作机制进行了优化,效率更好。

CopyOnWriteArrayList

  • CopyOnWrite容器即写时复制的容器。当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。
  • 这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。

优点:
在读多写少的场景下, 性能很高, 不需要加锁竞争.
缺点:

  • 1. 占用内存较多.
  • 2. 新写的数据不能被第一时间读取到

HashMap 和 ConcurrentHashMap 的区别

  • ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。)HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。

ConcurrentHashMap 和 Hashtable 的区别?


ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
  • 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。
  • (JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

img

 JDK1.7的ConcurrentHashMap:

img

 JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点

ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?


JDK1.7

  • 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。
  • 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下:
  • 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。img
  •  该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;
  • Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁

JDK1.8

  • 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。

img

CopyOnWriteArrayList 

  • 适合读操作远远多余写操作的应用,特别在并发情况下,可以提高性能的并发读取,但是他的原理导致了他只能保证了数据的最终一致性,不能保证数据的实时一致性,所以你希望写入的数据,马上就能读到,就不要使用CopyOnWrite

 CopyOnWriteArraySet

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/821939
推荐阅读
相关标签
  

闽ICP备14008679号