常用集合特点

List

ArrayList：线程不安全，底层实现数组

LinkedList：线程不安全，底层实现双向链表

Set

HashSet：非线程安全，特点不允许重复元素，类中包含HashMap属性，存储元素都放到HashMap集合中，底层实现实际上就是一个HashMap

TreeSet：非线程安全，特点不允许重复元素，可以排序类中包含NavigableMap接口属性，具体实例为TreeMap对象，底层实现实际上是一个TreeMap

LinkedHashSet：非线程安全，特点值允许为空，不允许重复元素，有序。类中包含LinkedHashMap属性，数据都存储在LinkedHashMap上，底层实现实际上是一个LinkedHashMap

Map

HashMap：非线程安全，基于数组、链表、红黑树实现，特点无序，链表长度大于8时会转换为红黑树

TreeMap：非线程安全，基于红黑树NavigableMap的实现，特点可根据键的自然顺序排序，也可以根据创建映射时提供的Comparator进行排序

LinkedHashMap：线程不安全，是一个有序map集合，默认按照key,value插入元素顺序排序，也支持访问顺序。LinkedHashMap继承HashMap，通过HashMap+双向链表的方式实现，在put数据的时候，会把key,value放到HashMap中去，还会加入到双向链表中。

HashTable：线程安全，底层实现数组+链表+红黑树，和HashMap的原理一样，区别在于put、clean、remove等方法增加了同步（synchronized）机制

List和Set一般使用场景

ConcurrentHashMap JDK1.8分析

历史版本的实现演变

首先说下jdk1.7采用分段锁技术，整个Hash表被分为多个段，每个段中会对应一个Segment段锁，段与段之间可以并发访问，但是多线程想要操作同一个段是需要获取锁的。所有的put、get、remove等方法都是根据键的hash值对应到对应的段中，然后尝试获取锁进行访问。
640.jpg
jdk1.8取消了基于Segment的分段锁思想，改用CAS+synchronized控制并发操作，在某些方面提升了性能。并且追随1.8版本的HashMap底层实现，使用数组+链表+红黑树进行数据存储。

重要成员属性介绍

  1. /**
  2. * The array of bins. Lazily initialized upon first insertion.
  3. * Size is always a power of two. Accessed directly by iterators.
  4. */
  5. transient volatile Node<K,V>[] table;

和 HashMap 中的语义一样，代表整个哈希表 ，用于存储整个值

  1. /**
  2. * The next table to use; non-null only while resizing.
  3. */
  4. private transient volatile Node<K,V>[] nextTable;

这是一个连接表，用于哈希表扩容，扩容完成后会被重置为 null

  1. private transient volatile long baseCount;

该属性保存着整个哈希表中存储的所有的结点的个数总和，有点类似于 HashMap 的 size 属性。 

  1. private transient volatile int sizeCtl;

这是属性无论是初始化哈希表，还是扩容 rehash 的过程，都是需要依赖这个关键属性的。该属性有以下几种取值：

  • 0：默认值
  • -1：代表哈希表正在进行初始化
  • 大于0：相当于HashMap中的threshold，表示阈值
  • 小于-1：代表有多个线程正在进行扩容

该属性的使用还是有点复杂的，在我们分析扩容源码的时候再给予更加详尽的描述，此处了解其可取的几个值都分别代表着什么样的含义即可。
构造函数的实现也和 HashMap 的实现类似，此处不再赘述，贴出源码供比较。 

  1. public ConcurrentHashMap(int initialCapacity) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException();
  4.     int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
  5.                MAXIMUM_CAPACITY :
  6.                tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
  7.     this.sizeCtl = cap;
  8. }

其他常用的方法我们将在文末进行简单介绍，下面我们主要来分析下 ConcurrentHashMap 的一个核心方法 put，我们也会一并解决掉该方法中涉及到的扩容、辅助扩容，初始化哈希表等方法。

put方法实现并发添加

对于 HashMap 来说，多线程并发添加元素会导致数据丢失等并发问题，那么 ConcurrentHashMap 又是如何做到并发添加的呢？

  1. public V put(K key, V value) {
  2.     return putVal(key, value, false);
  3. }

put()会转发到putValue()上，我们分两步对putVal()方法进行分析

  1. //第一部分
  2. final V putVal(K key, V value, boolean onlyIfAbsent) {
  3.     //对传入的参数进行合法性判断
  4.     if (key == null || value == null) throw new NullPointerException();
  5.     //计算键所对应的 hash 值
  6.     int hash = spread(key.hashCode());
  7.     //记录链表的长度
  8.     int binCount = 0;
  9.     //遍历table进处理，自旋操作，出现线程竞争时不断自旋
  10.     for (Node<K,V>[] tab = table;;) {
  11.         Node<K,V> f; int n, i, fh;
  12.         //如果哈希表还未初始化，那么初始化它
  13.         if (tab == null || (n = tab.length) == 0)
  14.             tab = initTable(); // 初始化数组
  15.         //根据键的 hash 值找到哈希数组下标得到相应的Node节点
  16.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  17.             // 如果数组下标得到的Node节点为空，直接通过CAS将key,value值封装为node节点插入数组
  18.             if (casTabAt(tab, i, null,
  19.                          new Node<K,V>(hash, key, value, null)))
  20.                 break;                   
  21.         }

这里需要详细说明的只有 initTable 方法，这是一个初始化哈希表的操作，它同时只允许一个线程进行初始化操作

  1. private final Node<K,V>[] initTable() {
  2.     Node<K,V>[] tab; int sc;
  3.     //如果表为空才进行初始化操作
  4.     while ((tab = table) == null || tab.length == 0) {
  5.         //sizeCtl 小于零说明已经有线程正在进行初始化操作
  6.         //当前线程应该放弃 CPU 的使用
  7.         if ((sc = sizeCtl) < 0)
  8.             Thread.yield(); // lost initialization race; just spin
  9.         //否则说明还未有线程对表进行初始化，那么本线程就来做这个工作
  10.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  11.             //保险起见，再次判断下表是否为空
  12.             try {
  13.                 if ((tab = table) == null || tab.length == 0) {
  14.                     //sc 大于零说明容量已经初始化了，否则使用默认容量
  15.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  16.                     @SuppressWarnings("unchecked")
  17.                     //根据容量构建数组
  18.                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  19.                     //将数组赋值给table
  20.                     table = tab = nt;
  21.                     //计算阈值（下一次扩容的大小），等效于 n*0.75
  22.                     sc = n - (n >>> 2);
  23.                 }
  24.             } finally {
  25.                 //设置阈值
  26.                 sizeCtl = sc;
  27.             }
  28.             break;
  29.         }
  30.     }
  31.     return tab;
  32. }

关于 initTable 方法的每一步实现都已经给出注释，该方法的核心思想就是，只允许一个线程对表进行初始化，如果不巧有其他线程进来了，那么会让其他线程交出 CPU 等待下次系统调度。这样，保证了表同时只会被一个线程初始化

接着，我们回到 putVal 方法，这样的话，我们第一部分的 putVal 源码就分析结束了，下面我们看后一部分的源码：

  1. //检测到桶结点是 ForwardingNode 类型，协助扩容
  2. else if ((fh = f.hash) == MOVED)
  3.      tab = helpTransfer(tab, f);
  4. //桶结点是普通的结点，锁住该桶头结点并试图在该链表的尾部添加一个节点
  5. else {
  6.        V oldVal = null;
  7.        // 锁定Node头节点
  8.        synchronized (f) {
  9.            if (tabAt(tab, i) == f) {
  10.               //向普通的链表中添加元素，无需赘述
  11.               if (fh >= 0) {
  12.                  binCount = 1;
  13.                  for (Node<K,V> e = f;; ++binCount) {
  14.                      K ek;
  15.                      // map的key一样的直接替换value值
  16.                      if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
  17.                          oldVal = e.val;
  18.                          if (!onlyIfAbsent)
  19.                             // 新老的value值替换为新的value值
  20.                             e.val = value;
  21.                             break;
  22.                       }
  23.                       // 老的Node节点，既hash计算出来通过数组下标取出的节点
  24.                       Node<K,V> pred = e;
  25.                       // 老Node节点的下一节(next)点为null，说明就是链表的最后一个元素
  26.                       // 这里需要将当前的节点放到链表最后一个元素的next上
  27.                       if ((e = e.next) == null) {
  28.                           // 将当前key,value的值放到老节点的next节点上
  29.                          pred.next = new Node<K,V>(hash, key,value, null);
  30.                          break;
  31.                       }
  32.                  }
  33.            }
  34.            //向红黑树中添加元素，TreeBin 结点的hash值为TREEBIN（-2）
  35.            else if (f instanceof TreeBin) {
  36.                Node<K,V> p;
  37.                binCount = 2;
  38.                  if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                      value)) != null) {
  39.                    oldVal = p.val;
  40.                    if (!onlyIfAbsent)
  41.                       p.val = value;
  42.                 }
  43.            }
  44.        }
  45.    }
  46.   //binCount != 0 说明向链表或者红黑树中添加或修改一个节点成功
  47.   //binCount  == 0 说明 put 操作将一个新节点添加成为某个桶的首节点
  48.   if (binCount != 0) {
  49.          //链表深度超过 8 转换为红黑树
  50.          if (binCount >= TREEIFY_THRESHOLD)
  51.              treeifyBin(tab, i);
  52.          //oldVal != null 说明此次操作是修改操作
  53.          //直接返回旧值即可，无需做下面的扩容边界检查
  54.          if (oldVal != null)
  55.              return oldVal;
  56.            break;
  57.         }
  58.     }
  59. }
  60. //CAS 式更新baseCount，并判断是否需要扩容
  61. addCount(1L, binCount);
  62. //程序走到这一步说明此次 put 操作是一个添加操作，否则早就 return 返回了
  63. return null;

这一部分的源码大体上已如注释所描述，至此整个 putVal 方法的大体逻辑实现相信你也已经清晰了，好好回味一下。下面我们对这部分中的某些方法的实现细节再做一些深入学习

首先需要介绍一下，ForwardingNode 这个节点类型

  1. static final class ForwardingNode<K,V> extends Node<K,V> {
  2.         final Node<K,V>[] nextTable;
  3.         ForwardingNode(Node<K,V>[] tab) {
  4.             //注意这里
  5.             super(MOVED, null, null, null);
  6.             this.nextTable = tab;
  7.         }
  8.     //省略其 find 方法
  9. }

这个节点内部保存了一 nextTable 引用，它指向一张 hash 表。在扩容操作中，我们需要对每个桶中的结点进行分离和转移，如果某个桶结点中所有节点都已经迁移完成了（已经被转移到新表 nextTable 中了），那么会在原 table 表的该位置挂上一个 ForwardingNode 结点，说明此桶已经完成迁移

ForwardingNode 继承自 Node 结点，并且它唯一的构造函数将构建一个键，值，next 都为 null 的结点，反正它就是个标识，无需那些属性。但是 hash 值却为 MOVED

所以，我们在 putVal 方法中遍历整个 hash 表的桶结点，如果遇到 hash 值等于 MOVED，说明已经有线程正在扩容 rehash 操作，整体上还未完成，不过我们要插入的桶的位置已经完成了所有节点的迁移

  1. final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
  2.     Node<K,V>[] nextTab; int sc;
  3.     if (tab != null && (f instanceof ForwardingNode) &&
  4.         (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
  5.         //返回一个 16 位长度的扩容校验标识
  6.         int rs = resizeStamp(tab.length);
  7.         while (nextTab == nextTable && table == tab &&
  8.                (sc = sizeCtl) < 0) {
  9.             //sizeCtl 如果处于扩容状态的话
  10.             //前 16 位是数据校验标识，后 16 位是当前正在扩容的线程总数
  11.             //这里判断校验标识是否相等，如果校验符不等或者扩容操作已经完成了，直接退出循环，不用协助它们扩容了
  12.             if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  13.                 sc == rs + MAX_RESIZERS || transferIndex <= 0)
  14.                 break;
  15.             //否则调用 transfer 帮助它们进行扩容
  16.             //sc + 1 标识增加了一个线程进行扩容
  17.             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
  18.                 transfer(tab, nextTab);
  19.                 break;
  20.             }
  21.         }
  22.         return nextTab;
  23.     }
  24.     return table;
  25. }

下面我们看这个稍显复杂的 transfer 方法，我们依然分几个部分来细说

  1. //第一部分
  2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  3.         int n = tab.length, stride;
  4.         //计算单个线程允许处理的最少table桶首节点个数，不能小于 16
  5.         if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  6.             stride = MIN_TRANSFER_STRIDE; 
  7.         //刚开始扩容，初始化 nextTab 
  8.         if (nextTab == null) {
  9.             try {
  10.                 // 新建一个长度为原来数组长度2倍的数组
  11.                 @SuppressWarnings("unchecked")
  12.                 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  13.                 nextTab = nt;
  14.             } catch (Throwable ex) {
  15.                 sizeCtl = Integer.MAX_VALUE;
  16.                 return;
  17.             }
  18.             nextTable = nextTab;
  19.             //transferIndex 指向最后一个桶，方便从后向前遍历 
  20.             transferIndex = n;
  21.         }
  22.         int nextn = nextTab.length;
  23.         //定义 ForwardingNode 用于标记迁移完成的桶
  24.         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);

这部分代码还是比较简单的，主要完成的是对单个线程能处理的最少桶结点个数的计算和一些属性的初始化操作

  1. //第二部分，并发扩容控制的核心
  2. boolean advance = true;
  3. boolean finishing = false;
  4. //i 指向当前桶，bound 指向当前线程需要处理的桶结点的区间下限
  5. for (int i = 0, bound = 0;;) {
  6.        Node<K,V> f; int fh;
  7.        //这个 while 循环的目的就是通过 --i 遍历当前线程所分配到的桶结点
  8.        //一个桶一个桶的处理
  9.        while (advance) {
  10.            int nextIndex, nextBound;
  11.            if (--i >= bound || finishing)
  12.                advance = false;
  13.            //transferIndex <= 0 说明已经没有需要迁移的桶了
  14.            else if ((nextIndex = transferIndex) <= 0) {
  15.                i = -1;
  16.                advance = false;
  17.            }
  18.            //更新 transferIndex
  19.            //为当前线程分配任务，处理的桶结点区间为（nextBound,nextIndex）
  20.            else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
  21.                bound = nextBound;
  22.                i = nextIndex - 1;
  23.                advance = false;
  24.            }
  25.        }
  26.        //当前线程所有任务完成
  27.        if (i < 0 || i >= n || i + n >= nextn) {
  28.            int sc;
  29.            if (finishing) {
  30.                nextTable = null;
  31.                table = nextTab;
  32.                sizeCtl = (n << 1) - (n >>> 1);
  33.                return;
  34.            }
  35.            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  36.                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  37.                    return;
  38.                finishing = advance = true;
  39.                i = n; 
  40.            }
  41.        }
  42.        //待迁移桶为空，那么在此位置 CAS 添加 ForwardingNode 结点标识该桶已经被处理过了
  43.        else if ((f = tabAt(tab, i)) == null)
  44.            advance = casTabAt(tab, i, null, fwd);
  45.        //如果扫描到 ForwardingNode，说明此桶已经被处理过了，跳过即可
  46.        else if ((fh = f.hash) == MOVED)
  47.            advance = true;

每个新参加进来扩容的线程必然先进 while 循环的最后一个判断条件中去领取自己需要迁移的桶的区间。然后 i 指向区间的最后一个位置，表示迁移操作从后往前的做。接下来的几个判断就是实际的迁移结点操作了。等我们大致介绍完成第三部分的源码再回来对各个判断条件下的迁移过程进行详细的叙述。

  1. //第三部分
  2. else {
  3.     //
  4.     synchronized (f) {
  5.         if (tabAt(tab, i) == f) {
  6.             Node<K,V> ln, hn;
  7.             //链表的迁移操作
  8.             if (fh >= 0) {
  9.                 int runBit = fh & n;
  10.                 Node<K,V> lastRun = f;
  11.                 //整个 for 循环为了找到整个桶中最后连续的 fh & n 不变的结点
  12.                 for (Node<K,V> p = f.next; p != null; p = p.next) {
  13.                     int b = p.hash & n;
  14.                     if (b != runBit) {
  15.                         runBit = b;
  16.                         lastRun = p;
  17.                     }
  18.                 }
  19.                 if (runBit == 0) {
  20.                     ln = lastRun;
  21.                     hn = null;
  22.                 }
  23.                 else {
  24.                     hn = lastRun;
  25.                     ln = null;
  26.                 }
  27.                 //如果fh&n不变的链表的runbit都是0，则nextTab[i]内元素ln前逆序，ln及其之后顺序
  28.                 //否则，nextTab[i+n]内元素全部相对原table逆序
  29.                 //这是通过一个节点一个节点的往nextTab添加
  30.                 for (Node<K,V> p = f; p != lastRun; p = p.next) {
  31.                     int ph = p.hash; K pk = p.key; V pv = p.val;
  32.                     if ((ph & n) == 0)
  33.                         ln = new Node<K,V>(ph, pk, pv, ln);
  34.                     else
  35.                         hn = new Node<K,V>(ph, pk, pv, hn);
  36.                 }
  37.                 //把两条链表整体迁移到nextTab中
  38.                 setTabAt(nextTab, i, ln);
  39.                 setTabAt(nextTab, i + n, hn);
  40.                 //将原桶标识位已经处理
  41.                 setTabAt(tab, i, fwd);
  42.                 advance = true;
  43.             }
  44.             //红黑树的复制算法，不再赘述
  45.             else if (f instanceof TreeBin) {
  46.                 TreeBin<K,V> t = (TreeBin<K,V>)f;
  47.                 TreeNode<K,V> lo = null, loTail = null;
  48.                 TreeNode<K,V> hi = null, hiTail = null;
  49.                 int lc = 0, hc = 0;
  50.                 for (Node<K,V> e = t.first; e != null; e = e.next) {
  51.                     int h = e.hash;
  52.                     TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);
  53.                     if ((h & n) == 0) {
  54.                         if ((p.prev = loTail) == null)
  55.                             lo = p;
  56.                         else
  57.                             loTail.next = p;
  58.                     loTail = p;
  59.                     ++lc;
  60.                     }
  61.                     else {
  62.                         if ((p.prev = hiTail) == null)
  63.                             hi = p;
  64.                         else
  65.                             hiTail.next = p;
  66.                     hiTail = p;
  67.                     ++hc;
  68.                     }
  69.                 }
  70.                 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;
  71.                 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;
  72.                 setTabAt(nextTab, i, ln);
  73.                 setTabAt(nextTab, i + n, hn);
  74.                 setTabAt(tab, i, fwd);
  75.                 advance = true;
  76.            }

那么至此，有关迁移的几种情况已经介绍完成了，下面我们整体上把控一下整个扩容和迁移过程。

首先，每个线程进来会先领取自己的任务区间，然后开始 —i 来遍历自己的任务区间，对每个桶进行处理。如果遇到桶的头结点是空的，那么使用 ForwardingNode 标识该桶已经被处理完成了。如果遇到已经处理完成的桶，直接跳过进行下一个桶的处理。如果是正常的桶，对桶首节点加锁，正常的迁移即可，迁移结束后依然会将原表的该位置标识为已经处理

当 i < 0，说明本线程处理速度够快的，整张表的最后一部分已经被它处理完了，现在需要看看是否还有其他线程在自己的区间段还在迁移中。这是退出的逻辑判断部分

  1. if (i < 0 || i >= n || i + n >= nextn) {
  2.     int sc;
  3.     if (finishing) {
  4.         nextTable = null;
  5.         table = nextTab;
  6.         sizeCtl = (n << 1) - (n >>> 1);
  7.         return;
  8.     }
  9.     if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  10.         if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  11.             return;
  12.         finishing = advance = true;
  13.         i = n; // recheck before commit
  14.     }
  15. }

finnish 是一个标志，如果为 true 则说明整张表的迁移操作已经全部完成了，我们只需要重置 table 的引用并将 nextTable 赋为空即可。否则，CAS 尝试的将 sizeCtl 减一，表示当前线程已经完成了任务，退出扩容操作

如果退出成功，那么需要进一步判断是否还有其他线程仍然在执行任务

  1. if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  2.     return;

我们说过 resizeStamp(n) 返回的是对 n 的一个数据校验标识，占 16 位。而 RESIZE_STAMP_SHIFT 的值为 16，那么位运算后，整个表达式必然在右边空出 16 个零。也正如我们所说的，sizeCtl 的高 16 位为数据校验标识，低 16 为表示正在进行扩容的线程数量

(resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2表示当前只有一个线程正在工作，相对应的，如果 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT，说明当前线程就是最后一个还在扩容的线程，那么会将 finishing 标识为 true，并在下一次循环中退出扩容方法。这一块的难点在于对 sizeCtl 的各个值的理解。

看到这里，真的为 Doug Lea 精妙的设计而折服，针对于多线程访问问题，不但没有拒绝式得将他们阻塞在门外，反而邀请他们来帮忙一起工作。

好了，我们一路往回走，回到我们最初分析的 putVal 方法。接着前文的分析，当我们根据 hash 值，找到对应的桶结点，如果发现该结点为 ForwardingNode 结点，表明当前的哈希表正在扩容和 rehash，于是将本线程送进去帮忙扩容。否则如果是普通的桶结点，于是锁住该桶，分链表和红黑树的插入一个节点，具体插入过程类似 HashMap，此处不再赘述。

当我们成功的添加完成一个结点，最后是需要判断添加操作后是否会导致哈希表达到它的阈值，并针对不同情况决定是否需要进行扩容，还有 CAS 式更新哈希表实际存储的键值对数量。这些操作都封装在 addCount 这个方法中，当然 putVal 方法的最后必然会调用该方法进行处理。下面我们看看该方法的具体实现，该方法主要做两个事情。一是更新 baseCount，二是判断是否需要扩容

这一部分主要完成的是对 baseCount 的 CAS 更新

  1. //第一部分，更新 baseCount
  2. private final void addCount(long x, int check) {
  3.     CounterCell[] as; long b, s;
  4.     //如果更新失败才会进入的 if 的主体代码中
  5.     //s = b + x  其中 x 等于 1
  6.     if ((as = counterCells) != null ||
  7.         !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  8.         CounterCell a; long v; int m;
  9.         boolean uncontended = true;
  10.         //高并发下 CAS 失败会执行 fullAddCount 方法
  11.         if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null ||!(uncontended =U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  12.             fullAddCount(x, uncontended);
  13.             return;
  14.         }
  15.         if (check <= 1)
  16.             return;
  17.         s = sumCount();
  18.     }

判断是否需要扩容

  1. //第二部分，判断是否需要扩容
  2. if (check >= 0) {
  3.      Node<K,V>[] tab, nt; int n, sc;
  4.      while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {
  5.           int rs = resizeStamp(n);
  6.           if (sc < 0) {
  7.              if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)
  8.                break;
  9.                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  10.                   transfer(tab, nt);
  11.                }
  12.            else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))
  13.                     transfer(tab, null);
  14.                s = sumCount();
  15.             }
  16.     }

get方法实现读取

get 方法可以根据指定的键，返回对应的键值对，由于是读操作，所以不涉及到并发问题。源码也是比较简单的

  1. public V get(Object key) {
  2.     Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3.     // 1. 计算hash值
  4.     int h = spread(key.hashCode());
  5.     // 2. 验证table是否初始化，且通过hash计算的下标位置不能为null，否则直接返回
  6.     if ((tab = table) != null && (n = tab.length) > 0 &&
  7.         (e = tabAt(tab, (n - 1) & h)) != null) {
  8.         // 2.1 先判断table[i]的头节点(node)的hash值和key生成的hash值是否相等
  9.         if ((eh = e.hash) == h) {
  10.             if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  11.                 return e.val;
  12.         }
  13.         // 2.2 table[i]的node为红黑树，通过红黑树搜索返回
  14.         else if (eh < 0)
  15.             return (p = e.find(h, key)) != null ? p.val : null;
  16.         // 2.3 通过链表搜索返回
  17.         while ((e = e.next) != null) {
  18.             if (e.hash == h &&
  19.                 ((ek = e.key) == key || (ek != null && key.equals(ek))))
  20.                 return e.val;
  21.         }
  22.     }
  23.     return null;
  24. }

这里的处理流程相对比较易懂，主要做以下几件事：

  1. 获取hash值
  2. 先比对table[i]头节点的has值和key的has值是否相等
  3. 再对比table[i]头节点的key是否相等
  4. hash值小于0表示为红黑树结构，通过红黑树搜索结果
  5. 不是红黑树，遍历tables[i]链表搜索结果

clear 删除元素

clear 方法将删除整张哈希表中所有的键值对，删除操作也是一个桶一个桶的进行删除

  1. public void clear() {
  2.     long delta = 0L; // negative number of deletions
  3.     int i = 0;
  4.     Node<K,V>[] tab = table;
  5.     // 数组不能为空，遍历table数组
  6.     while (tab != null && i < tab.length) {
  7.         int fh;
  8.         // 通过数组下标取出node节点
  9.         Node<K,V> f = tabAt(tab, i);
  10.         if (f == null)
  11.             ++i;
  12.         // 如果当前节点在正在扩容，就协助扩容
  13.         else if ((fh = f.hash) == MOVED) {
  14.             tab = helpTransfer(tab, f);
  15.             i = 0; // restart
  16.         }
  17.         else {
  18.             // 锁定数组中头节点
  19.             synchronized (f) {
  20.                 if (tabAt(tab, i) == f) {
  21.                     Node<K,V> p = (fh >= 0 ? f :(f instanceof TreeBin) ?((TreeBin<K,V>)f).first : null);
  22.                         //循环到链表或者红黑树的尾部
  23.                         while (p != null) {
  24.                             --delta;
  25.                             p = p.next;
  26.                         }
  27.                         //首先删除链、树的末尾元素，避免产生大量垃圾  
  28.                         //利用CAS无锁置null  
  29.                         setTabAt(tab, i++, null);
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         if (delta != 0L)
  35.             addCount(delta, -1);
  36.     }

HashMap

JDK1.7和1.8对比

  1. JDK1.7是底层数据结构是数组+链表结构，通过对key进行hash运算除以数组长度取模（hashcode%数组长度）计算数组下标，通过数组下标决定元素存储在哪个数据下标。如果取模计算出的数组下标相同，会把这些相同的元素组成一个链表（Entry）。在极端情况下这些key全部定位到同一个数组下标中国，会导致链表的长度会很长，在put()和get()时会遍历整张链表
  2. JDK1.8中的底层数据结构是数组+链表+红黑树结构，也是通过key进行hash运算除以数组长度取模计算数组下标，区别在于链表长度大于8时会将链表转换为红黑树结构。红黑树的特点在数组下标的元素很多时，遍历元素时比链表效率要高
  3. JDK1.7中数组中存放的对象是Entry，是HashMap中的一个内部类，实现Map.Entry接口。JDK1.8数组中存放的对象是Node，实现Map.Entry接口。这点在名字上不同
  4. JDK1.8中提出了1.7中对key为null的单独处理，1.7中会将key=null的元素存储在数组的第0个下标上，1.8中对key=null没有单独处理和普通key的处理方式一样
  5. JDK1.7中插入元素到链表采用头插法，所谓头插法就将新元素做为链表的第一个元素，下一个元素为之前链表的第一个元素。1.8采用尾插法，就是新增元素时，将元素放到链表的最后。1.7的头插法会在多线程操作扩容时存在死循环的情况，为什么会存在死循环的分析会在后面介绍。
  6. JDK1.7中在扩容时，会对所有元素重新进行数组下标定位计算，1.8中采用高低位索引机制，再扩容时不再需要对所有元素进行下标定位计算

JDK1.7 死循环的原因

因为JDK1.7的链表拼接是采用头插法，在多线线程扩容时会出现链表死循环的情况，具体分析如下：

线程1扩容

  1. do {
  2.   Entry<K,V> next = e.next; // 假设线程一执行到这里就被调度挂起了
  3.   int i = indexFor(e.hash, newCapacity); // 计算元素在新数组中的下标位置
  4.   e.next = newTable[i];  //之前链表指向当前链表的下一个节点
  5.   newTable[i] = e;       //当前链表放到数组
  6.   e = next;
  7. } while (e != null);

此时线程二开始执行扩容，并完成扩容，扩容后的数据存储。扩容后key=7元素的next结点是key=3这个元素。
未命名文件 (1).jpg

线程二执行完后，线程一从挂起状态唤醒继续执行

  1. 执行e.next=newTable[i]， 注意此时newTable[i]链表的头结点key=7，e元素的key=3，也就是说key=3这个元素的next元素指向了key=7这个元素。
  2. 执行newTable[i]=e，扩容后的链表头结点是key=3
  3. e=next，这里的next结点是key=7，而key=7这个元素的next结点在线程二中已经为key=3
  4. 此时我们发现环形链表出现了，key=3的next元素是key=7，key=7的next元素是key=3

未命名文件 (3).jpg

HashMap 内存泄露

在java中，内存泄露是指一些被分配的对象，已经不用了，但是对象还是可达的GC无法回收掉，我们认为这就是内存泄露。

  1. class HashMapLeak {
  2.     public static void main(String[] args) {
  3.         Map<Person, String> map = new HashMap<Person, String>();
  4.         Person person = new Person("张山", 30, "杭州市");
  5.         map.put(person, "A");
  7.         // 修改person的值
  8.         person.setAddress("上海市");
  10.         // 删除map
  11.         // 由于在put时，person对象的address属性参与了hash运算，修改后person对象后，在删除map，hash值发生变化，所以无法删除map导致内存泄露
  12.         map.remove(person);
  13.     }
  14. }
  16. class Person {
  17.     private String name;
  18.     private int age;
  19.     private String address;
  21.     Person(String name, int age, String address) {
  22.         this.name = name;
  23.         this.age = age;
  24.         this.address = address;
  25.     }
  27.     // 省略set、get...
  28. }

分析原因

因为我们在put时，person对象作为map的key，所以参与了hash运算。当我们修改person对象后在删除，删除时也会对person对象做hash运算，导致和put时的hash值不一致无法删除，所以导致内存泄露

解决方案

重写person对象的hashCode方法，只使用不发生变化的对象参与hash运算

HashMap内存溢出

所谓内存溢出是指内存使用，GC无法及时回收，导致超出JVM的内存大小，抛出java.lang.OutOfMemoryError异常

  1. class HashMapOutOfMemeryError {
  2.     public static void main(String[] args) {
  3.         Map<Key, String> map = new HashMap<Key, String>(1000);
  4.         int counter = 0;
  5.         while (true) {
  6.             Key key = new Key("张山", 30, "杭州市");
  7.             map.put(key, "A");
  9.             counter++;
  10.             if (counter % 1000 == 0) {
  11.                 System.out.println("map size: " + map.size());
  12.                 System.out.println("运行" + counter + "次后，可用内存剩余" + Runtime.getRuntime().freeMemory() / (1024 * 1024) + "MB");
  13.             }
  14.         }
  15.     }
  16. }
  18. class Key {
  19.     private String name;
  20.     private int age;
  21.     private String address;
  23.     Key(String name, int age, String address) {
  24.         this.name = name;
  25.         this.age = age;
  26.         this.address = address;
  27.     }
  29.     @Override
  30.     public int hashCode() {
  31.         return name.hashCode();
  32.     }
  33. }

为了加快测试内存溢出，在执行上面代码时将JVM内存调小。

分析原因

上面代码我们的目的是想覆盖map的key，但是每次都是作为一个新的对象插入map中，因为HashMap判断key相同的条件是e.hash == hash && ((k = e.key) == key || key.equals(k)) ，但是我们只重写了hashCode()方法，只有e.hash=hash这个条件满足，key.equals(k)这个条件不能满足，导致HashMap在添加元素是都认为不是同一个key不能覆盖原来的key，导致内存溢出。

解决方案

除了重写HashCode()方法外，还需要重写equals()方法。

HashMap 源码分析 JDK 1.8

我们在分析HashMap之前，先看一张流程图，来对HashMap的执行逻辑由一个大概的了解。
HashMap JDK1.8流程.png
在JDK1.8中，HashMap的底层数据结构已经是数组+（链表+红黑树）的结构了，在链表深度大于8时，会转换为红黑树。小于8时是链表结构。

构造方法

  1. // 默认构造函数。
  2. public HashMap() {
  3.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
  4. }
  6. // 包含另一个“Map”的构造函数
  7. public HashMap(Map<? extends K, ? extends V> m) {
  8.     this.loadFactor = DEFAULT_LOAD_FACTOR;
  9.     putMapEntries(m, false);//下面会分析到这个方法
  10. }
  12. // 指定“容量大小”的构造函数
  13. public HashMap(int initialCapacity) {
  14.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  15. }
  17. // 指定“容量大小”和“加载因子”的构造函数
  18. public HashMap(int initialCapacity, float loadFactor) {
  19.     if (initialCapacity < 0)
  20.         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  21.     if (initialCapacity > MAXIMUM_CAPACITY)
  22.         initialCapacity = MAXIMUM_CAPACITY;
  23.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  24.         throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  25.     // 初始化扩容阈值（负载因子，超过这个阈值时会扩容数组长度）
  26.     this.loadFactor = loadFactor;
  27.     // 初始化数组长度
  28.     this.threshold = tableSizeFor(initialCapacity);
  29. }
  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException("Illegal initial capacity: " +
  4.                                                initialCapacity);
  5.     if (initialCapacity > MAXIMUM_CAPACITY)
  6.         initialCapacity = MAXIMUM_CAPACITY;
  7.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  8.         throw new IllegalArgumentException("Illegal load factor: " +
  9.                                                loadFactor);
  10.     // 初始化扩容阈值（负载因子，超过这个阈值时会扩容数组长度）
  11.     this.loadFactor = loadFactor;
  12.     // 初始化数组长度
  13.     this.threshold = tableSizeFor(initialCapacity);
  14. }

添加put()

  1. public V put(K key, V value) {
  2.     // hash(key)获取key的hash值
  3.     return putVal(hash(key), key, value, false, true);
  4. }
  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.     if ((tab = table) == null || (n = tab.length) == 0)
  5.         // resize()扩容
  6.         n = (tab = resize()).length;
  7.     // (n-1) & hash 计算数组下标
  8.     // 获取数组下标的值，如果为空说明桶里没有链表
  9.     if ((p = tab[i = (n - 1) & hash]) == null)
  10.         // 数组的桶为空，说明是链表头节点
  11.         // 直接将当前值做为头节点放到数组下标
  12.         tab[i] = newNode(hash, key, value, null);
  13.     else {
  14.         Node<K,V> e; K k;
  15.         // 校验插入的key是否已经存在
  16.         // 首先根据hash值匹配，在==匹配，最后equals匹配
  17.         if (p.hash == hash &&
  18.             ((k = p.key) == key || (key != null && key.equals(k))))
  19.             // key存在直接覆盖
  20.             e = p;
  21.         else if (p instanceof TreeNode)
  22.             // 如果是红黑树结构，直接往红黑树添加
  23.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  24.         else {
  25.             // 遍历链表，往链表最后一个节点追加添加的值
  26.             for (int binCount = 0; ; ++binCount) {
  27.                 // next为空时，说明是最后一个节点，往这个节点添加值
  28.                 if ((e = p.next) == null) {
  29.                     p.next = newNode(hash, key, value, null);
  30.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  31.                         // 链表深度大于8，将链表转红黑树
  32.                         treeifyBin(tab, hash);
  33.                     break;
  34.                 }
  35.                 // 先通过hash值对比，在通过==和equals()方法比较key是否存在
  36.                 // 如果存在，跳出循环
  37.                 if (e.hash == hash &&
  38.                     ((k = e.key) == key || (key != null && key.equals(k))))
  39.                     break;
  41.                 p = e;
  42.             }
  43.         }
  44.         // e!=null条件成立时，说明添加内容已经在链表中存在
  45.         // 那么将旧值替换为新值，返回旧值
  46.         if (e != null) { // existing mapping for key
  47.             V oldValue = e.value;
  48.             if (!onlyIfAbsent || oldValue == null)
  49.                 // 旧值替换为新值
  50.                 e.value = value;
  51.             afterNodeAccess(e);
  52.             return oldValue;
  53.         }
  54.     }
  55.     ++modCount;
  56.     // 键值对数量超过阈值时，则进行扩容.
  57.     // threshold 的值是根据数组长度乘以阈值得出
  58.     if (++size > threshold)
  59.         resize();
  60.     afterNodeInsertion(evict);
  61.     return null;
  62. }

扩容resize()

扩容为HashMap中很重要的一个知识点，因为我们的HashMap的底层实现是数组，数组是有长度的，我们在初始化HashMap的时候，会给数组指定一个长度，可以由构造函数指定，默认长度是16。当我们往HashMap存储的元素越多时，不进行数组扩容的话会造成hash碰撞率提高和数组链表（红黑树）的高度变高，对添加和查找的性能造成影响。所以我们会设置一个对数组最多存储多个元素的阈值，默认是：数组长度乘以0.75，存储元素的个数超过这个阈值时，会对数组进行扩容。扩容后会把原来数组中的值迁移到新的数组，这是非常耗时的，我们在开发当中设置合理的数组长度来避免扩容。

  1. final Node<K,V>[] resize() {
  2.     // 当前hashmap的数组
  3.     Node<K,V>[] oldTab = table;
  4.     // Cap 是 capacity 的缩写，容量。
  5.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.     int oldThr = threshold;
  7.     int newCap, newThr = 0; // newCap新数组长度，newThr新数组最大存储元素阈值
  8.     // 如果大于0，说明数组已经初始化过
  9.     if (oldCap > 0) {
  10.         // 数组容量不能超过最大数组长度
  11.         if (oldCap >= MAXIMUM_CAPACITY) {
  12.             // 扩容长度超过最大数组长度，不在进行扩容，还是用原来数组
  13.             threshold = Integer.MAX_VALUE;
  14.             return oldTab;
  15.         }
  16.         // 数组扩容后的长度不能超过数组最大长度
  17.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  18.                  // 扩容数组长度必须大于16
  19.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  20.             // 扩容后的数组长度是原来数组长度的2倍
  21.             newThr = oldThr << 1; // double threshold
  22.     }
  23.     else if (oldThr > 0)
  24.         // 通过有参构造方法指定了阈值时
  25.         // 数组长度为阈值长度
  26.         newCap = oldThr;
  27.     else {
  28.         // 调用无参构造方法时，默认的数组长度
  29.         // 默认阈值：数组长度*负载因子0.75
  30.         newCap = DEFAULT_INITIAL_CAPACITY;
  31.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  32.     }
  33.     if (newThr == 0) {
  34.         //  newThr为0，使用阀值公式计算容量
  35.         float ft = (float)newCap * loadFactor;
  36.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  37.                   (int)ft : Integer.MAX_VALUE);
  38.     }
  39.     // 最大存储元素个数，超过这个时会进行扩容
  40.     threshold = newThr;
  41.     @SuppressWarnings({"rawtypes","unchecked"})
  42.     // 初始化扩容后的数组
  43.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  44.     table = newTab;
  45.     // 不为空，说明数组已经有值，需要把旧数据迁移到新数组中
  46.     if (oldTab != null) {
  47.         // 遍历旧数组
  48.         for (int j = 0; j < oldCap; ++j) {
  49.             Node<K,V> e;
  50.             // 取数组下标的值
  51.             if ((e = oldTab[j]) != null) {
  52.                 // 取完之后设置为null
  53.                 oldTab[j] = null;
  54.                 // 没有next元素，说明链表只有一个值
  55.                 // 直接把值放到新的数组中
  56.                 if (e.next == null)
  57.                     // e.hash & (newCap - 1)计算数组下标
  58.                     // 把值放到这个数组对应的下标中
  59.                     newTab[e.hash & (newCap - 1)] = e;
  60.                 else if (e instanceof TreeNode)
  61.                     // 是红黑树节点
  62.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  63.                 else {
  64.                     // JDK1.8中，hash算法采用的是hashCode的高16位和低16位进行与或运算
  65.                     // 所以有一个规律：
  66.                     // 当旧数组长度是2的幂次方，且扩容后的数组长度是旧数组长度的2倍。
  67.                     // e.hash & oldCap == 0 数据迁移后数组下标不变
  68.                     // e.hash & oldCap !=0  下标为原位置(j)+旧数组长度(oldCap)
  69.                     Node<K,V> loHead = null, loTail = null; // 低位链表，数组下标不变
  70.                     Node<K,V> hiHead = null, hiTail = null; // 高位链表，数组下标为原位置+旧数组长度
  71.                     Node<K,V> next;
  72.                     do {
  73.                         // 自旋遍历链表，头插法把迁移数据
  74.                         next = e.next;
  75.                         // 低位链表，数据迁移后数组下标不变
  76.                         if ((e.hash & oldCap) == 0) {
  77.                             // 头节点为空
  78.                             if (loTail == null)
  79.                                 // 头节点
  80.                                 loHead = e;
  81.                             else
  82.                                 // 
  83.                                 loTail.next = e;
  84.                             // 放到尾节点
  85.                             loTail = e;
  86.                         }
  87.                         else {
  88.                             // 高位链表，新数组下标为原位置+旧数组长度
  89.                             // 头节点为空
  90.                             if (hiTail == null)
  91.                                 // 头节点
  92.                                 hiHead = e;
  93.                             else
  94.                                 // 旧值给链表的下一个节点
  95.                                 hiTail.next = e;
  96.                             // 把旧值赋值给新链表的尾节点
  97.                             // 当下一次取出这个尾节点时，给尾节点的下一个节点赋值
  98.                             //（这块逻辑有点绕，希望在阅读的时候需要多读多体会）
  99.                             hiTail = e;
  100.                         }
  101.                     } while ((e = next) != null); //next为空，说明是链表的最后一个节点，结束自旋
  102.                     if (loTail != null) {
  103.                         loTail.next = null;
  104.                         // 低位链表，下标位置不变
  105.                         newTab[j] = loHead;
  106.                     }
  107.                     if (hiTail != null) {
  108.                         hiTail.next = null;
  109.                         // 高位链表，数组下标为原位置+旧数组长度
  110.                         newTab[j + oldCap] = hiHead;
  111.                     }
  112.                 }
  113.             }
  114.         }
  115.     }
  116.     return newTab;
  117. }

查找get()

首先调用hash(key)获取key的hash值

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     // 获取key的hash值
  4.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  5. }

调用getNode()方法

  1. final Node<K,V> getNode(int hash, Object key) {
  2.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  3.     // hash值取余得到数组下标，取出数组下标对应的链表或红黑树
  4.     if ((tab = table) != null && (n = tab.length) > 0 &&
  5.         (first = tab[(n - 1) & hash]) != null) {
  6.         // 链表中第一个节点的hash值、key和查找的key、key的hash值相等，表示找到数据
  7.         if (first.hash == hash && // always check first node
  8.             ((k = first.key) == key || (key != null && key.equals(k))))
  9.             return first;
  10.         // 链表中下一个节点
  11.         if ((e = first.next) != null) {
  12.             if (first instanceof TreeNode)
  13.                 //是红黑树节点，从红黑树中查找节点数据
  14.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  15.             do {
  16.                 // 自旋链表，依次取出节点，直到key、hash和查找的key、hash相等
  17.                 if (e.hash == hash &&
  18.                     ((k = e.key) == key || (key != null && key.equals(k))))
  19.                     return e;
  20.             } while ((e = e.next) != null); // 如果是最后一个节点，调出字自旋
  21.         }
  22.     }
  23.     return null;
  24. }