本文共 5206 字，大约阅读时间需要 17 分钟。

HashMap1.7与1.8对比

• JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8并且数组长度到达64的时候，也就是默认阈值，就会自动扩容把数组中具体这一个链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率, 如果后续在该红黑树中删除元素, 删到只剩6的时候就会由红黑树转为单链表）
• JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
• 扩容后数据存储位置的计算方式也不一样，JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或。
• JDK1.7的时候是先进行扩容后进行插入，而在JDK1.8的时候则是先插入后进行扩容, 这个原因我觉得还是因为1.8加入了红黑树, 在插入的时候需要判断是普通链表节点还是红黑树节点

ConcurrentHashMap 1.7和1.8对比

• 在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：

  

• 所以在1.7中如果你要put数据, 是先经过离散定位到具体的segment数组中的位置, 而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样, 然后尝试获取锁之后,再经过一次离散定位到HashEntry数组中的具体位置

• ConcurrentHashMap1.7的初始化是会通过位与运算来初始化Segment的大小，用ssize来表示, Segment的大小ssize默认为 DEFAULT_CONCURRENCY_LEVEL =16

• Segment实现了ReentrantLock,也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行初始化，然后进行第二次hash操作，找到相应的HashEntry的位置，再将数据插入指定的HashEntry位置时（链表的尾端），后续的线程会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒

• ConcurrentHashMap1.7的get操作跟HashMap类似最主要的还是不上锁，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null

• ConcurrentHashMap1.7的getSize操作会间隔一段时间获取俩次, 如果相同返回数据, 如果不相同则全部上锁, 然后去获取值

• 在1.8中, 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

  

• 1.8将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。

• 1.8的put的过程很清晰，对当前的table进行无条件自循环直到put成功, 如果没有初始化就先调用initTable（）方法来进行初始化过程

  如果没有hash冲突就直接CAS插入
  如果还在进行扩容操作就先进行扩容
  如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
  最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
  如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容

• ConcurrentHashMap1.8的get操作的流程很简单，计算hash值，定位到该table索引位置，如果是首节点符合就返回

  如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
  以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

• 在JDK1.8版本中，对于size的计算，在扩容和addCount()方法就已经有处理了，可以注意一下Put函数，里面就有addCount()函数，早就计算好的，然后你size的时候直接给你

安全的List

• 对于普通的链表进行多线程下的add操作的时候, 因为其内部是直接进行size++操作往数组中放数据的, 然后在多线程下就会有ConcurrentModificationException 并发修改异常
• 所以java中有三种链表可以实现安全的链表

List
   
     list = new Vector<>(); //给add方法直接上锁, 效率很低
   

List
   
     list = Collections.synchronizedList(new ArrayList<>()); //使用了synchronized实现同步代码块, 粒度降低了, 但是效率还是不尽如意
   

List
   
     list = new CopyOnWriteArrayList<>();          //使用ReentrantLock上锁        // 并且在写入时进行了Arrays.copyOf进行了复制, 使其数组长度加一, 然后加载数组的最后一个位置,避免了数据的覆盖        //读数据的时候, 不用上锁直接读取原数组中的数据, 实现了读写分离, 效率很好        public void add(int index, E element) {
           final ReentrantLock lock = this.lock;        lock.lock();        try {
               Object[] elements = getArray();            int len = elements.length;            if (index > len || index < 0)                throw new IndexOutOfBoundsException("Index: "+index+                                                    ", Size: "+len);            Object[] newElements;            int numMoved = len - index;            if (numMoved == 0)                newElements = Arrays.copyOf(elements, len + 1);            else {
                   newElements = new Object[len + 1];                System.arraycopy(elements, 0, newElements, 0, index);                System.arraycopy(elements, index, newElements, index + 1,                                 numMoved);            }            newElements[index] = element;            setArray(newElements);        } finally {
               lock.unlock();        }    }
   

安全的Set

• 多线程下put操作ConcurrentModificationException 并发修改异常

Set
   
     stringSet = Collections.synchronizedSet(new HashSet<>()); //还是synchronized使用同步代码块实现
   

Set
   
     stringSet = new CopyOnWriteArraySet<>(); //和list的相同, 使用ReentrantLock实现同步        //并且在新增的时候采用复制的方法, 将读写进行分离, 也就是写会加锁, 读不会加锁        //因为Arrays.copyOf对数组而言是深拷贝, 也就是新建了一个数组空间, 所以对其进行放数据, 对原来的数据进行读数据, 是不影响的
   

Set
   
     stringSet = new ConcurrentSkipListSet<>();        /*        * ConcurrentSkipListSet的底层就是封装着一个ConcurrentSkipListMap, 后面讲        * */
   

安全的map

• 多线程下put操作ConcurrentModificationException 并发修改异常

Map
   
     map = new ConcurrentHashMap<>() //一开始讲的很详细了
   

ConcurrentSkipListMap
   
     map = new ConcurrentSkipListMap<>();
   

• ConcurrentSkipListMap是线程安全的有序的哈希表，适用于超高并发的场景。
• ConcurrentSkipListMap和TreeMap，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap是非线程安全的，而ConcurrentSkipListMap是线程安全的。第二，ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。所以在范围查找上ConcurrentSkipListMap是及其高效的, 但是ConcurrentSkipListMap由于索引的大量存在, 就消耗了内存
• 虽然在超大数据小并发的情况下对单个数据的存取 ConcurrentHashMap 速度比ConcurrentSkipListMap 快。
• 但ConcurrentSkipListMap有几个ConcurrentHashMap 不能比拟的优点：
  1、ConcurrentSkipListMap 的key是有序的。范围查找很高效
  2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log（N），和线程数几乎无关。也就是说在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap越能体现出他的优势。
• ConcurrentSkipListMap线程安全的原理与非阻塞队列ConcurrentBlockingQueue的原理一样：利用底层的插入、删除的CAS原子性操作，通过死循环不断获取最新的结点指针来保证不会出现竞态条件。
• 所以在多线程程序中，如果需要对Map的键值进行排序时，请尽量使用ConcurrentSkipListMap，可能得到更好的并发度。

转载地址：http://unsci.baihongyu.com/