发表于 | 分类于 ， |

背景知识

Java内存模型

JMM定义了线程和主内存之间的抽象关系：线程之间的共享变量存储在主内存中，每个线程都有一个私有的本地内存，本地内存中存储了该线程的共享变量的副本。主要目标是定义程序中各个变量的访问规则**。**

如果线程 A 和线程 B 要通信的话，要如下两个步骤：

1、线程A需要将本地内存A中的共享变量副本刷新到主内存去；

2、线程B去主内存读取线程A之前已更新过的共享变量。

JMM的特性

1）原子性：原子性指的是一个操作是不可中断的。JVM自身提供的对基本数据类型读写操作的原子性外，对于方法级别或者代码块级别的原子性操作，可以使用synchronized关键字或者重入锁(ReentrantLock)保证程序执行的原子性。

2）可见性：可见性指的是当一个线程修改了某个共享变量的值，其他线程能够马上得知这个修改的值。

3）有序性：有序性是指对于单线程的执行代码，可以认为代码的执行是按顺序依次执行的，但对于多线程环境，则可能出现乱序现象。

Happens-Before规则

除了靠sychronized和volatile关键字来保证原子性、可见性以及有序性外，JMM内部还定义一套happens-before原则来保证多线程环境下两个操作间的原子性、可见性以及有序性，happens-before 原则也是判断数据是否存在竞争、线程是否安全的依据。

happens-before 原则：指的是前一个动作的结果对后一个动作是可见的。

“Happens-before”规则都有哪些（摘自《Java并发编程实践》）：

① 程序次序法则：线程中的每个动作A都happens-before于该线程中的每一个动作B，其中，在程序中，所有的动作B都能出现在A之后。

② 监视器锁法则：对一个监视器锁的解锁 happens-before 于每一个后续对同一监视器锁的加锁。

③ volatile变量法则：对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。
④ 线程启动法则：在一个线程里，对Thread.start的调用会happens-before于每个启动线程的动作。
⑤ 线程终结法则：线程中的任何动作都happens-before于其他线程检测到这个线程已经终结、或者从Thread.join调用中成功返回，或Thread.isAlive返回false。
⑥ 中断法则：一个线程调用另一个线程的interrupt happens-before于被中断的线程发现中断。
⑦ 终结法则：一个对象的构造函数的结束happens-before于这个对象finalizer的开始。
⑧ 传递性：如果A happens-before于B，且B happens-before于C，则A happens-before于C

解释与分析

在解释该规则之前，我们先看一段多线程访问数据的代码例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test1 {
    private int a=1, b=2;
 
    public void foo(){  // 线程1 
        a=3;
        b=4;
    }
 
    public int getA(){ // 线程2
        return a;
    }    
    public int getB(){ // 线程2
        return b;
    }
}

上面的代码，当线程1执行foo方法的时候，线程2访问getA和getB会得到什么样的结果？

结果如下：

1
2
3
4
A：a=1, b=2  // 都未改变
B：a=3, b=4  // 都改变了
C：a=3, b=2  //  a改变了，b未改变
D：a=1, b=4  //  b改变了，a未改变

上面的A,B,C都好理解，但是D可能会出乎一些人的预料。
一些不了解JMM的同学可能会问怎么可能 b=4语句会先于 a=3 执行？

这是一个多线程之间内存可见性（Visibility）顺序不一致的问题，有两种可能会造成上面的D选项：

1) Java编译器的重排序(Reording)操作有可能导致执行顺序和代码顺序不一致

关于Reordering：

Java语言规范规定了JVM要维护内部线程类似顺序化语义(within-thread as-is-serial semantics)：只要程序的最终结果等同于它在严格的顺序化环境中执行的结果，那么上述所有的行为都是允许的。

简单的说：假设代码有两条语句，代码顺序是语句1先于语句2执行；那么只要语句2不依赖于语句1的结果，打乱它们的顺序对最终的结果没有影响的话，那么真正交给CPU去执行时，他们的顺序可以是没有限制的，即可以允许语句2先于语句1被CPU执行，和代码中的顺序不一致。

重排序（Reordering）是JVM针对现代CPU的一种优化，Reordering后的指令会在性能上有很大提升。(不知道这种优化对于多核CPU是否更加明显，也或许和单核多核没有关系。)

因为我们例子中的两条赋值语句，并没有依赖关系，无论谁先谁后结果都是一样的，所以就可能有Reordering的情况，这种情况下，对于其他线程来说就可能造成了可见性顺序不一致的问题。

2) 从线程工作内存写回主存时顺序无法保证

下图描述了JVM中主存和线程工作内存之间的交互：

j1

JLS中对线程和主存互操作定义了6个行为，分别为load、save、read、write、assign、use，这些操作行为具有原子性，且相互依赖，有明确的调用先后顺序。这个细节也比较繁琐，我们暂不深入追究，下面再解释。先简单认为线程在修改一个变量时，先拷贝入线程工作内存中，在线程工作内存修改后再写回主存(Main Memery)中。

下面介绍一下内存交互操作：

  • lock（锁定）：作用于主内存的变量，把一个变量标识为一条线程独占状态。
  • unlock（解锁）：作用于主内存变量，把一个处于锁定状态的变量释放出来，释放后才可以被其他线程锁定。
  • read（读取）：作用于主内存变量，把一个变量值从主内存传输到线程的工作内存中，以便随后的load动作使用。
  • load（载入）：作用于工作内存的变量，它把read操作从主内存中得到的变量值放入工作内存的变量副本中。
  • use（使用）：作用于工作内存的变量，把工作内存中的一个变量值传递给执行引擎。
  • assign（赋值）：作用于工作内存的变量，它把一个从执行引擎接收到的值赋值给工作内存的变量。
  • store（存储）：作用于工作内存的变量，把工作内存中的一个变量的值传送到主内存中，以便随后的write的操作。
  • write（写入）：作用于主内存的变量，它把store操作从工作内存中一个变量的值传送到主内存的变量中。

假设例子中Reording后顺序仍与代码中的顺序一致，那么接下来呢？有意思的事情就发生在线程把Working Copy Memery中的变量写回Main Memery的时刻，线程1把变量写回Main Memery的过程对线程2的可见性顺序也是无法保证的。
上面的例子中，a=3; b=4； 这两个语句在 Working Copy Memery中执行后，写回主存的过程对于线程2来说同样可能出现先b=4，后a=3，这样的相反顺序。

JMM为所有程序内部动作定义了一个偏序关系，叫做happens-before。要想保证执行动作B的线程看到动作A的结果（无论A和B是否发生在同一个线程中），A和B之间就必须满足happens-before关系。

上面的happens-before规则中我们重点关注的是②，③，这两条也是我们通常编程中常用的。

例如在ConcurrenHashMap中使用到锁(ReentrantLock)、Volatile、final等手段来保证happens-before规则的。

使用锁方式实现“Happens-before”是最简单，容易理解的：

j2

早期Java中的锁只有最基本的synchronized，它是一种互斥的实现方式。在Java5之后，增加了一些其它锁，比如ReentrantLock，它基本作用和synchronized相似，但提供了更多的操作方式，比如在获取锁时不必像synchronized那样只是傻等，可以设置定时，轮询，或者中断，这些方法使得它在获取多个锁的情况可以避免死锁操作。

而我们需要了解的是ReentrantLock的性能相对synchronized来说有很大的提高。在ConcurrentHashMap中，每个hash区间使用的锁正是ReentrantLock。

volatile关键字

volatile内存语义

1、保证内存可见性

2、防止指令重排

3、volatile并不保证操作的原子性

volatile保证可见性的原理是在每次访问变量时都会进行一次刷新，因此每次访问都是主内存中最新的版本。所以volatile关键字的作用之一就是保证变量修改的实时可见性。volatile关键字通过提供“内存屏障”的方式来防止指令被重排序，为了实现volatile的内存语义，编译器在生成字节码时，会在指令序列中插入内存屏障来禁止特定类型的处理器重排序。

为何要有内存屏障？

每个CPU都会有自己的缓存，缓存的目的就是为了提高性能，避免每次都要向内存取。但是这样的弊端也很明显：不能实时的和内存发生信息交换，分在不同CPU执行的不同线程对同一个变量的缓存值不同。

内存屏障是什么？

硬件层的内存屏障分为两种：Load Barrier 和 Store Barrier即读屏障和写屏障。

内存屏障有两个作用：

A.阻止屏障两侧的指令重排序；

B.强制把写缓冲区/高速缓存中的脏数据等写回主内存，让缓存中相应的数据失效。

在指令前插入Load Barrier，可以让高速缓存中的数据失效，强制从主内存加载数据；在指令后插入Store Barrier，能让写入缓存中的最新数据更新写入主内存，让其他线程可见。

java的内存屏障有四种，即LoadLoad,StoreStore,LoadStore,StoreLoad。

  • LoadLoad屏障：对于Load1; LoadLoad; Load2，在Load2及后续读取操作要读取的数据被访问前，保证Load1要读取的数据被读取完毕；
  • StoreStore屏障：对于Store1; StoreStore; Store2，在Store2及后续写入操作执行前，保证Store1的写入操作对其它处理器可见；
  • LoadStore屏障：对于Load1; LoadStore; Store2，在Store2及后续写入操作被刷出前，保证Load1要读取的数据被读取完毕；
  • StoreLoad屏障：对于Store1; StoreLoad; Load2，在Load2及后续所有读取操作执行前，保证Store1的写入对所有处理器可见。它的开销是四种屏障中最大的。在大多数处理器的实现中，这个屏障是个万能屏障，兼具其它三种内存屏障的功能。

volatile语义中的内存屏障？

1）在每个volatile写操作前插入StoreStore屏障，在写操作后插入StoreLoad屏障；

​ 在每个volatile读操作前插入LoadLoad屏障，在读操作后插入LoadStore屏障；

2）由于内存屏障的作用，避免了volatile变量和其它指令重排序、线程之间实现了通信，使得volatile表现出了锁的特性。

补充

volatile可以看做一种轻量级的锁，但又和锁有些不同。
a) 它对于多线程，不是一种互斥（mutex）关系。
b) 用volatile修饰的变量，不能保证该变量状态的改变对于其他线程来说是一种“原子化操作”。

在Java5之前，JMM对Volatile的定义是：保证读写volatile都直接发生在main memory中，线程的working memory不进行缓存。它只承诺了读和写过程的可见性，并没有对Reording做限制，所以旧的Volatile并不太可靠。在Java5之后，JMM对volatile的语义进行了增强，就是我们看到的③volatile变量法则。

那对于“原子化操作”怎么理解呢？看下面例子：

1
2
3
4
5
private static volatile int nextSerialNum = 0;
 
public static int generateSerialNumber(){
    return nextSerialNum++;
}

上面代码中对nextSerialNum使用了volatile来修饰，根据前面“Happens-Before”法则的第三条Volatile变量法则，看似不同线程都会得到一个新的serialNumber

问题出在了 nextSerialNum++ 这条语句上，它不是一个原子化的，实际上是read-modify-write三项操作，这就有可能使得在线程1在write之前，线程2也访问到了nextSerialNum，造成了线程1和线程2得到一样的serialNumber。

所以，在使用Volatile时，需要注意：
a) 需不需要互斥；
b) 对象状态的改变是不是原子化的。

final关键字

不变模式（immutable）是多线程安全里最简单的一种保障方式。因为你拿他没有办法，想改变它也没有机会。
不变模式主要通过final关键字来限定的。

在JMM中final关键字还有特殊的语义。Final域使得确保初始化安全性（initialization safety）成为可能，初始化安全性让不可变形对象不需要同步就能自由地被访问和共享。

final域的内存语义

  • 写final域的重排序规则：JMM禁止编译器在构造函数之外进行final域的写重排。编译器会在final域的写之后，构造函数的return之前，插入一个StoreStore屏障。

    写final域的重排序规则可以确保：在对象引用为任意线程可见之前，对象的final域已经被正确初始化过了。

  • 读final域的重排序规则：在一个线程中，JMM禁止处理器重排序初次读对象引用与初次读该对象包含的final域。编译器会在读final域操作的前面插入一个LoadLoad屏障。

参考：

http://www.importnew.com/21781.html

发表于 | 分类于 ， |

概述

ConcurrentHashMap是HashMap的线程安全版本的实现版本。

ConcurrentHashMap是conccurrent家族中的一个类，由于它可以高效地支持并发操作，以及被广泛使用，经典的开源框架Spring的底层数据结构就是使用ConcurrentHashMap实现的。与同是线程安全的老大哥HashTable相比，它已经更胜一筹，因为它的锁更加细化，而不是像HashTable一样为几乎每个方法都添加了synchronized锁，这样的锁无疑会影响到性能。

在JDK1.6中，ConcurrentHashMap将数据分成一段一段存储，给每一段数据配一把锁，当一个线程获得锁互斥访问一个段数据时，其他段的数据也可被其他线程访问；每个Segment拥有一把可重入锁，因此ConcurrentHashMap的分段锁数目即为Segment数组长度。

ConcurrentHashMap结构：每一个segment都是一个HashEntry<K,V>[] table， table中的每一个元素本质上都是一个HashEntry的单向队列（单向链表实现）。每一个segment都是一个HashEntry<K,V>[] table， table中的每一个元素本质上都是一个HashEntry的单向队列。

c2

本文的分析的源码是JDK8的版本，与JDK6的版本有很大的差异。实现线程安全的思想也已经完全变了，它摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现,利用CAS算法。它沿用了与它同时期的HashMap版本的思想，底层依然由“数组”+链表+红黑树的方式思想，但是为了做到并发，又增加了很多辅助的类，例如TreeBin，Traverser等对象内部类。

c1

源码分析

重要属性

首先来看几个重要的属性，与HashMap相同的就不再介绍了，这里重点解释一下sizeCtl这个属性。可以说它是ConcurrentHashMap中出镜率很高的一个属性，因为它是一个控制标识符，在不同的地方有不同用途，而且它的取值不同，也代表不同的含义。

负数代表正在进行初始化或扩容操作

  • -1代表正在初始化
  • -N 表示有N-1个线程正在进行扩容操作

正数或0代表hash表还没有被初始化

  • 表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。

它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor相对应。

相关属性的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
	
/**
    * 盛装Node元素的数组 它的大小是2的整数次幂
    * Size is always a power of two. Accessed directly by iterators.
    */
   transient volatile Node<K,V>[] table;
	
/**
    * Table initialization and resizing control.  When negative, the
    * table is being initialized or resized: -1 for initialization,
    * else -(1 + the number of active resizing threads).  Otherwise,
    * when table is null, holds the initial table size to use upon
    * creation, or 0 for default. After initialization, holds the
    * next element count value upon which to resize the table.
    * hash表初始化或扩容时的一个控制位标识量。
    * 负数代表正在进行初始化或扩容操作
    * -1代表正在初始化
    * -N 表示有N-1个线程正在进行扩容操作
    * 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小
    */
   private transient volatile int sizeCtl; 
   
   // 以下两个是用来控制扩容的时候 单线程进入的变量
   /**
    * The number of bits used for generation stamp in sizeCtl.
    * Must be at least 6 for 32bit arrays.
    */
   private static int RESIZE_STAMP_BITS = 16;
/**
    * The bit shift for recording size stamp in sizeCtl.
    */
   private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
   
   
   /*
    * Encodings for Node hash fields. See above for explanation.
    */
   static final int MOVED     = -1; // hash值是-1，表示这是一个forwardNode节点
   static final int TREEBIN   = -2; // hash值是-2  表示这时一个TreeBin节点

重要内部类

Node

Node是最核心的内部类，它包装了key-value键值对，所有插入 ConcurrentHashMap 的数据都包装在这里面。它与 HashMap 中的定义很相似，但是有一些差别。

它对 value 和 next 属性设置了volatile同步锁，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

相关源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;//带有同步锁的value
        volatile Node<K,V> next;//带有同步锁的next指针
 
        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
 
        public final K getKey()       { return key; }
        public final V getValue()     { return val; }
        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
        public final String toString(){ return key + "=" + val; }
        //不允许直接改变value的值
        public final V setValue(V value) {
            throw new UnsupportedOperationException();
        }
 
        public final boolean equals(Object o) {
            Object k, v, u; Map.Entry<?,?> e;
            return ((o instanceof Map.Entry) &&
                    (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                    (v = e.getValue()) != null &&
                    (k == key || k.equals(key)) &&
                    (v == (u = val) || v.equals(u)));
        }
 
        /**
         * Virtualized support for map.get(); overridden in subclasses.
         */
        Node<K,V> find(int h, Object k) {
            Node<K,V> e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

TreeNode

树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap继承自Node类，而并非HashMap中的继承自LinkedHashMap.Entry<K,V>类，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。

TreeBin

这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。

可以看到在构造TreeBin节点时，仅仅指定了它的hash值为TREEBIN常量，这也就是个标识为。同时也看到我们熟悉的红黑树构造方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
TreeNode<K,V> root;
      volatile TreeNode<K,V> first;
      volatile Thread waiter;
      volatile int lockState;
      // values for lockState
      static final int WRITER = 1; // set while holding write lock
      static final int WAITER = 2; // set when waiting for write lock
      static final int READER = 4; // increment value for setting read lock	
	
//省略大部分代码

/**
       * Creates bin with initial set of nodes headed by b.
       */
      TreeBin(TreeNode<K,V> b) {
          super(TREEBIN, null, null, null);
          this.first = b;
          TreeNode<K,V> r = null;
          for (TreeNode<K,V> x = b, next; x != null; x = next) {
              next = (TreeNode<K,V>)x.next;
              x.left = x.right = null;
              if (r == null) {
                  x.parent = null;
                  x.red = false;
                  r = x;
              }
              else {
                  K k = x.key;
                  int h = x.hash;
                  Class<?> kc = null;
                  for (TreeNode<K,V> p = r;;) {
                      int dir, ph;
                      K pk = p.key;
                      if ((ph = p.hash) > h)
                          dir = -1;
                      else if (ph < h)
                          dir = 1;
                      else if ((kc == null &&
                                (kc = comparableClassFor(k)) == null) ||
                               (dir = compareComparables(kc, k, pk)) == 0)
                          dir = tieBreakOrder(k, pk);
                          TreeNode<K,V> xp = p;
                      if ((p = (dir <= 0) ? p.left : p.right) == null) {
                          x.parent = xp;
                          if (dir <= 0)
                              xp.left = x;
                          else
                              xp.right = x;
                          r = balanceInsertion(r, x);
                          break;
                      }
                  }
              }
          }
          this.root = r;
          assert checkInvariants(root);
      }

ForwardingNode

一个用于连接两个table的节点类。

它包含一个 nextTable 指针，用于指向下一张表。而且这个节点的key、value、next指针全部为null，它的hash值为 -1 ，这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
    * A node inserted at head of bins during transfer operations.
    */
   static final class ForwardingNode<K,V> extends Node<K,V> {
       final Node<K,V>[] nextTable;
       ForwardingNode(Node<K,V>[] tab) {
           super(MOVED, null, null, null);
           this.nextTable = tab;
       }

       Node<K,V> find(int h, Object k) {
           // loop to avoid arbitrarily deep recursion on forwarding nodes
           outer: for (Node<K,V>[] tab = nextTable;;) {
               Node<K,V> e; int n;
               if (k == null || tab == null || (n = tab.length) == 0 ||
                   (e = tabAt(tab, (n - 1) & h)) == null)
                   return null;
               for (;;) {
                   int eh; K ek;
                   if ((eh = e.hash) == h &&
                       ((ek = e.key) == k || (ek != null && k.equals(ek))))
                       return e;
                   if (eh < 0) {
                       if (e instanceof ForwardingNode) {
                           tab = ((ForwardingNode<K,V>)e).nextTable;
                           continue outer;
                       }
                       else
                           return e.find(h, k);
                   }
                   if ((e = e.next) == null)
                       return null;
               }
           }
       }
   }

Unsafe与CAS

在ConcurrentHashMap中，随处可以看到U, 大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。

这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。

unsafe静态块

unsafe代码块控制了一些属性的修改工作，比如最常用的SIZECTL 。

在这一版本的concurrentHashMap中，大量应用来的CAS方法进行变量、属性的修改工作。利用CAS进行无锁操作，可以大大提高性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Unsafe mechanics
   private static final sun.misc.Unsafe U;
   private static final long SIZECTL;
   private static final long TRANSFERINDEX;
   private static final long BASECOUNT;
   private static final long CELLSBUSY;
   private static final long CELLVALUE;
   private static final long ABASE;
   private static final int ASHIFT;

   static {
       try {
           U = sun.misc.Unsafe.getUnsafe();
           Class<?> k = ConcurrentHashMap.class;
           SIZECTL = U.objectFieldOffset
               (k.getDeclaredField("sizeCtl"));
           TRANSFERINDEX = U.objectFieldOffset
               (k.getDeclaredField("transferIndex"));
           BASECOUNT = U.objectFieldOffset
               (k.getDeclaredField("baseCount"));
           CELLSBUSY = U.objectFieldOffset
               (k.getDeclaredField("cellsBusy"));
           Class<?> ck = CounterCell.class;
           CELLVALUE = U.objectFieldOffset
               (ck.getDeclaredField("value"));
           Class<?> ak = Node[].class;
           ABASE = U.arrayBaseOffset(ak);
           int scale = U.arrayIndexScale(ak);
           if ((scale & (scale - 1)) != 0)
               throw new Error("data type scale not a power of two");
           ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
       } catch (Exception e) {
           throw new Error(e);
       }
   }

三个核心方法

ConcurrentHashMap定义了三个原子操作，用于对指定位置的节点进行操作。正是这些原子操作保证了ConcurrentHashMap的线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	@SuppressWarnings("unchecked")
   //获得在i位置上的Node节点
   static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
       return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
   }

//利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
//在CAS算法中，会比较内存中的值与你指定的这个值是否相等，如果相等才接受你的修改，否则拒绝你的修改
//因此当前线程中的值并不是最新的值，这种修改可能会覆盖掉其他线程的修改结果  有点类似于SVN
   static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                       Node<K,V> c, Node<K,V> v) {
       return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
   }

//利用volatile方法设置节点位置的值
   static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
       U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
   }

初始化方法initTable

对于ConcurrentHashMap来说，调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候，初始化方法的调用时机是检查table==null。

初始化方法主要应用了关键属性sizeCtl 如果这个值小于0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为 -1 ，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75*n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
    * Initializes table, using the size recorded in sizeCtl.
    */
   private final Node<K,V>[] initTable() {
       Node<K,V>[] tab; int sc;
       while ((tab = table) == null || tab.length == 0) {
       //sizeCtl表示有其他线程正在进行初始化操作，把线程挂起。对于table的初始化工作，只能有一个线程在			进行。
           if ((sc = sizeCtl) < 0)
               Thread.yield(); // lost initialization race; just spin
           else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
               //利用CAS方法把sizectl的值置为-1 表示本线程正在进行初始化
               try {
                   if ((tab = table) == null || tab.length == 0) {
                       int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                       @SuppressWarnings("unchecked")
                       Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                       table = tab = nt;
                       sc = n - (n >>> 2);//相当于0.75*n 设置一个扩容的阈值
                   }
               } finally {
                   sizeCtl = sc;
               }
               break;
           }
       }
       return tab;
   }

扩容方法transfer

当ConcurrentHashMap容量不足的时候，需要对table进行扩容。这个方法的基本思想跟HashMap是很像的，但是由于它是支持并发扩容的，所以要复杂的多。原因是它支持多线程进行扩容操作，而并没有加锁。

我想这样做的目的不仅仅是为了满足concurrent的要求，而是希望利用并发处理去减少扩容带来的时间影响。因为在扩容的时候，总是会涉及到从一个“数组”到另一个“数组”拷贝的操作，如果这个操作能够并发进行，那真真是极好的了。

整个扩容操作分为两个部分：

  • 第一部分是构建一个nextTable，它的容量是原来的两倍，这个操作是单线程完成的。这个单线程的保证是通过RESIZE_STAMP_SHIFT这个常量经过一次运算来保证的，这个地方在后面会有提到；
  • 第二个部分就是将原来table中的元素复制到nextTable中，这里允许多线程进行操作。

先来看一下单线程是如何完成的：

它的大体思想就是遍历、复制的过程。

  • 首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素：
  • 如果这个位置为空，就在原table中的i位置放入forwardNode节点，这个也是触发并发扩容的关键点；
  • 如果这个位置是Node节点（fh>=0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上
  • 如果这个位置是TreeBin节点（fh<0），也做一个反序处理，并且判断是否需要untreefi，把处理的结果分别放在nextTable的i和i+n的位置上
  • 遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0.75倍 ，完成扩容。

再看一下多线程是如何完成的：

如果遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。

多线程遍历节点，处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作，而且还很好的解决了线程安全的问题。

c3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
	/**
   * 一个过渡的table表  只有在扩容的时候才会使用
   */
  private transient volatile Node<K,V>[] nextTable;
 
/**
   * Moves and/or copies the nodes in each bin to new table. See
   * above for explanation.
   */
  private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
      int n = tab.length, stride;
      if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
          stride = MIN_TRANSFER_STRIDE; // subdivide range
      if (nextTab == null) {            // initiating
          try {
              @SuppressWarnings("unchecked")
              Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];//构造一个nextTable对象 																		它的容量是原来的两倍
              nextTab = nt;
          } catch (Throwable ex) {      // try to cope with OOME
              sizeCtl = Integer.MAX_VALUE;
              return;
          }
          nextTable = nextTab;
          transferIndex = n;
      }
      int nextn = nextTab.length;
      ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);//构造一个连节点指针 用于																	  标志位
      boolean advance = true;//并发扩容的关键属性 如果等于true 说明这个节点已经处理过
      boolean finishing = false; // to ensure sweep before committing nextTab
      for (int i = 0, bound = 0;;) {
          Node<K,V> f; int fh;
          //这个while循环体的作用就是在控制i--  通过i--可以依次遍历原hash表中的节点
          while (advance) {
              int nextIndex, nextBound;
              if (--i >= bound || finishing)
                  advance = false;
              else if ((nextIndex = transferIndex) <= 0) {
                  i = -1;
                  advance = false;
              }
              else if (U.compareAndSwapInt
                       (this, TRANSFERINDEX, nextIndex,
                        nextBound = (nextIndex > stride ?
                                     nextIndex - stride : 0))) {
                  bound = nextBound;
                  i = nextIndex - 1;
                  advance = false;
              }
          }
          if (i < 0 || i >= n || i + n >= nextn) {
              int sc;
              if (finishing) {
              	//如果所有的节点都已经完成复制工作  就把nextTable赋值给table 清空临时对象						  nextTable
                  nextTable = null;
                  table = nextTab;
                  sizeCtl = (n << 1) - (n >>> 1);//扩容阈值设置为原来容量的1.5倍  依然相当于现													  在容量的0.75倍
                  return;
              }
              //利用CAS方法更新这个扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作
              if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                  if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                      return;
                  finishing = advance = true;
                  i = n; // recheck before commit
              }
          }
          //如果遍历到的节点为空 则放入ForwardingNode指针
          else if ((f = tabAt(tab, i)) == null)
              advance = casTabAt(tab, i, null, fwd);
          //如果遍历到ForwardingNode节点，说明这个点已经被处理过了，则直接跳过
          //这里是控制并发扩容的核心
          else if ((fh = f.hash) == MOVED)
              advance = true; // already processed
          else {
          		//节点上锁
              synchronized (f) {
                  if (tabAt(tab, i) == f) {
                      Node<K,V> ln, hn;
                      //如果fh>=0 证明这是一个Node节点
                      if (fh >= 0) {
                          int runBit = fh & n;
                          //以下的部分在完成的工作是构造两个链表  一个是原链表  另一个是原链表的反								 序排列
                          Node<K,V> lastRun = f;
                          for (Node<K,V> p = f.next; p != null; p = p.next) {
                              int b = p.hash & n;
                              if (b != runBit) {
                                  runBit = b;
                                  lastRun = p;
                              }
                          }
                          if (runBit == 0) {
                              ln = lastRun;
                              hn = null;
                          }
                          else {
                              hn = lastRun;
                              ln = null;
                          }
                          for (Node<K,V> p = f; p != lastRun; p = p.next) {
                              int ph = p.hash; K pk = p.key; V pv = p.val;
                              if ((ph & n) == 0)
                                  ln = new Node<K,V>(ph, pk, pv, ln);
                              else
                                  hn = new Node<K,V>(ph, pk, pv, hn);
                          }
                          //在nextTable的i位置上插入一个链表
                          setTabAt(nextTab, i, ln);
                          //在nextTable的i+n的位置上插入另一个链表
                          setTabAt(nextTab, i + n, hn);
                          //在table的i位置上插入forwardNode节点  表示已经处理过该节点
                          setTabAt(tab, i, fwd);
                          //设置advance为true 返回到上面的while循环中 就可以执行i--操作
                          advance = true;
                      }
                      //对TreeBin对象进行处理  与上面的过程类似
                      else if (f instanceof TreeBin) {
                          TreeBin<K,V> t = (TreeBin<K,V>)f;
                          TreeNode<K,V> lo = null, loTail = null;
                          TreeNode<K,V> hi = null, hiTail = null;
                          int lc = 0, hc = 0;
                          //构造正序和反序两个链表
                          for (Node<K,V> e = t.first; e != null; e = e.next) {
                              int h = e.hash;
                              TreeNode<K,V> p = new TreeNode<K,V>
                                  (h, e.key, e.val, null, null);
                              if ((h & n) == 0) {
                                  if ((p.prev = loTail) == null)
                                      lo = p;
                                  else
                                      loTail.next = p;
                                  loTail = p;
                                  ++lc;
                              }
                              else {
                                  if ((p.prev = hiTail) == null)
                                      hi = p;
                                  else
                                      hiTail.next = p;
                                  hiTail = p;
                                  ++hc;
                              }
                          }
                          //如果扩容后已经不再需要tree的结构 反向转换为链表结构
                          ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                              (hc != 0) ? new TreeBin<K,V>(lo) : t;
                          hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                              (lc != 0) ? new TreeBin<K,V>(hi) : t;
                           //在nextTable的i位置上插入一个链表    
                          setTabAt(nextTab, i, ln);
                          //在nextTable的i+n的位置上插入另一个链表
                          setTabAt(nextTab, i + n, hn);
                           //在table的i位置上插入forwardNode节点  表示已经处理过该节点
                          setTabAt(tab, i, fwd);
                          //设置advance为true 返回到上面的while循环中 就可以执行i--操作
                          advance = true;
                      }
                  }
              }
          }
      }
  }

Put方法

现在来介绍put方法，这个put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。另外由于涉及到多线程，put方法就要复杂一点。

在多线程中可能有以下两个情况：

  1. 如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；
  2. 如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。

整体流程就是首先定义不允许key或value为null的情况放入。

对于每一个放入的值，首先利用spread()方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。

  • 如果这个位置是空的，那么直接放入，而且不需要加锁操作。
  • 如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。 如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public V put(K key, V value) {
       return putVal(key, value, false);
   }

   /** Implementation for put and putIfAbsent */
   final V putVal(K key, V value, boolean onlyIfAbsent) {
   		//不允许 key或value为null
       if (key == null || value == null) throw new NullPointerException();
       //计算hash值
       int hash = spread(key.hashCode());
       int binCount = 0;
       //死循环 何时插入成功 何时跳出
       for (Node<K,V>[] tab = table;;) {
           Node<K,V> f; int n, i, fh;
           //如果table为空的话，初始化table
           if (tab == null || (n = tab.length) == 0)
               tab = initTable();
           //根据hash值计算出在table里面的位置 
           else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
           	//如果这个位置没有值 ，直接放进去，不需要加锁
               if (casTabAt(tab, i, null,
                            new Node<K,V>(hash, key, value, null)))
                   break;                   // no lock when adding to empty bin
           }
           //当遇到表连接点时，需要进行整合表的操作
           else if ((fh = f.hash) == MOVED)
               tab = helpTransfer(tab, f);
           else {
               V oldVal = null;
               //结点上锁  这里的结点可以理解为hash值相同组成的链表的头结点
               synchronized (f) {
                   if (tabAt(tab, i) == f) {
                       //fh〉0 说明这个节点是一个链表的节点 不是树的节点
                       if (fh >= 0) {
                           binCount = 1;
                           //在这里遍历链表所有的结点
                           for (Node<K,V> e = f;; ++binCount) {
                               K ek;
                               //如果hash值和key值相同  则修改对应结点的value值
                               if (e.hash == hash &&
                                   ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                   oldVal = e.val;
                                   if (!onlyIfAbsent)
                                       e.val = value;
                                   break;
                               }
                               Node<K,V> pred = e;
                               //如果遍历到了最后一个结点，那么就证明新的节点需要插入 就把它插入在									  链表尾部
                               if ((e = e.next) == null) {
                                   pred.next = new Node<K,V>(hash, key,
                                                             value, null);
                                   break;
                               }
                           }
                       }
                       //如果这个节点是树节点，就按照树的方式插入值
                       else if (f instanceof TreeBin) {
                           Node<K,V> p;
                           binCount = 2;
                           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                          value)) != null) {
                               oldVal = p.val;
                               if (!onlyIfAbsent)
                                   p.val = value;
                           }
                       }
                   }
               }
               if (binCount != 0) {
               	//如果链表长度已经达到临界值8 就需要把链表转换为树结构
                   if (binCount >= TREEIFY_THRESHOLD)
                       treeifyBin(tab, i);
                   if (oldVal != null)
                       return oldVal;
                   break;
               }
           }
       }
       //将当前ConcurrentHashMap的元素数量+1
       addCount(1L, binCount);
       return null;
   }

helpTransfer方法

这个方法被调用的时候，当前ConcurrentHashMap一定已经有了nextTable对象，首先拿到这个nextTable对象，调用transfer方法。根据上面的transfer方法可以看到，当本线程进入扩容方法的时候会直接进入复制阶段。

下面是该方法的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
   * Helps transfer if a resize is in progress.
   */
  final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
      Node<K,V>[] nextTab; int sc;
      if (tab != null && (f instanceof ForwardingNode) &&
          (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
          int rs = resizeStamp(tab.length);//计算一个操作校验码
          while (nextTab == nextTable && table == tab &&
                 (sc = sizeCtl) < 0) {
              if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                  sc == rs + MAX_RESIZERS || transferIndex <= 0)
                  break;
              if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                  transfer(tab, nextTab);
                  break;
              }
          }
          return nextTab;
      }
      return table;
  }

treeifyBin方法

这个方法用于将过长的链表转换为TreeBin对象。但是它并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要求，直接进行扩容操作并返回；如果满足条件才链表的结构抓换为TreeBin 。这与HashMap不同的是，它并没有把TreeNode直接放入红黑树，而是利用了TreeBin这个小容器来封装所有的TreeNode。

下面是该方法的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)//如果table.length<64，就扩大一倍，然															 后返回
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;
                        //构造了一个TreeBin对象 把所有Node节点包装成TreeNode放进去
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            //这里只是利用了TreeNode封装 而没有利用TreeNode的next域和parent域
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        //在原来index的位置 用TreeBin替换掉原来的Node对象
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

get方法

给定一个key来确定value的时候，必须满足两个条件：key相同且hash值相同。

对于节点可能在链表或树上的情况，需要分别去查找。

下面是该方法源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        //计算hash值
        int h = spread(key.hashCode());
        //根据hash值确定节点位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //如果搜索到的节点key与传入的key相同且不为null,直接返回这个节点	
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            //如果eh<0 说明这个节点在树上 直接寻找
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
             //否则遍历链表 找到对应的值并返回
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
}

Size相关的方法

对于ConcurrentHashMap来说，这个table里到底装了多少东西其实是个不确定的数量，因为不可能在调用size()方法的时候像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值。对于这个估计值，ConcurrentHashMap也是大费周章才计算出来的。

辅助定义

为了统计元素个数，ConcurrentHashMap定义了一些变量和一个内部类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
    * A padded cell for distributing counts.  Adapted from LongAdder
    * and Striped64.  See their internal docs for explanation.
    */
   @sun.misc.Contended static final class CounterCell {
       volatile long value;
       CounterCell(long x) { value = x; }
   }
   
 /******************************************/  
   
   /**
    * 实际上保存的是hashmap中的元素个数  利用CAS锁进行更新
    但它并不用返回当前hashmap的元素个数 
    
    */
   private transient volatile long baseCount;
   /**
    * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
    */
   private transient volatile int cellsBusy;

   /**
    * Table of counter cells. When non-null, size is a power of 2.
    */
   private transient volatile CounterCell[] counterCells;

mappingCount与Size方法

这两个方法很类似。

从Java工程师给出的注释来看，应该使用mappingCount()代替size()方法。两个方法都没有直接返回basecount，而是统计一次这个值，而这个值其实也是一个大概的数值，因此可能在统计的时候有其他线程正在执行插入或删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int size() {
       long n = sumCount();
       return ((n < 0L) ? 0 :
               (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
               (int)n);
   }
    /**
    * Returns the number of mappings. This method should be used
    * instead of {@link #size} because a ConcurrentHashMap may
    * contain more mappings than can be represented as an int. The
    * value returned is an estimate; the actual count may differ if
    * there are concurrent insertions or removals.
    *
    * @return the number of mappings
    * @since 1.8
    */
   public long mappingCount() {
       long n = sumCount();
       return (n < 0L) ? 0L : n; // ignore transient negative values
   }
   
    final long sumCount() {
       CounterCell[] as = counterCells; CounterCell a;
       long sum = baseCount;
       if (as != null) {
           for (int i = 0; i < as.length; ++i) {
               if ((a = as[i]) != null)
                   sum += a.value;//所有counter的值求和
           }
       }
       return sum;
   }

addCount方法

在put方法结尾处调用了addCount方法，把当前ConcurrentHashMap的元素个数+1。

这个方法一共做了两件事：

  • 更新baseCount的值
  • 检测是否进行扩容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private final void addCount(long x, int check) {
       CounterCell[] as; long b, s;
       //利用CAS方法更新baseCount的值 
       if ((as = counterCells) != null ||
           !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
           CounterCell a; long v; int m;
           boolean uncontended = true;
           if (as == null || (m = as.length - 1) < 0 ||
               (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
               !(uncontended =
                 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
               fullAddCount(x, uncontended);
               return;
           }
           if (check <= 1)
               return;
           s = sumCount();
       }
       //如果check值大于等于0 则需要检验是否需要进行扩容操作
       if (check >= 0) {
           Node<K,V>[] tab, nt; int n, sc;
           while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                  (n = tab.length) < MAXIMUM_CAPACITY) {
               int rs = resizeStamp(n);
               //
               if (sc < 0) {
                   if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                       sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                       transferIndex <= 0)
                       break;
                    //如果已经有其他线程在执行扩容操作
                   if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                       transfer(tab, nt);
               }
               //当前线程是唯一的或是第一个发起扩容的线程  此时nextTable=null
               else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                            (rs << RESIZE_STAMP_SHIFT) + 2))
                   transfer(tab, null);
               s = sumCount();
           }
       }
   }

参考：

https://blog.csdn.net/J_Dark/article/details/72853937

https://blog.csdn.net/u010723709/article/details/48007881

发表于 | 分类于 ， |

概述

LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。所以，要看懂 LinkedHashMap 的源码，需要先看懂 HashMap 的源码。

原理

LinkedHashMap继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表或红黑树组成，结构示意图大致如下：

l1

LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。其结构可能如下图：

l2

上图中，淡蓝色的箭头表示前驱引用，红色箭头表示后继引用。

每当有新键值对节点插入，新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上，这样一个双向链表就建立起来了。

源码分析

Entry的继承体系

在对核心内容展开分析之前，这里先插队分析一下键值对节点的继承体系。先来看看继承体系结构图：

l3

下面是LinkedHashMap.Entry的源码：

1
2
3
4
5
6
7
8
9
/**
    * HashMap.Node subclass for normal LinkedHashMap entries.
    */
   static class Entry<K,V> extends HashMap.Node<K,V> {
       Entry<K,V> before, after;
       Entry(int hash, K key, V value, Node<K,V> next) {
           super(hash, key, value, next);
       }
   }

上面的继承体系乍一看还是有点复杂的，同时也有点让人迷惑。

HashMap 的内部类 TreeNode 不继承它的了一个内部类 Node，却继承自 Node 的子类 LinkedHashMap 内部类 Entry。这里这样做是有一定原因的，这里先不说。

先来简单说明一下上面的继承体系。LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node，并新增了两个引用，分别是 before 和 after。这两个引用的用途不难理解，也就是用于维护双向链表。同时，TreeNode 继承 LinkedHashMap 的内部类 Entry 后，就具备了和其他 Entry 一起组成链表的能力。

但是这里需要大家考虑一个问题。当我们使用 HashMap 时，TreeNode 并不需要具备组成链表能力。如果继承 LinkedHashMap 内部类 Entry ，TreeNode 就多了两个用不到的引用，这样做不是会浪费空间吗？简单说明一下这个问题（水平有限，不保证完全正确），这里这么做确实会浪费空间，但与 TreeNode 通过继承获取的组成链表的能力相比，这点浪费是值得的。在 HashMap 的设计思路注释中，有这样一段话：

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used.

大致的意思是 TreeNode 对象的大小约是普通 Node 对象的2倍，我们仅在桶（bin）中包含足够多的节点时再使用。当桶中的节点数量变少时（取决于删除和扩容），TreeNode 会被转成 Node。当用户实现的 hashCode 方法具有良好分布性时，树类型的桶将会很少被使用。

通过上面的注释，我们可以了解到。一般情况下，只要 hashCode 的实现不糟糕，Node 组成的链表很少会被转成由 TreeNode 组成的红黑树。也就是说 TreeNode 使用的并不多，浪费那点空间是可接受的。假如 TreeNode 机制继承自 Node 类，那么它要想具备组成链表的能力，就需要 Node 去继承 LinkedHashMap 的内部类 Entry。这个时候就得不偿失了，浪费很多空间去获取不一定用得到的能力。

链表的建立能力

链表的建立过程是在插入键值对节点时开始的。

初始情况下，让 LinkedHashMap 的 head 和 tail 引用同时指向新节点，链表就算建立起来了。随后不断有新节点插入，通过将新节点接在 tail 引用指向节点的后面，即可实现链表的更新。

Map 类型的集合类是通过 put(K,V) 方法插入键值对，LinkedHashMap 本身并没有覆写父类的 put 方法，而是直接使用了父类的实现。但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么，LinkedHashMap 是怎样建立链表的呢？在展开说明之前，我们先看一下 LinkedHashMap 插入操作相关的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// HashMap 中实现
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// HashMap 中实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) {...}
    // 通过节点 hash 定位节点所在的桶位置，并检测桶中是否包含节点引用
    if ((p = tab[i = (n - 1) & hash]) == null) {...}
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) {...}
        else {
            // 遍历链表，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 未在单链表中找到要插入的节点，将新节点接在单链表的后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) {...}
                    break;
                }
                // 插入的节点已经存在于单链表中
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) {...}
            afterNodeAccess(e);    // 回调方法，后续说明
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) {...}
    afterNodeInsertion(evict);    // 回调方法，后续说明
    return null;
}

// HashMap 中实现
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap 中覆写
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将 Entry 接在双向链表的尾部
    linkNodeLast(p);
    return p;
}

// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // last 为 null，表明链表还未建立
    if (last == null)
        head = p;
    else {
        // 将新节点 p 接在链表尾部
        p.before = last;
        last.after = p;
    }
}

上面省略了部分非关键的代码，根据上面的代码，可以知道 LinkedHashMap 插入操作的调用过程。如下：

l4

我把 newNode(int hash, K key, V value, Node<K,V> e) 方法红色背景标注了出来，这一步比较关键。LinkedHashMap 覆写了该方法。在这个方法中，LinkedHashMap 创建了 Entry，并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。

双向链表建立之后，我们就可以按照插入顺序去遍历 LinkedHashMap，大家可以自己写点测试代码验证一下插入顺序。

以上就是 LinkedHashMap 维护插入顺序的相关分析。本节的最后，再额外补充一些东西。大家如果仔细看上面的代码的话，会发现有两个以after开头方法，在上文中没有被提及。在 JDK 1.8 HashMap 的源码中，相关的方法有3个：

1
2
3
4
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

根据这三个方法的注释可以看出，这些方法的用途是在增删查等操作后，通过回调的方式，让 LinkedHashMap 有机会做一些后置操作。上述三个方法的具体实现在 LinkedHashMap 中，本节先不分析这些实现，相关分析会在下面进行。

链表节点的删除过程

与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现。

在删除节点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表，这不是它的职责。那么删除及节点后，被删除的节点该如何从双链表中移除呢？

在删除及节点后，回调方法 afterNodeRemoval 会被调用。LinkedHashMap 覆写该方法，并在该方法中完成了移除被删除节点的操作。相关源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// HashMap 中实现
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

// HashMap 中实现
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode) {...}
            else {
                // 遍历单链表，寻找要删除的节点，并赋值给 node 变量
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) {...}
            // 将要删除的节点从单链表中移除
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);    // 调用删除回调方法进行后续操作
            return node;
        }
    }
    return null;
}

// LinkedHashMap 中覆写
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将 p 节点的前驱后后继引用置空
    p.before = p.after = null;
    // b 为 null，表明 p 是头节点
    if (b == null)
        head = a;
    else
        b.after = a;
    // a 为 null，表明 p 是尾节点
    if (a == null)
        tail = b;
    else
        a.before = b;
}

删除的过程并不复杂，上面这么多代码其实就做了三件事：

  1. 根据 hash 定位到桶位置
  2. 遍历链表或调用红黑树相关的删除方法
  3. 从 LinkedHashMap 维护的双链表中移除要删除的节点

举个例子说明一下，假如我们要删除下图键值为 3 的节点：

l5

根据 hash 定位到该节点属于3号桶，然后在对3号桶保存的单链表进行遍历。

找到要删除的节点后，先从单链表中移除该节点，如下图所示：

l6

然后再双向链表中移除该节点：

l7

访问顺序的维护过程

默认情况下，LinkedHashMap 是按插入顺序维护链表。

不过我们可以在初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可让它按访问顺序维护链表，相关的构造方法源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
    * Constructs an empty <tt>LinkedHashMap</tt> instance with the
    * specified initial capacity, load factor and ordering mode.
    *
    * @param  initialCapacity the initial capacity
    * @param  loadFactor      the load factor
    * @param  accessOrder     the ordering mode - <tt>true</tt> for
    *         access-order, <tt>false</tt> for insertion-order
    * @throws IllegalArgumentException if the initial capacity is negative
    *         or the load factor is nonpositive
    */
   public LinkedHashMap(int initialCapacity,
                        float loadFactor,
                        boolean accessOrder) {
       super(initialCapacity, loadFactor);
       this.accessOrder = accessOrder;
   }

访问顺序的原理上并不复杂，当我们调用get/getOrDefault/replace等方法时，只需要将这些方法访问的节点移动到链表的尾部即可。相应的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// LinkedHashMap 中覆写
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

// LinkedHashMap 中覆写
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        // 如果 b 为 null，表明 p 为头节点
        if (b == null)
            head = a;
        else
            b.after = a;
            
        if (a != null)
            a.before = b;
        /*
         * 这里存疑，父条件分支已经确保节点 e 不会是尾节点，
         * 那么 e.after 必然不会为 null，不知道 else 分支有什么作用
         */
        else
            last = b;
    
        if (last == null)
            head = p;
        else {
            // 将 p 接在链表的最后
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

下面举例演示一下，帮助大家理解。

假设我们访问下图键值为3的节点，访问前结构为：

l8

访问后，键值为3的节点将会被移动到双向链表的最后位置，其前驱和后继也会跟着更新。访问后的结构如下：

l9

基于 LinkedHashMap 实现缓存

前面介绍了 LinkedHashMap 是如何维护插入和访问顺序的，大家对 LinkedHashMap 的原理应该有了一定的认识。

本节我们来写一些代码实践一下，这里通过继承 LinkedHashMap 实现了一个简单的 LRU 策略的缓存。

在写代码之前，先介绍一下前置知识。

在前面分析链表建立过程时，我故意忽略了部分源码分析，本节就把忽略的部分补上，先看源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除最近最少被访问的节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

上面的源码的核心逻辑在一般情况下都不会被执行，所以之前并没有进行分析。

上面的代码做的事情比较简单，就是通过一些条件，判断是否移除最近最少被访问的节点。看到这里，大家应该知道上面两个方法的用途了。

当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。

本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class SimpleCache<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_NODE_NUM = 100;

    private int limit;

    public SimpleCache() {
        this(MAX_NODE_NUM);
    }

    public SimpleCache(int limit) {
        super(limit, 0.75f, true);
        this.limit = limit;
    }

    public V save(K key, V val) {
        return put(key, val);
    }

    public V getOne(K key) {
        return get(key);
    }

    public boolean exists(K key) {
        return containsKey(key);
    }
    
    /**
     * 判断节点数是否超限
     * @param eldest
     * @return 超限返回 true，否则返回 false
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > limit;
    }
}

测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SimpleCacheTest {

    @Test
    public void test() throws Exception {
        SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);

        for (int i = 0; i < 10; i++) {
            cache.save(i, i * i);
        }

        System.out.println("插入10个键值对后，缓存内容：");
        System.out.println(cache + "\n");

        System.out.println("访问键值为7的节点后，缓存内容：");
        cache.getOne(7);
        System.out.println(cache + "\n");

        System.out.println("插入键值为1的键值对后，缓存内容：");
        cache.save(1, 1);
        System.out.println(cache);
    }
}

测试结果如下：

l10

在测试代码中，设定缓存大小为3。在向缓存中插入10个键值对后，只有最后3个被保存下来了，其他的都被移除了。然后通过访问键值为7的节点，使得该节点被移到双向链表的最后位置。当我们再次插入一个键值对时，键值为7的节点就不会被移除。

总结

本文从 LinkedHashMap 维护双向链表的角度对 LinkedHashMap 的源码进行了分析，并在文章的结尾基于 LinkedHashMap 实现了一个简单的 Cache。在日常开发中，LinkedHashMap 的使用频率虽不及 HashMap，但它也个重要的实现。在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。

发表于 | 分类于 ， |

概述

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。

JDK1.8 以后 HashMap 由 数组+链表+红黑树 组成。JDK1.8以后HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）且总容量大于64时，将链表转化为红黑树，以减少搜索时间。

HashMap是非线程安全类，在多线程环境下可能会存在问题。

原理

HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下：

h1

对于拉链式的散列算法，其数据结构是由数组和链表（或树形结构）组成。在进行增删查等操作时，首先要定位到元素的所在桶的位置，之后再从链表中定位该元素。

比如我们要查询上图结构中是否包含元素35，步骤如下：

  1. 定位元素35所处桶的位置，index = 35 % 16 = 3
  2. 在3号桶所指向的链表中继续查找，发现35在链表中。

上面就是 HashMap 底层数据结构的原理，HashMap 基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树，底层数据结构由数组+链表变为了数组+链表+红黑树，不过本质并未变。

底层数据结构分析

JDK1.8之前

h2

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码：

1
2
3
4
5
6
7
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比一下 JDK1.7的 HashMap 的 hash 方法源码：

1
2
3
4
5
6
7
8
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

JDK1.8之后

相比于之前的版本，JDK1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）且总容量大于64时，将链表转化为红黑树，以减少搜索时间。

h3

源码分析

HashMap中的成员变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}
名称 用途
initialCapacity HashMap 初始容量
loadFactor 负载因子
threshold 当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容

相关代码如下：

1
2
3
4
5
6
7
8
9
10
/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

final float loadFactor;

/** The next size value at which to resize (capacity * load factor). */
int threshold;

如果大家去看源码，会发现 HashMap 中没有定义 initialCapacity 这个变量。这个也并不难理解，从参数名上可看出，这个变量表示一个初始容量，只是构造方法中用一次，没必要定义一个变量保存。但如果大家仔细看上面 HashMap 的构造方法，会发现存储键值对的数据结构并不是在构造方法里初始化的。这就有个疑问了，既然叫初始容量，但最终并没有用与初始化数据结构，那传这个参数还有什么用呢？

  • Node节点类源码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    // 继承自 Map.Entry<K,V>
    static class Node<K,V> implements Map.Entry<K,V> {
           final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
           final K key;//键
           V value;//值
           // 指向下一个节点
           Node<K,V> next;
           Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
            // 重写hashCode()方法
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }

            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
            // 重写 equals() 方法
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
    }

  • 树节点类源码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
            TreeNode<K,V> parent;  // 父
            TreeNode<K,V> left;    // 左
            TreeNode<K,V> right;   // 右
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;           // 判断颜色
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
            // 返回根节点
            final TreeNode<K,V> root() {
                for (TreeNode<K,V> r = this, p;;) {
                    if ((p = r.parent) == null)
                        return r;
                    r = p;
    }

构造方法

h4

HashMap 的构造方法不多，只有四个。

HashMap 构造方法做的事情比较简单，一般都是初始化一些重要变量。比如 loadFactor 和 threshold，而底层的数据结构则是延迟到插入键值对时再进行初始化。

HashMap 相关构造方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/** 构造方法 1 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/** 构造方法 2 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/** 构造方法 3 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/** 构造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

上面4个构造方法中，大家平时用的最多的应该是第一个了。

构造方法1很简单，仅将 loadFactor 变量设为默认值。

构造方法2调用了构造方法3，而构造方法3仍然只是设置了一些变量。

构造方法4则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来，这个方法不是很常用。

初始阈值的计算过程

默认情况下，HashMap 初始容量是16，负载因子为 0.75。这里并没有默认阈值，原因是阈值可由容量乘上负载因子计算而来（注释中有说明），即threshold = capacity * loadFactor。

但当你仔细看构造方法3时，会发现阈值并不是由上面公式计算而来，而是通过一个方法算出来的。这是不是可以说明 threshold 变量的注释有误呢？还是仅这里进行了特殊处理，其他地方遵循计算公式呢？关于这个疑问，这里也先不说明，后面在分析扩容方法时，再来解释这个问题。接下来，我们来看看初始化 threshold 的方法长什么样的的，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

总结起来就一句话：找到大于或等于 cap 的最小2的幂。

下面我们来看看 tableSizeFor 方法的图解：

h5

上面是 tableSizeFor 方法的计算过程图，这里cap = 536,870,913 = 2<sup>29</sup> + 1，多次计算后，算出n + 1 = 1,073,741,824 = 2<sup>30</sup>。通过图解应该可以比较容易理解这个方法的用途，这里就不多说了。

负载因子

对于 HashMap 来说，负载因子是一个很重要的参数，该参数反应了 HashMap 桶数组的使用情况（假设键值对节点均匀分布在桶数组中）。

通过调节负载因子，可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。

至于负载因子怎么调节，这个看使用场景了。一般情况下，我们用默认值就可以了。

查找

HashMap 的查找操作比较简单，查找步骤与原理篇介绍一致。

即先定位键值对所在的桶的位置，然后再对链表或红黑树进行查找。通过这两步即可完成查找，该操作相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
            // 2. 对链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

查找的核心逻辑是封装在 getNode() 方法中的，getNode() 方法源码我已经写了一些注释，应该不难看懂。

我们先来看看查找过程的第一步 - 确定桶位置，其实现代码如下：

1
2
// index = (n - 1) & hash
first = tab[(n - 1) & hash]

这里通过(n - 1)& hash即可算出桶的在桶数组中的位置，可能有的朋友不太明白这里为什么这么做，这里简单解释一下。

HashMap 中桶数组的大小 length 总是2的幂，此时，(n - 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高，所以(n - 1) & hash也是一个小的优化。

举个例子说明一下吧，假设 hash = 185，n = 16。计算过程示意图如下：

h6

在上面源码中，除了查找相关逻辑，还有一个计算 hash 的方法。这个方法源码如下：

1
2
3
4
5
6
7
/**
 * 计算键的 hash 值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看这个方法的逻辑好像是通过位运算重新计算 hash，那么这里为什么要这样做呢？

为什么不直接用键的 hashCode 方法产生的 hash 呢？

我们再看一下上面求余(上面的例子是8位二进制)的计算图，图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小，hash 只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。

为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。

通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：

h7

在 Java 中，hashCode 方法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位。

上面所说的是重新计算 hash 的一个好处。

除此之外，重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。

遍历

和查找一样，遍历操作也是大家使用频率比较高的一个操作。对于 遍历 HashMap，我们一般都会用下面的方式：

1
2
3
4
5
6
7
8
9
for(Object key : map.keySet()) {
    // do something
}

或

for(HashMap.Entry entry : map.entrySet()) {
    // do something
}

从上面代码片段中可以看出，大家一般都是对 HashMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历 keySet 方法产生的集合，在编译时会转换成用迭代器遍历，等价于：

1
2
3
4
5
6
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
    Object key = ite.next();
    // do something
}

大家在遍历 HashMap 的过程中会发现，多次对 HashMap 进行遍历时，遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的。

产生上述行为的原因是怎样的呢？大家想一下原因。我先把遍历相关的代码贴出来，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

/**
 * 键集合
 */
final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    // 省略部分代码
}

/**
 * 键迭代器
 */
final class KeyIterator extends HashIterator 
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry 
            // 寻找第一个包含链表节点引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 寻找下一个包含链表节点引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    //省略部分代码
}

如上面的源码，遍历所有的键时，首先要获取键集合KeySet对象，然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类，核心逻辑也封装在 HashIterator 类中。

HashIterator 的逻辑并不复杂。在初始化时，HashIterator 先从桶数组中找到包含链表节点引用的桶，然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。

举个例子，假设我们遍历下图的结构：

h8

HashIterator 在初始化时，会先遍历桶数组，找到包含链表节点引用的桶，对应图中就是3号桶。

随后由 nextNode 方法遍历该桶所指向的链表。遍历完3号桶后，nextNode 方法继续寻找下一个不为空的桶，对应图中的7号桶。之后流程和上面类似，直至遍历完最后一个桶。

以上就是 HashIterator 的核心逻辑的流程，对应下图：

h9

遍历上图的最终结果是 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59。

为了验证正确性，简单写点测试代码跑一下看看。测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 应在 JDK 1.8 下测试，其他环境下不保证结果和上面一致
 */
public class HashMapTest {

    @Test
    public void testTraversal() {
        HashMap<Integer, String> map = new HashMap(16);
        map.put(7, "");
        map.put(11, "");
        map.put(43, "");
        map.put(59, "");
        map.put(19, "");
        map.put(3, "");
        map.put(35, "");

        System.out.println("遍历结果：");
        for (Integer key : map.keySet()) {
            System.out.print(key + " -> ");
        }
    }
}

遍历结果如下：

h10

插入

h22

插入逻辑分析

首先肯定是先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对接在链表最后一个位置，或者更新键值对。

这就是 HashMap 的插入流程，是不是觉得很简单。当然，大家先别高兴。这只是一个简化版的插入流程，真正的插入流程要复杂不少。首先 HashMap 是变长集合，所以需要考虑扩容的问题。其次，在 JDK 1.8 中，HashMap 引入了红黑树优化过长链表，这里还要考虑多长的链表需要进行优化，优化过程又是怎样的问题。引入这里两个问题后，大家会发现原本简单的操作，现在略显复杂了。

在本节中，我将先分析插入操作的源码，扩容、树化（链表转为红黑树，下同）以及其他和树结构相关的操作，随后将在独立的两小结中进行分析。

接下来，先来看一下插入操作的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // hash值不相等，即key不相等；为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

插入操作的入口方法是 put(K,V)，但核心逻辑在V putVal(int, K, V, boolean, boolean) 方法中。

V putVal(int, K, V, boolean, boolean) 方法主要做了这么几件事情：

  1. 当桶数组 table 为空时，通过扩容的方式初始化 table
  2. 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
  3. 如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
  4. 判断键值对数量是否大于阈值，大于的话则进行扩容操作

h11

扩容机制

在 Java 中，数组的长度是固定的，这意味着数组只能存储固定量的数据。但在开发的过程中，很多时候我们无法知道该建多大的数组合适。建小了不够用，建大了用不完，造成浪费。

如果我们能实现一种变长的数组，并按需分配空间就好了。好在，我们不用自己实现变长数组，Java 集合框架已经实现了变长的数据结构，比如 ArrayList 和 HashMap。对于这类基于数组的变长数据结构，扩容是一个非常重要的操作。下面就来聊聊 HashMap 的扩容机制。

在详细分析之前，先来说一下扩容相关的背景知识：

在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。

HashMap 的扩容机制与其他变长集合的套路不太一样，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。

以上就是 HashMap 的扩容大致过程，接下来我们来看看具体的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不为空，表明已经初始化过了
    if (oldCap > 0) {
        // 当 table 容量超过容量最大值，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化时，将 threshold 的值赋值给 newCap，
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 调用无参构造方法时，桶数组容量为默认容量，
         * 阈值为默认容量与默认负载因子乘积
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0 时，按阈值计算公式进行计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 创建新的桶数组，桶数组的初始化也是在这里完成的
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新映射时，需要对红黑树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，并将链表节点按原顺序进行分组
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将分组后的链表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize()方法总共做了3件事，分别是：

  1. 计算新桶数组的容量 newCap 和新阈值 newThr
  2. 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

上面列的三点中，第二点创建新的桶数组就一行代码，不用说了。接下来，来说说第一点和第三点。

先说说 newCap 和 newThr 计算过程。该计算过程对应 resize 源码的第一和第二个条件分支，如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 第一个条件分支
if ( oldCap > 0) {
    // 嵌套条件分支
    if (oldCap >= MAXIMUM_CAPACITY) {...}
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
} 
else if (oldThr > 0) {...}
else {...}

// 第二个条件分支
if (newThr == 0) {...}

通过这两个条件分支对不同情况进行判断，进而算出不同的容量值和阈值。它们所覆盖的情况如下：

分支一：

条件 覆盖情况 备注
oldCap > 0 桶数组 table 已经被初始化
oldThr > 0 threshold > 0，且桶数组未被初始化 调用 HashMap(int) 和 HashMap(int, float) 构造方法时会产生这种情况，此种情况下 newCap = oldThr，newThr 在第二个条件分支中算出
oldCap == 0 && oldThr == 0 桶数组未被初始化，且 threshold 为 0 调用 HashMap() 构造方法会产生这种情况。

注意：这里把oldThr > 0情况单独拿出来说一下。在这种情况下，会将 oldThr 赋值给 newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。这也就解答了前面提的一个疑问：initialCapacity 参数没有被保存下来，那么它怎么参与桶数组的初始化过程的呢？

分支一中的嵌套分支：

条件 覆盖情况 备注
oldCap >= 230 桶数组容量大于或等于最大桶容量 230 这种情况下不再扩容
newCap < 230 && oldCap > 16 新桶数组容量小于最大值，且旧桶数组容量大于 16 该种情况下新阈值 newThr = oldThr << 1，移位可能会导致溢出

这里简单说明一下移位导致的溢出情况，当 loadFactor小数位为 0，整数位可被2整除且大于等于8时，在某次计算中就可能会导致 newThr 溢出归零。见下图：

h12

分支二：

条件 覆盖情况 备注
newThr == 0 第一个条件分支未计算 newThr 或嵌套分支在计算过程中导致 newThr 溢出归零

说完 newCap 和 newThr 的计算过程，接下来再来分析一下键值对节点重新映射的过程。

在 JDK 1.8 中，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。关于红黑树拆分的逻辑将会放在下一小节说明，先来看看链表是怎样进行分组映射的。

我们都知道往底层数据结构中插入节点时，一般都是先通过模运算计算桶位置，接着把节点放入桶中即可。事实上，我们可以把重新映射看做插入操作。在 JDK 1.7 中，也确实是这样做的。但在 JDK 1.8 中，则对这个过程进行了一定的优化，逻辑上要稍微复杂一些。在详细分析前，我们先来回顾一下 hash 求余的过程：

h13

上图中，桶数组大小 n = 16，hash1 与 hash2 不相等。但因为只有后4位参与求余，所以结果相等。当桶数组扩容后，n 由16变成了32，对上面的 hash 值重新进行映射：

h14

扩容后，参与模运算的位数由4位变为了5位。由于两个 hash 第5位的值是不一样，所以两个 hash 算出的结果也不一样。上面的计算过程并不难理解，继续往下分析。

h15

假设我们上图的桶数组进行扩容，扩容后容量 n = 16，重新映射过程如下:

依次遍历链表，并计算节点 hash & oldCap 的值，如下图所示：

h16

如果值为0，将 loHead 和 loTail 指向这个节点。如果后面还有节点 hash & oldCap 为0的话，则将节点链入 loHead 指向的链表中，并将 loTail 指向该节点。如果值为非0的话，则让 hiHead 和 hiTail 指向该节点。完成遍历后，可能会得到两条链表，此时就完成了链表分组：

h17

最后再将这两条链接存放到相应的桶中，完成扩容。如下图：

h18

从上图可以发现，重新映射后，两条链表中的节点顺序并未发生变化，还是保持了扩容前的顺序。以上就是 JDK 1.8 中 HashMap 扩容的代码讲解。另外再补充一下，JDK 1.8 版本下 HashMap 扩容效率要高于之前版本。如果大家看过 JDK 1.7 的源码会发现，JDK 1.7 为了防止因 hash 碰撞引发的拒绝服务攻击，在计算 hash 过程中引入随机种子。以增强 hash 的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方法会根据容量判断是否需要生成新的随机种子，并重新计算所有节点的 hash。而在 JDK 1.8 中，则通过引入红黑树替代了该种方式。从而避免了多次计算 hash 的操作，提高了扩容效率。

链表树化、红黑树链化与拆分

JDK 1.8 对 HashMap 实现进行了改进。最大的改进莫过于在引入了红黑树处理频繁的碰撞，代码复杂度也随之上升。比如，以前只需实现一套针对链表操作的方法即可。而引入红黑树后，需要另外实现红黑树相关的操作。红黑树是一种自平衡的二叉查找树，本身就比较复杂。

在展开说明之前，先把树化的相关代码贴出来，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
static final int TREEIFY_THRESHOLD = 8;

/**
 * 当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

/**
 * 将普通节点链表转换成树形节点链表
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 为头节点（head），tl 为尾节点（tail）
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将普通节点替换成树形节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);  // 将普通链表转成由树形节点链表
        if ((tab[index] = hd) != null)
            // 将树形链表转换成红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

在扩容过程中，树化要满足两个条件：

  1. 链表长度大于等于 TREEIFY_THRESHOLD
  2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY

第一个条件比较好理解，这里就不说了。这里来说说加入第二个条件的原因，个人觉得原因如下：

当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

回到上面的源码中，我们继续看一下 treeifyBin 方法。该方法主要的作用是将普通链表转成为由 TreeNode 型节点组成的链表，并在最后调用 treeify 是将该链表转为红黑树。TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。我们假设树化前，链表结构如下：

h19

HashMap 在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。

为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下：

  1. 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
  2. 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
  3. 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder（大家自己看源码吧）

tie break 是网球术语，可以理解为加时赛的意思，起这个名字还是挺有意思的。

通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：

h20

橙色的箭头表示 TreeNode 的 next 引用。由于空间有限，prev 引用未画出。可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。这样的结构为后面红黑树的切分以及红黑树转成链表做好了铺垫，我们继续往下分析。

  • 红黑树拆分

    扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，HashMap 实现的思路则是上好佳（上好佳请把广告费打给我）。如上节所说，在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。

    以上就是红黑树拆分的逻辑，下面看一下具体实现吧：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    // 红黑树转链表阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        /* 
         * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
         * 下面的循环是对红黑树节点进行分组，与上面类似
         */
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }

        if (loHead != null) {
            // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead;
                /* 
                 * hiHead == null 时，表明扩容后，
                 * 所有节点仍在原位置，树结构不变，无需重新树化
                 */
                if (hiHead != null) 
                    loHead.treeify(tab);
            }
        }
        // 与上面类似
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

    从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。

    举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：

    h21

  • 红黑树链化

    前面说过，红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。相关代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    final Node<K,V> untreeify(HashMap<K,V> map) {
        Node<K,V> hd = null, tl = null;
        // 遍历 TreeNode 链表，并用 Node 替换
        for (Node<K,V> q = this; q != null; q = q.next) {
            // 替换节点类型
            Node<K,V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

删除

HashMap 的删除操作并不复杂，仅需三个步骤即可完成。

第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。

相关源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {  
            // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 2. 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 3. 删除节点，并修复链表或红黑树
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

其他细节

被 transient 所修饰 table 变量

如果大家细心阅读 HashMap 的源码，会发现桶数组 table 被声明为 transient。

transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。

我们再回到源码中，考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，别人还怎么还原呢？这里简单说明一下吧，HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap 中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建 HashMap。有的朋友可能会想，序列化 table 不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化 talbe 存在着两个问题：

  1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
  2. 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。

以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 继续操作，就会出现问题。

综上所述，大家应该能明白 HashMap 不序列化 table 的原因了。

非线程安全的表现

数据覆盖

如果有A、B两个线程同时对hashMap进行插入操作，刚好插入的数据经过哈希计算后得到的哈希码相同，且该位置还没有其他的数据。假设A在完成hash冲突检测后就把资源让给了线程B，此时B判断该位置没有哈希冲突（线程A的数据还没插入），就完成了数据插入，之后A又得到了资源，将直接在该位置插入而不用再判断。这时候，线程A把线程B插入的数据覆盖了。

死锁问题

假设有二个进程T1、T2，HashMap容量为2，T1线程放入key A、C、D、E。在T1线程中A、C Hash值相同，于是形成一个链接，假设为A->C，而D、E Hash值不同，于是需要扩容，需要把数据从老的Hash表中迁移到新的Hash表中(refresh)。这时T2进程闯进来了，T1暂时挂起，T2进程也准备放入新的key，这时也发现容量不足，也refresh一把。refresh之后原来的链表结构假设为C->A，之后T1进程继续执行，链接结构为A->C，这时就形成A.next = C,B.next = A的环形链表。一旦取值进入这个环形链表就会陷入死循环。

参考：

http://www.tianxiaobo.com/2018/01/18/HashMap-%E6%BA%90%E7%A0%81%E8%AF%A6%E7%BB%86%E5%88%86%E6%9E%90-JDK1-8/#4-%E5%86%99%E5%9C%A8%E6%9C%80%E5%90%8E

https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/HashMap.md

发表于 | 分类于 ， |

概述

LinkedList 是 Java 集合框架中一个重要的实现，其底层采用的双向链表结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

   /**
    * Pointer to first node.
    * Invariant: (first == null && last == null) ||
    *            (first.prev == null && first.item != null)
    */
   transient Node<E> first;

   /**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
   transient Node<E> last;

和 ArrayList 一样，LinkedList 也支持空值和重复值。

由于 LinkedList 基于链表实现，存储元素过程中，无需像 ArrayList 那样进行扩容。但有得必有失，LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面，LinkedList 在链表头部和尾部插入效率比较高，但在指定位置进行插入时，效率一般。原因是，在指定位置插入需要定位到该位置处的节点，此操作的时间复杂度为O(N)。

最后，LinkedList 是非线程安全的集合类，并发环境下，多个线程同时操作 LinkedList，会引发不可预知的错误。如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：

1
List list=Collections.synchronizedList(new LinkedList(...));

内部结构分析

LinkedList类中的一个内部私有类Node，这个类就代表双端链表的节点Node：

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
        E item;//节点值
        Node<E> next;//后继节点
        Node<E> prev;//前驱节点

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

l1

继承体系

LinkedList的继承体系较为复杂，继承自 AbstractSequentialList，同时又实现了 List 和 Deque 接口。

LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有

队列的特性，我们可以这样使用：

1
Queue<T> queue = new LinkedList<>();

继承体系图如下（删除了部分实现的接口）：

l2

LinkedList继承自 AbstractSequentialList ，AbstractSequentialList 又是什么呢？从实现上，AbstractSequentialList提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。深入源码，AbstractSequentialList 提供的方法基本上都是通过 ListIterator实现的，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected AbstractSequentialList() {
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * <p>This implementation first gets a list iterator pointing to the
     * indexed element (with <tt>listIterator(index)</tt>).  Then, it gets
     * the element using <tt>ListIterator.next</tt> and returns it.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        try {
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified element (optional operation).
     *
     * <p>This implementation first gets a list iterator pointing to the
     * indexed element (with <tt>listIterator(index)</tt>).  Then, it gets
     * the current element using <tt>ListIterator.next</tt> and replaces it
     * with <tt>ListIterator.set</tt>.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the list iterator does not
     * implement the <tt>set</tt> operation.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public E set(int index, E element) {
        try {
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    /**
     * Inserts the specified element at the specified position in this list
     * (optional operation).  Shifts the element currently at that position
     * (if any) and any subsequent elements to the right (adds one to their
     * indices).
     *
     * <p>This implementation first gets a list iterator pointing to the
     * indexed element (with <tt>listIterator(index)</tt>).  Then, it
     * inserts the specified element with <tt>ListIterator.add</tt>.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the list iterator does not
     * implement the <tt>add</tt> operation.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public void add(int index, E element) {
        try {
            listIterator(index).add(element);
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    /**
     * Removes the element at the specified position in this list (optional
     * operation).  Shifts any subsequent elements to the left (subtracts one
     * from their indices).  Returns the element that was removed from the
     * list.
     *
     * <p>This implementation first gets a list iterator pointing to the
     * indexed element (with <tt>listIterator(index)</tt>).  Then, it removes
     * the element with <tt>ListIterator.remove</tt>.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the list iterator does not
     * implement the <tt>remove</tt> operation.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public E remove(int index) {
        try {
            ListIterator<E> e = listIterator(index);
            E outCast = e.next();
            e.remove();
            return outCast;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }


    // Bulk Operations

    /**
     * Inserts all of the elements in the specified collection into this
     * list at the specified position (optional operation).  Shifts the
     * element currently at that position (if any) and any subsequent
     * elements to the right (increases their indices).  The new elements
     * will appear in this list in the order that they are returned by the
     * specified collection's iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the
     * operation is in progress.  (Note that this will occur if the specified
     * collection is this list, and it's nonempty.)
     *
     * <p>This implementation gets an iterator over the specified collection and
     * a list iterator over this list pointing to the indexed element (with
     * <tt>listIterator(index)</tt>).  Then, it iterates over the specified
     * collection, inserting the elements obtained from the iterator into this
     * list, one at a time, using <tt>ListIterator.add</tt> followed by
     * <tt>ListIterator.next</tt> (to skip over the added element).
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the list iterator returned by
     * the <tt>listIterator</tt> method does not implement the <tt>add</tt>
     * operation.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        try {
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            Iterator<? extends E> e2 = c.iterator();
            while (e2.hasNext()) {
                e1.add(e2.next());
                modified = true;
            }
            return modified;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }


    // Iterators

    /**
     * Returns an iterator over the elements in this list (in proper
     * sequence).<p>
     *
     * This implementation merely returns a list iterator over the list.
     *
     * @return an iterator over the elements in this list (in proper sequence)
     */
    public Iterator<E> iterator() {
        return listIterator();
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence).
     *
     * @param  index index of first element to be returned from the list
     *         iterator (by a call to the <code>next</code> method)
     * @return a list iterator over the elements in this list (in proper
     *         sequence)
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public abstract ListIterator<E> listIterator(int index);
}

所以只要继承类实现了 listIterator 方法，它不需要再额外实现什么即可使用。

对于随机访问集合类一般建议继承 AbstractList 而不是 AbstractSequentialList。

LinkedList和其父类一样，也是基于顺序访问。所以 LinkedList 继承了AbstractSequentialList，但 LinkedList 并没有直接使用父类的方法，而是重新实现了一套的方法。

源码分析

构造方法

LinkedList有两个构造方法，一个是空构造方法，一个是用已有的集合创建链表的构造方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
    * Constructs an empty list.
    */
public LinkedList() {
   }

   /**
    * Constructs a list containing the elements of the specified
    * collection, in the order they are returned by the collection's
    * iterator.
    *
    * @param  c the collection whose elements are to be placed into this list
    * @throws NullPointerException if the specified collection is null
    */
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

查找

LinkedList 底层基于链表结构，无法向 ArrayList 那样随机访问指定位置的元素。

LinkedList 查找过程要稍麻烦一些，需要从链表头结点（或尾节点）向后（向前）查找，时间复杂度为 `O(N)`。相关源码如下：

根据指定位置取数据的方法

get(int index)： 根据指定索引返回数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public E get(int index) {
        //检查index范围是否在size之内
        checkElementIndex(index);
        //调用Node(index)去找到index对应的node然后返回它的值
        return node(index).item;
}

Node<E> node(int index) {
    /*
     * 则从头节点开始查找，否则从尾节点查找
     * 查找位置 index 如果小于节点数量的一半，
     */    
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 循环向后查找，直至 i == index
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

上面的代码比较简单，主要是通过遍历的方式定位目标位置的节点。获取到节点后，取出节点存储的值返回即可。这里面有个小优化，即通过比较 index 与节点数量 size/2 的大小，决定从头结点还是尾节点进行查找。

获取头结点(index = 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
}

public E element() {
        return getFirst();
}

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
}

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
}

区别： getFirst()，element()，peek()，peekFirst() 这四个获取头结点方法的区别在于对链表为空时的处理，是抛出异常还是返回null。

其中getFirst() 和element() 方法将会在链表为空时，抛出NoSuchElementException。

获取尾结点(index = -1)

1
2
3
4
5
6
7
8
9
10
11
public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
}

public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
}

两者区别： getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。

根据对象得到索引的方法

int indexOf(Object o)： 从头遍历找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            //从头遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            //从头遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
}

int lastIndexOf(Object o)： 从尾遍历找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            //从尾遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            //从尾遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
}

检查链表是否包含某对象

contains(Object o)： 检查对象o是否存在于链表中

1
2
3
4
5
6
7
8
9
10
11
12
/**
    * Returns {@code true} if this list contains the specified element.
    * More formally, returns {@code true} if and only if this list contains
    * at least one element {@code e} such that
    * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
    *
    * @param o element whose presence in this list is to be tested
    * @return {@code true} if this list contains the specified element
    */
   public boolean contains(Object o) {
       return indexOf(o) != -1;
   }

遍历

链表的遍历过程也很简单，和上面查找过程类似，我们从头节点往后遍历就行了。但对于 LinkedList 的遍历还是需要注意一些，不然可能会导致代码效率低下。通常情况下，我们会使用 for each 遍历 LinkedList，而 for each 最终转换成迭代器形式。所以分析 LinkedList 的遍历的核心就是它的迭代器实现，相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    /** 构造方法将 next 引用指向指定位置的节点 */
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;    // 调用 next 方法后，next 引用都会指向他的后继节点
        nextIndex++;
        return lastReturned.item;
    }
    
    // 省略部分方法
}

插入

LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。

LinkedList 插入元素的过程实际上就是链表链入节点的过程，下面我们分析 List 接口中相关的插入方法：

将元素添加到链表尾部

add(E e) 方法：将元素添加到链表尾部

在指定位置添加元素

add(int index,E e)：在指定位置添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/** 在链表尾部插入元素 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/** 在链表指定位置插入元素 */
public void add(int index, E element) {
    checkPositionIndex(index);//检查索引是否处于[0-size]之间

    // 判断 index 是不是链表尾部位置，如果是，直接将元素节点插入链表尾部即可
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/** 将元素节点插入到链表尾部 */
void linkLast(E e) {
    final Node<E> l = last;
    // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;    // 让原尾节点后继引用 next 指向新的尾节点
    size++;
    modCount++;
}

/** 将元素节点插入到 succ 之前的位置 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    // 1. 初始化节点，并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 2. 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点    
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;   // 3. succ 节点前驱的后继引用指向新节点
    size++;
    modCount++;
}

上面是插入过程的源码，我对源码进行了比较详细的注释，应该不难看懂。上面两个 add 方法只是对操作链表的方法做了一层包装，核心逻辑在 linkBefore 和 linkLast 中。

这里以 linkBefore 为例，linkBefore方法需要给定两个参数，一个插入节点的值，一个指定的node，所以我们又调用了Node(index)去找到index对应的node，它的逻辑流程如下：

  1. 创建新节点，并指明新节点的前驱和后继
  2. 将 succ 的前驱引用指向新节点
  3. 如果 succ 的前驱不为空，则将 succ 前驱的后继引用指向新节点

对应于下图：

l3

将集合插到链表尾部

addAll(Collection c )：将集合插入到链表尾部

1
2
3
public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
}

将集合从指定位置开始插入

addAll(int index, Collection c)： 将集合从指定位置开始插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public boolean addAll(int index, Collection<? extends E> c) {
        //1:检查index范围是否在size之内
        checkPositionIndex(index);

        //2:toArray()方法把集合的数据存到对象数组中
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        //3：得到插入位置的前驱节点和后继节点
        Node<E> pred, succ;
        //如果插入位置为尾部，前驱节点为last，后继节点为null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //否则，调用node()方法得到后继节点，再得到前驱节点
        else {
            succ = node(index);
            pred = succ.prev;
        }

        // 4：遍历数据将数据插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //创建新节点
            Node<E> newNode = new Node<>(pred, e, null);
            //如果插入位置在链表头部
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        //如果插入位置在尾部，重置last节点
        if (succ == null) {
            last = pred;
        }
        //否则，将插入的链表与先前链表连接起来
        else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
}

上面可以看出addAll()方法通常包括下面四个步骤：

  1. 检查index范围是否在size之内
  2. toArray()方法把集合的数据存到对象数组中
  3. 得到插入位置的前驱和后继节点
  4. 遍历数据，将数据插入到指定位置

将元素添加到链表头部

addFirst(E e)： 将元素添加到链表头部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void addFirst(E e) {
        linkFirst(e);
}

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//新建节点，以头节点为后继节点
        first = newNode;
        //如果链表为空，last节点也指向该节点
        if (f == null)
            last = newNode;
        //否则，将头节点的前驱指针指向新节点，也就是指向前一个元素
        else
            f.prev = newNode;
        size++;
        modCount++;
}

将元素添加到链表尾部

addLast(E e)： 将元素添加到链表尾部，与 add(E e) 方法一样

1
2
3
public void addLast(E e) {
        linkLast(e);
}

删除

如果大家看懂了上面的插入源码分析，那么再看删除操作实际上也很简单了。删除操作通过解除待删除节点与前后节点的链接，即可完成任务。过程比较简单，看源码吧：

删除指定元素

remove(Object o): 删除指定元素

删除指定位置的元素

remove(int index)：删除指定位置的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//删除指定元素
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 遍历链表，找到要删除的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);    // 将节点从链表中移除
                return true;
            }
        }
    }
    return false;
}

//删除指定位置的元素
public E remove(int index) {
    checkElementIndex(index);
    // 通过 node 方法定位节点，并调用 unlink 将节点从链表中移除
    return unlink(node(index));
}

/** 将某个节点从链表中移除 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    // prev 为空，表明删除的是头节点
    if (prev == null) {
        first = next;
    } else {
        // 将 x 的前驱的后继指向 x 的后继
        prev.next = next;
        // 将 x 的前驱引用置空，断开与前驱的链接
        x.prev = null;
    }

    // next 为空，表明删除的是尾节点
    if (next == null) {
        last = prev;
    } else {
        // 将 x 的后继的前驱指向 x 的前驱
        next.prev = prev;
        // 将 x 的后继引用置空，断开与后继的链接
        x.next = null;
    }

    // 将 item 置空，方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

和插入操作一样，删除操作方法也是对底层方法的一层保证，核心逻辑在底层 unlink 方法中。所以长驱直入，直接分析 unlink 方法吧。unlink 方法的逻辑如下（假设删除的节点既不是头节点，也不是尾节点）：

  1. 将待删除节点 x 的前驱的后继指向 x 的后继
  2. 将待删除节点 x 的前驱引用置空，断开与前驱的链接
  3. 将待删除节点 x 的后继的前驱指向 x 的前驱
  4. 将待删除节点 x 的后继引用置空，断开与后继的链接

对应下图：

l4

删除头节点

remove() ，removeFirst()，pop()： 删除头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
   public E pop() {
           return removeFirst();
   }

   public E remove() {
           return removeFirst();
   }

   public E removeFirst() {
           final Node<E> f = first;
           if (f == null)
               throw new NoSuchElementException();
           return unlinkFirst(f);
   }

/**
    * Unlinks non-null first node f.
    */
   private E unlinkFirst(Node<E> f) {
       // assert f == first && f != null;
       final E element = f.item;
       final Node<E> next = f.next;
       f.item = null;
       f.next = null; // help GC
       first = next;
       if (next == null)
           last = null;
       else
           next.prev = null;
       size--;
       modCount++;
       return element;
   }

删除尾节点

removeLast()，pollLast()： 删除尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   public E removeLast() {
           final Node<E> l = last;
           if (l == null)
               throw new NoSuchElementException();
           return unlinkLast(l);
   }

   public E pollLast() {
           final Node<E> l = last;
           return (l == null) ? null : unlinkLast(l);
   }

/**
    * Unlinks non-null last node l.
    */
   private E unlinkLast(Node<E> l) {
       // assert l == last && l != null;
       final E element = l.item;
       final Node<E> prev = l.prev;
       l.item = null;
       l.prev = null; // help GC
       last = prev;
       if (prev == null)
           first = null;
       else
           prev.next = null;
       size--;
       modCount++;
       return element;
   }

区别： 区别在于对于链表为空时的处理，removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。

参考：

http://www.tianxiaobo.com/2018/01/31/LinkedList-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-JDK-1-8/#4%E6%80%BB%E7%BB%93

https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/LinkedList.md

发表于 | 分类于 ， |

概述

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

在我们学数据结构的时候就知道了线性表的顺序存储，插入删除元素的时间复杂度为O(n),求表长以及增加元素，取第 i 元素的时间复杂度为O(1)

  • ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
  • ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
  • ArrayList 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
  • ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。
  • 和 Vector 不同，ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

源码分析

构造方法

ArrayList有三个构造方法，相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
private static final long serialVersionUID = 8683452581122892189L;

   /**
    * 默认初始容量大小
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * 空数组（用于空实例）。
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

    //用于默认大小空实例的共享空数组实例。
    //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * 保存ArrayList数据的数组
    */
   transient Object[] elementData; // non-private to simplify nested class access

   /**
    * ArrayList 所包含的元素个数
    */
   private int size;

   /**
    * 带初始容量参数的构造函数。（用户自己指定容量）
    */
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           //创建initialCapacity大小的数组
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           //创建空数组
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }

   /**
    *默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
    */
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

   /**
    * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
    */
   public ArrayList(Collection<? extends E> c) {
       //
       elementData = c.toArray();
       //如果指定集合元素个数不为0
       if ((size = elementData.length) != 0) {
           // c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断，
           //这里用到了反射里面的getClass()方法
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           // 用空数组代替
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

上面的代码比较简单，三个构造方法做的事情并不复杂，目的都是初始化底层数组 elementData。

区别在于无参构造方法会将 elementData 初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组。而有参的构造方法则会将 elementData 初始化为参数值大小（>= 0）的数组。一般情况下，我们用默认的构造方法即可。倘若在可知道将会向 ArrayList 插入多少元素的情况下，应该使用有参构造方法。按需分配，避免浪费。

方法参数为Collection集合的构造参数旨在构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

插入

对于数组（线性表）结构，插入操作分为两种情况。一种是在元素序列尾部插入，另一种是在元素序列其他位置插入。ArrayList 的源码里也体现了这两种插入情况，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
    * 将指定的元素追加到此列表的末尾。 
    */
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //这里看到ArrayList添加元素的实质就相当于为数组赋值
       elementData[size++] = e;
       return true;
   }

   /**
    * 在此列表中的指定位置插入指定的元素。 
    *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
    *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
    */
   public void add(int index, E element) {
       rangeCheckForAdd(index);
	//检测是否需要扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
       System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
       elementData[index] = element;
       size++;
   }

  • 对于在元素序列尾部插入，这种情况比较简单，只需两个步骤即可：

    1. 检测数组是否有足够的空间插入
    2. 将新元素插入至序列尾部

    如下图：

    a1

  • 如果是在元素序列指定位置（假设该位置合理）插入，则情况稍微复杂一点，需要三个步骤：

    1. 检测数组是否有足够的空间
    2. 将 index 及其之后的所有元素向后移一位
    3. 将新元素插入至 index 处

    如下图：

    a2

总结：从上图可以看出，将新元素插入至序列指定位置，需要先将该位置及其之后的元素都向后移动一位，为新元素腾出位置。这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二个插入方法。

删除

不同于插入操作，ArrayList 没有无参删除方法。所以其只能删除指定位置的元素或删除指定元素，这样就无法避免移动元素（除非从元素序列的尾部删除）。相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
    * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。 
    */
   public E remove(int index) {
       rangeCheck(index);

       modCount++;
       E oldValue = elementData(index);

       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
     //从列表中删除的元素 
       return oldValue;
   }

   /**
    * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
    *返回true，如果此列表包含指定的元素
    */
   public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   }

   /*
    * Private remove method that skips bounds checking and does not
    * return the value removed.
    */
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
   }

   /**
    * 从列表中删除所有元素。 
    */
   public void clear() {
       modCount++;

       // 把数组中所有的元素的值设为null
       for (int i = 0; i < size; i++)
           elementData[i] = null;

       size = 0;
   }

上面的删除方法并不复杂，这里以第一个删除方法为例，删除一个元素步骤如下：

  1. 获取指定位置 index 处的元素值
  2. 将 index + 1 及之后的元素向前移动一位
  3. 将最后一个元素置空，并将 size 值减 1
  4. 返回被删除值，完成删除操作

如下图：

a3

现在，考虑这样一种情况。我们往 ArrayList 插入大量元素后，又删除很多元素，此时底层数组会空闲处大量的空间。因为 ArrayList 没有自动缩容机制，导致底层数组大量的空闲空间不能被释放，造成浪费。对于这种情况，ArrayList 也提供了相应的处理方法，如下：

1
2
3
4
5
6
7
8
9
10
11
/**
    * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存		   储。 
    */
   public void trimToSize() {
       modCount++;
       if (size < elementData.length) {
           elementData = (size == 0)
             ? EMPTY_ELEMENTDATA
             : Arrays.copyOf(elementData, size);
       }
   }

通过上面的方法，我们可以手动触发 ArrayList 的缩容机制。这样就可以释放多余的空间，提高空间利用率。

如下图：

a4

扩容

对于变长数据结构，当结构中没有空余空间可供使用时，就需要进行扩容。在 ArrayList 中，当空间用完，其会按照原数组空间的1.5倍进行扩容。相关源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能，如果每次只扩充一个，
//那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
   /**
    * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
    * @param   minCapacity   所需的最小容量
    */
   public void ensureCapacity(int minCapacity) {
       int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
           // any size if not default element table
           ? 0
           // larger than default for default empty table. It's already
           // supposed to be at default size.
           : DEFAULT_CAPACITY;

       if (minCapacity > minExpand) {
           ensureExplicitCapacity(minCapacity);
       }
   }
/** 计算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
   	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
       	return Math.max(DEFAULT_CAPACITY, minCapacity);
   	}
   	return minCapacity;
   }

/** 扩容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
   	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
 	//判断是否需要扩容
   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;

       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           //调用grow方法进行扩容，调用此方法代表已经开始扩容了
           grow(minCapacity);
   }

   /**
    * 要分配的最大数组大小
    */
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   /**
    * ArrayList扩容的核心方法。
    */
   private void grow(int minCapacity) {
       // oldCapacity为旧容量，newCapacity为新容量
       int oldCapacity = elementData.length;
       //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
       //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       //再检查新容量是否超出了ArrayList所定义的最大容量，
       //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
       //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   //比较minCapacity和 MAX_ARRAY_SIZE
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }

接下来我们一步步分析ArrayList扩容机制，这里以无参构造函数创建的 ArrayList 为例分析。

  1. 先来看看add 方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
        * 将指定的元素追加到此列表的末尾。 
        */
       public boolean add(E e) {
      //添加元素之前，先调用ensureCapacityInternal方法
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           //这里看到ArrayList添加元素的实质就相当于为数组赋值
           elementData[size++] = e;
           return true;
       }

  2. 再来看看ensureCapacityInternal() 方法

    可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
               return Math.max(DEFAULT_CAPACITY, minCapacity);
           }
           return minCapacity;
       }
       
       private void ensureCapacityInternal(int minCapacity) {
           ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
       }

    当要add进第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity 为10。

  3. ensureExplicitCapacity()方法

    如果调用 ensureCapacityInternal() 方法就一定会执行grow()方法，下面我们来研究一下这个方法的源码！

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //判断是否需要扩容
       private void ensureExplicitCapacity(int minCapacity) {
           modCount++;
       
           // overflow-conscious code
           if (minCapacity - elementData.length > 0)
               //调用grow方法进行扩容，调用此方法代表已经开始扩容了
               grow(minCapacity);
       }

    我们来仔细分析一下：

    • 当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0（因为还是一个空的 list ），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
    • 当add第2个元素时，minCapacity 为2，此时elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0不成立，所以不会进入（执行）grow(minCapacity) 方法。
    • 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。

    直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大，进入grow方法进行扩容。

  4. grow()方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /**
        * 要分配的最大数组大小
        */
       private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
       
       /**
        * ArrayList扩容的核心方法。
        */
       private void grow(int minCapacity) {
           // oldCapacity为旧容量，newCapacity为新容量
           int oldCapacity = elementData.length;
           //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
           //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的	 		   新容量，
           if (newCapacity - minCapacity < 0)
               newCapacity = minCapacity;
          // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 			 和 MAX_ARRAY_SIZE，
          //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 			 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
           if (newCapacity - MAX_ARRAY_SIZE > 0)
               newCapacity = hugeCapacity(minCapacity);
           // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
       }

    int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍！（JDK1.6版本以后）

    “>>”（移位运算符）：>>1 右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity / 2。对于大数据的2进制运算，位移运算符比那些普通运算符的运算要快很多，因为程序仅仅移动一下而已，不去计算,这样提高了效率，节省了资源。

    我们再来通过例子探究一下grow() 方法 ：

    • 当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。数组容量为10，add方法中 return true，size增为1。
    • 当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true，size增为11。
    • 以此类推······

    这里补充一点比较重要，但是容易被忽视掉的知识点：

    • java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
    • java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
    • java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

  5. hugeCapacity()方法

    从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private static int hugeCapacity(int minCapacity) {
           if (minCapacity < 0) // overflow
               throw new OutOfMemoryError();
           //对minCapacity和MAX_ARRAY_SIZE进行比较
           //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
           //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
           //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
           return (minCapacity > MAX_ARRAY_SIZE) ?
               Integer.MAX_VALUE :
               MAX_ARRAY_SIZE;
       }

  6. ensureCapacity()方法

    ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /**
        如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
         *
         * @param   minCapacity   所需的最小容量
         */
        public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;

            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }

    总结：最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数

遍历

ArrayList 实现了 RandomAccess 接口（该接口是个标志性接口），表明它具有随机访问的能力。ArrayList 底层基于数组实现，所以它可在常数阶的时间内完成随机访问，效率很高。对 ArrayList 进行遍历时，一般情况下，我们喜欢使用 for each 循环遍历，但这并不是推荐的遍历方式。ArrayList 具有随机访问的能力，如果在一些效率要求比较高的场景下，更推荐下面这种方式：

1
2
3
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

至于原因也不难理解，for each 最终会被转换成迭代器遍历的形式，效率不如上面的遍历方式。

关于遍历时的删除

遍历时删除是一个不正确的操作，即使有时候代码不出现异常，但执行逻辑也会出现问题。关于这个问题，阿里巴巴 Java 开发手册里也有所提及。这里引用一下：

【强制】不要在 for each 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

相关代码（稍作修改）如下：

1
2
3
4
5
6
7
8
9
10
	List<String> a = new ArrayList<String>();
	a.add("1");
	a.add("2");
	for (String temp : a) {
	    System.out.println(temp);
	    if("1".equals(temp)){
	        a.remove(temp);
	    }
	}
}

相信有些朋友应该看过这个，并且也执行过上面的程序。上面的程序执行起来不会虽不会出现异常，但代码执行逻辑上却有问题，只不过这个问题隐藏的比较深。

我们把 temp 变量打印出来，会发现只打印了数字1，2没打印出来。初看这个执行结果确实很让人诧异，不明原因。如果死抠上面的代码，我们很难找出原因，此时需要稍微转换一下思路。

我们都知道 Java 中的 for each 是个语法糖，编译成字节码后会被转成用迭代器遍历的方式。所以我们可以把上面的代码转换一下，等价于下面形式：

1
2
3
4
5
6
7
8
9
10
11
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
   	String temp = it.next();
   	System.out.println("temp: " + temp);
   	if("1".equals(temp)){
       	a.remove(temp);
   	}
}

这个时候，我们再去分析一下 ArrayList 的迭代器源码就能找出原因，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
	private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 并发修改检测，检测不通过则抛出异常
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    
    // 省略不相关的代码
}

我们一步一步执行一下上面的代码，第一次进入 while 循环时，一切正常，元素 1 也被删除了。但删除元素 1 后，就无法再进入 while 循环，此时 it.hasNext() 为 false。原因是删除元素 1 后，元素计数器 size = 1，而迭代器中的 cursor 也等于 1，从而导致 it.hasNext() 返回false。归根结底，上面的代码段没抛异常的原因是，循环提前结束，导致 next 方法没有机会抛异常。不信的话，大家可以把代码稍微修改一下，即可发现问题：

1
2
3
4
5
6
7
8
9
10
11
12
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
   	String temp = it.next();
   	System.out.println("temp: " + temp);
   	if("1".equals(temp)){
       	a.remove(temp);
   	}
}

以上是关于遍历时删除的分析，在日常开发中，我们要避免上面的做法。正确的做法使用迭代器提供的删除方法，而不是直接删除。

System.arraycopy()和Arrays.copyOf()方法

System.arraycopy() 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
    * 在此列表中的指定位置插入指定的元素。 
    *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证		  capacity足够大；
    *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
    */
   public void add(int index, E element) {
       rangeCheckForAdd(index);

       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //arraycopy()方法实现数组自己复制自己
       //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组		   中的起始位置； size - index：要复制的数组元素的数量；
       System.arraycopy(elementData, index, elementData, index + 1, size - index);
       elementData[index] = element;
       size++;
   }

Arrays.copyOf()方法：

1
2
3
4
5
6
7
8
9
/**
    *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 
    *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
    *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
    */
   public Object[] toArray() {
   //elementData：要复制的数组；size：要复制的长度
       return Arrays.copyOf(elementData, size);
   }

两者的联系与区别

联系：看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法

区别：

  1. arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置。
  2. copyOf()是系统自动在内部新建一个数组，并返回该数组。

参考：

https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/ArrayList.md#systemarraycopy%E5%92%8Carrayscopyof%E6%96%B9%E6%B3%95

http://www.tianxiaobo.com/2018/01/31/LinkedList-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-JDK-1-8/#4%E6%80%BB%E7%BB%93

发表于 | 分类于 ， |

interrupt()

interrupt方法用于中断线程。调用该方法的线程的状态为将被置为”中断”状态。

注意：线程中断仅仅是设置线程的中断状态位，不会停止线程。

支持线程中断的方法（也就是线程中断后会抛出interruptedException的方法）就是在监视线程的中断状态，一旦线程的中断状态被置为“中断状态”，就会抛出中断异常。

当处于阻塞状态的线程调用interrupt()时，会抛出InterruptedException，此时线程会退出阻塞，并会清除中断标记。也就是我们调用sleep、wait等此类可中断（throw InterruptedException）方法时，一旦方法抛出InterruptedException，当前调用该方法的线程的中断状态就会被jvm自动清除了，就是说我们调用该线程的isInterrupted 方法时是返回false。

如果你想保持中断状态，可以再次调用interrupt方法设置中断状态。这样做的原因是，java的中断并不是真正的中断线程，而只设置标志位（中断位）来通知用户。如果你捕获到中断异常，说明当前线程已经被中断，不需要继续保持中断位。

下面给出例子来看看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Interrupt {
	public static void main(String[] args) throws Exception {
		Thread t = new Thread(new Worker());
		t.start();
		
		Thread.sleep(200);
		t.interrupt();
		
		System.out.println("Main thread stopped.");
	}
	
	public static class Worker implements Runnable {
		public void run() {
			System.out.println("Worker started.");
			
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				System.out.println("Worker IsInterrupted: " + 
						Thread.currentThread().isInterrupted());
			}
			
			System.out.println("Worker stopped.");
		}
	}
}

内容很简答：主线程main启动了一个子线程Worker，然后让worker睡500ms，而main睡200ms，之后main调用worker线程的interrupt方法去中断worker，worker被中断后打印中断的状态。

下面是执行结果：

1
2
3
4
Worker started.
Main thread stopped.
Worker IsInterrupted: false
Worker stopped.

打印的结果充分地印证了当可中断的方法抛出异常时，线程中断的标记也会跟着被jvm所清除，因此调用isInterrupted()方法返回的是false。

interrupted()和isInterrupted()

我们先看看这两个方法的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	public static boolean interrupted() {
        return currentThread().isInterrupted(true);
    }

    public boolean isInterrupted() {
        return isInterrupted(false);
    }
    
     /**
2      * Tests if some Thread has been interrupted.  The interrupted state
3      * is reset or not based on the value of ClearInterrupted that is
4      * passed.
5      */
6   private native boolean isInterrupted(boolean ClearInterrupted);

原来这是一个本地方法，看不到源码。不过没关系，通过参数名我们就能知道，这个参数代表是否要清除状态位。

如果这个参数为true，说明返回线程的状态位后，要清掉原来的状态位（恢复成原来情况）。这个参数为false，就是直接返回线程的状态位。

这两个方法有两个主要区别：

  1. interrupted()是作用于当前线程，静态方法，isInterrupted()是作用于调用该方法的线程对象所对应的线程；(线程对象对应的线程不一定是当前运行的线程。例如我们可以在A线程中去调用B线程对象的isInterrupted()方法)
  2. 这两个方法最终都会调用同一个方法，只不过参数一个是true，一个是false；
  3. 这两个方法很好区分，只有当前线程才能清除自己的中断位。(对应interrupted()方法)

interrupted()是静态方法，返回的是当前线程的中断状态。例如，如果当前线程被中断（没有抛出中断异常，否则中断状态就会被清除），你调用interrupted()方法，第一次会返回true。然后，当前线程的中断状态被方法内部清除了。第二次调用时就会返回false。如果你刚开始一直调用isInterrupted()，则会一直返回true，除非中间线程的中断状态被其他操作清除了。

下面我们看看例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Interrupt  {
	public static void main(String[] args) throws Exception {
		Thread t = new Thread(new Worker());
		t.start();
		
		Thread.sleep(200);
		t.interrupt();
		
		System.out.println("Main thread stopped.");
	}
	
	public static class Worker implements Runnable {
		public void run() {
			System.out.println("Worker started.");
			
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				Thread curr = Thread.currentThread();
				//再次调用interrupt方法中断自己，将中断状态设置为“中断”
				curr.interrupt();
				System.out.println("Worker IsInterrupted: " + curr.isInterrupted());
				System.out.println("Worker IsInterrupted: " + curr.isInterrupted());
				System.out.println("Static Call: " + Thread.interrupted());//clear status
				System.out.println("---------After Interrupt Status Cleared----------");
				System.out.println("Static Call: " + Thread.interrupted());
				System.out.println("Worker IsInterrupted: " + curr.isInterrupted());
				System.out.println("Worker IsInterrupted: " + curr.isInterrupted());
			}
			
			System.out.println("Worker stopped.");
		}
	}
}

执行结果：

1
2
3
4
5
6
7
8
9
10
Worker started.
Main thread stopped.
Worker IsInterrupted: true
Worker IsInterrupted: true
Static Call: true
---------After Interrupt Status Cleared----------
Static Call: false
Worker IsInterrupted: false
Worker IsInterrupted: false
Worker stopped.

从执行结果也可以看到，前两次调用isInterrupted方法都返回true，说明isInterrupted方法不会改变线程的中断状态，而接下来调用静态的interrupted()方法，第一次返回了true，表示线程被中断，第二次则返回了false，因为第一次调用的时候已经清除了中断状态。最后两次调用isInterrupted()方法就肯定返回false了。

参考：

https://www.cnblogs.com/zhuhongchang/p/8467803.html

https://my.oschina.net/itblog/blog/787024

发表于 | 分类于 ， |

概述

Spring框架的核心就是IOC,通过controller一类注解的bean的实例化过程可以大体总结spring注解的工作原理：

1）利用asm技术扫描class文件，转化成Springbean结构，把符合扫描规则的（主要是是否有相关的注解标注，例如@Component）bean注册到Spring 容器中beanFactory。

2）注册处理器，包括注解处理器

3）实例化处理器（包括注解处理器），并将其注册到容器的beanPostProcessors列表中。

4）创建bean的过程中，属性注入或者初始化bean时会调用对应的注解处理器进行处理。

例如注解@Autowired：

对于这个注解，您需要在xml中配置这个注解的处理器AutowiredAnnotationBeanPostProcessor，这个处理器会扫描容器中所有的bean对象，发现bean中拥有@Autowired注解的时候会自动去找到容器中和这个注解修饰类型匹配的bean对象，并注入到对应的地方去。

元注解

  • @Target：表示该注释可以用于什么地方，下面是源码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    @Documented
    @Retention(RetentionPolicy.RUNTIME)   // 保留到运行时
    @Target(ElementType.ANNOTATION_TYPE)
    public @interface Target {
        /**
         * Returns an array of the kinds of elements an annotation type
         * can be applied to.
         * @return an array of the kinds of elements an annotation type
         * can be applied to.
         */
        ElementType[] value();
    }

    注解作用位置：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public enum ElementType {
        TYPE,                             // 类，接口（包括注解），enum;
        FIELD,                            // 属性域
        METHOD,                           // 方法
        PARAMETER,                        // 参数
        CONSTRUCTOR,                      // 构造函数
        LOCAL_VARIABLE,                   // 局部变量
        ANNOTATION_TYPE,                  // 注解类型
        PACKAGE,                          // 包

        /**
         * Type parameter declaration
         * @since 1.8
         */
        TYPE_PARAMETER,                   // 表明可以标注 类型参数

        /**
         * Use of a type
         * @since 1.8
         */
        TYPE_USE                          // 可以注解 任何类型名称
    }

  • @Retention 表示需要在什么级别保存该注释信息，下面是源码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /* Indicates how long annotations with the annotated type are to
     * be retained.  If no Retention annotation is present on
     * an annotation type declaration, the retention policy defaults to
     * {@code RetentionPolicy.CLASS}.
     *
     * A Retention meta-annotation has effect only if the
     * meta-annotated type is used directly for annotation.  It has no
     * effect if the meta-annotated type is used as a member type in
     * another annotation type.
    */
    @Documented     // 表明 注解会被包含在Java API文档中。
    @Retention(RetentionPolicy.RUNTIME)
    @Target(ElementType.ANNOTATION_TYPE)
    public @interface Retention {
        /**
         * Returns the retention policy.
         * @return the retention policy
         */
        RetentionPolicy value();
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public enum RetentionPolicy {
        /**
         * Annotations are to be discarded by the compiler.
         */
        SOURCE,

        /**
         * Annotations are to be recorded in the class file by the compiler
         * but need not be retained by the VM at run time.  This is the default
         * behavior.
         */
        CLASS,

        /**
         * Annotations are to be recorded in the class file by the compiler and
         * retained by the VM at run time, so they may be read reflectively.
         *
         * @see java.lang.reflect.AnnotatedElement
         */
        RUNTIME
    }

    RetentionPolicy.SOURCE 保留在源码级别，被编译器抛弃，如@Override；
    RetentionPolicy.CLASS 被编译器保留在编译后的class文件，但是被VM抛弃；
    RetentionPolicy.RUNTIME 保留至运行时，可以被反射读取。如 @Retention 元注解本身。

  • @Documented 将注释包含在JavaDoc中

  • @Inheried 允许子类继承父类中的注解

Java如何识别注解

关键词：Java反射

java.lang.reflect 包，实现反射功能的工具类

注解处理类库：java.lang.reflect.AnnotatedElement

zhujie2

zhujie3

程序通过反射获取了某个类的AnnotatedElement对象之后, 程序就可以调用该对象如下的方法来访问Annotation的信息：

  • Annotation[] getAnnotations()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
         * Returns annotations that are <em>present</em> on this element.
         *
         * If there are no annotations <em>present</em> on this element, the return
         * value is an array of length 0.
         *
         * The caller of this method is free to modify the returned array; it will
         * have no effect on the arrays returned to other callers.
         *
         * @return annotations present on this element
         * @since 1.5
         */
        Annotation[] getAnnotations();

  • default boolean isAnnotationPresent(Class<? extends Annotation> annotationClass)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /**
         * Returns true if an annotation for the specified type
         * is <em>present</em> on this element, else false.  This method
         * is designed primarily for convenient access to marker annotations.
         *
         * <p>The truth value returned by this method is equivalent to:
         * {@code getAnnotation(annotationClass) != null}
         *
         * <p>The body of the default method is specified to be the code
         * above.
         *
         * @param annotationClass the Class object corresponding to the
         *        annotation type
         * @return true if an annotation for the specified annotation
         *     type is present on this element, else false
         * @throws NullPointerException if the given annotation class is null
         * @since 1.5
         */
        default boolean isAnnotationPresent(Class<? extends Annotation> annotationClass) {
            return getAnnotation(annotationClass) != null;
        }

  • default T getDeclaredAnnotation(Class annotationClass)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    /**
         * Returns this element's annotation for the specified type if
         * such an annotation is <em>directly present</em>, else null.
         *
         * This method ignores inherited annotations. (Returns null if no
         * annotations are directly present on this element.)
         *
         * @implSpec The default implementation first performs a null check
         * and then loops over the results of {@link
         * #getDeclaredAnnotations} returning the first annotation whose
         * annotation type matches the argument type.
         *
         * @param <T> the type of the annotation to query for and return if directly present
         * @param annotationClass the Class object corresponding to the
         *        annotation type
         * @return this element's annotation for the specified annotation type if
         *     directly present on this element, else null
         * @throws NullPointerException if the given annotation class is null
         * @since 1.8
         */
        default <T extends Annotation> T getDeclaredAnnotation(Class<T> annotationClass) {
             Objects.requireNonNull(annotationClass);
             // Loop over all directly-present annotations looking for a matching one
             for (Annotation annotation : getDeclaredAnnotations()) {
                 if (annotationClass.equals(annotation.annotationType())) {
                     // More robust to do a dynamic cast at runtime instead
                     // of compile-time only.
                     return annotationClass.cast(annotation);
                 }
             }
             return null;
         }

为了处理注解，注解处理器做3件事情：

  • 读取配置文件中管理的bean
  • 实例化bean
  • 注解处理器获取实例bean中的注解并操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 自定义的注解处理器
public class ClassPathXMLApplicationContext {
    
    public ClassPathXMLApplicationContext(String configFileName) {
        // 读取配置文件中管理的bean
        readXMLConfigFile(configFileName);
        // 实例化bean
        instanceBean();
        // 向容器注册bean
        registerAnnotationBean();
    }

    // 读取配置文件中的bean
    private void readXMLConfigFile() {

    }

    // 实例化bean
    private void instanceBean() {

    }

    // 向容器注册bean
    private void registerAnnotationBean() {

    }
}

Spring是如何实现注解的扫描注册的

管理注解bean定义的两个容器：

  • AnnotationConfigApplicationContext
  • AnnotationConfigWebApplicationContext

AnnotationConfigApplicationContext的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package org.springframework.context.annotation;

public class AnnotationConfigApplicationContext extends GenericApplicationContext implements AnnotationConfigRegistry {
    // 读取器：读取注解的Bean，并注册到容器中。
    private final AnnotatedBeanDefinitionReader reader;
    // 扫描器：扫描类路径中注解的Bean，并注册到容器中。
    private final ClassPathBeanDefinitionScanner scanner;

    public AnnotationConfigApplicationContext() {
        // reader和scanner，功能类似，使用场景不同：annotatedClasses, basePakages.
        this.reader = new AnnotatedBeanDefinitionReader(this);
        this.scanner = new ClassPathBeanDefinitionScanner(this);
    }

    public AnnotationConfigApplicationContext(DefaultListableBeanFactory beanFactory) {
        super(beanFactory);
        this.reader = new AnnotatedBeanDefinitionReader(this);
        this.scanner = new ClassPathBeanDefinitionScanner(this);
    }

/*********************************
 *  1 区
 ***/
    public AnnotationConfigApplicationContext(Class<?>... annotatedClasses) {
        this();
        register(annotatedClasses);
        refresh();
    }

    public AnnotationConfigApplicationContext(String... basePackages) {
        this();
        scan(basePackages);
        refresh();
    }
/*********************************/
    @Override
    public void setEnvironment(ConfigurableEnvironment environment) {
        super.setEnvironment(environment);
        this.reader.setEnvironment(environment);
        this.scanner.setEnvironment(environment);
    }

    public void setBeanNameGenerator(BeanNameGenerator beanNameGenerator) {
        this.reader.setBeanNameGenerator(beanNameGenerator);
        this.scanner.setBeanNameGenerator(beanNameGenerator);
        getBeanFactory().registerSingleton(
                AnnotationConfigUtils.CONFIGURATION_BEAN_NAME_GENERATOR, beanNameGenerator);
    }

    public void setScopeMetadataResolver(ScopeMetadataResolver scopeMetadataResolver) {
        this.reader.setScopeMetadataResolver(scopeMetadataResolver);
        this.scanner.setScopeMetadataResolver(scopeMetadataResolver);
    }

/***************************
 *  2 区
 ***/
    public void register(Class<?>... annotatedClasses) {
        Assert.notEmpty(annotatedClasses, "At least one annotated class must be specified");
        this.reader.register(annotatedClasses);
    }

    public void scan(String... basePackages) {
        Assert.notEmpty(basePackages, "At least one base package must be specified");
        this.scanner.scan(basePackages);
    }
/***************************/
    @Override
    protected void prepareRefresh() {
        this.scanner.clearCache();
        super.prepareRefresh();
    }
}

AnnotationCnofigApplicationContext类的源码中的 “1 区”：

AnnotationConfigApplicationContext的基本功能在构造函数中完成

实例化reader和scanner，然后调用 register(Class<?>… annotatedClasses)或scan(String… basePackages)方法，最后刷新。

register(Class<?>… annotatedClasses)方法调用reader.register(Class<?>… annotatedClasses)

scan(String… basePackages)方法调用scanner.scan(String… basePackages)

AnnotatedBeanDefinitionReader 和 ClassPathBeanDefinitionScanner 功能类似，二者取其一。

AnnotationConfigApplicationContext 类的源码中的 “2 区”：

如下两个方法完成了Spring的扫描注册功能：

reader.register(Class<?>… annotatedClasses)

scanner.scan(String… basePackages)

  • reader.register(Class<?>… annotatedClasses) 的源码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    public void register(Class<?>... annotatedClasses) {
            for (Class<?> annotatedClass : annotatedClasses) {
                registerBean(annotatedClass);
            }
        }

    public void registerBean(Class<?> annotatedClass) {
            registerBean(annotatedClass, null, (Class<? extends Annotation>[]) null);
        }


    // 注解功能实现区
    @SuppressWarnings("unchecked")
    public void registerBean(Class<?> annotatedClass, String name, Class<? extends Annotation>... qualifiers) {
        AnnotatedGenericBeanDefinition abd = new AnnotatedGenericBeanDefinition(annotatedClass);
        if (this.conditionEvaluator.shouldSkip(abd.getMetadata())) {
            return;
        }

        ScopeMetadata scopeMetadata = this.scopeMetadataResolver.resolveScopeMetadata(abd);
        abd.setScope(scopeMetadata.getScopeName());
        String beanName = (name != null ? name : this.beanNameGenerator.generateBeanName(abd, this.registry));
            
        AnnotationConfigUtils.processCommonDefinitionAnnotations(abd);
        if (qualifiers != null) {
            for (Class<? extends Annotation> qualifier : qualifiers) {
                if (Primary.class == qualifier) {
                    abd.setPrimary(true);
                } else if (Lazy.class == qualifier) {
                    abd.setLazyInit(true);
                } else {
                    abd.addQualifier(new AutowireCandidateQualifier(qualifier));
                }
            }
        }

        BeanDefinitionHolder definitionHolder = new BeanDefinitionHolder(abd, beanName);
        definitionHolder = AnnotationConfigUtils.applyScopedProxyMode(scopeMetadata, definitionHolder, this.registry);
        BeanDefinitionReaderUtils.registerBeanDefinition(definitionHolder, this.registry);
    }

  • scanner.scan(String… basePackages) 源码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    public int scan(String... basePackages) {
            int beanCountAtScanStart = this.registry.getBeanDefinitionCount();

            doScan(basePackages);    // 备注：重点关注此处

            // Register annotation config processors, if necessary.
            if (this.includeAnnotationConfig) {
                AnnotationConfigUtils.registerAnnotationConfigProcessors(this.registry);
            }

            return (this.registry.getBeanDefinitionCount() - beanCountAtScanStart);
        }


    // 注解功能实现区
    protected Set<BeanDefinitionHolder> doScan(String... basePackages) {
        Assert.notEmpty(basePackages, "At least one base package must be specified");
        /**
         * BeanDefinitionHoder: Holder for a BeanDefinition with name and aliases.
         * BeanDefinition: A BeanDefinition describes a bean instance,   
         *   which has property values, constructor argument values, and 
         *   further information supplied by concrete implementations.
         */
        Set<BeanDefinitionHolder> beanDefinitions = new LinkedHashSet<BeanDefinitionHolder>();
        for (String basePackage : basePackages) {  // 多个包路径
            Set<BeanDefinition> candidates = findCandidateComponents(basePackage);
            for (BeanDefinition candidate : candidates) {
                ScopeMetadata scopeMetadata = this.scopeMetadataResolver.resolveScopeMetadata(candidate);
                candidate.setScope(scopeMetadata.getScopeName());
                String beanName = this.beanNameGenerator.generateBeanName(candidate, this.registry);
                if (candidate instanceof AbstractBeanDefinition) {
                    postProcessBeanDefinition((AbstractBeanDefinition) candidate, beanName);
                }
                if (candidate instanceof AnnotatedBeanDefinition) {
                    AnnotationConfigUtils.processCommonDefinitionAnnotations((AnnotatedBeanDefinition) candidate);
                }
                if (checkCandidate(beanName, candidate)) {
                    BeanDefinitionHolder definitionHolder = new BeanDefinitionHolder(candidate, beanName);
                    definitionHolder = AnnotationConfigUtils.applyScopedProxyMode(scopeMetadata, definitionHolder, this.registry);
                    beanDefinitions.add(definitionHolder);
                    registerBeanDefinition(definitionHolder, this.registry);
                }
            }
        }
        return beanDefinitions;
    }

总结

zhujie1

发表于 | 分类于 ， |

Spring声明式事务异常回滚机制

前言

Spring事务管理是根据异常来进行回滚操作；

Spring与Mybatis整合时，虽然在Service方法中并没有checked异常，但是如果数据库有异常发生，默认会进行事务回滚。

Spring如果不添加rollbackFor等属性，Spring碰到Unchecked Exceptions都会回滚，不仅仅是RuntimeException，也包括Error。

如果在事务方法中捕获异常并进行处理，一定要继续抛出异常并在Spring事务管理中进行rollbak-for配置。

概述

首先看一个Service层的方法，该方法调用两个DAO层的方法分别往数据库中的两张表中插入数据，实现一个业务逻辑。而且根据业务规则，这两个插入动作是要进行事务控制的原子操作，即要么一起成功，要么一起失败，否则会导致数据一致性问题。

1
2
3
4
5
6
@Override
public void SaveDispatchInfoService(GxluProjectInfo projInfo, GxluDispatchResultSchedule dispatchResultSchedule) throws Exception
{
     projectInfoDAO.updateOrderInfoByOrderId(projInfo); //此句执行完后，事务已经被提交了
     gxluDispatchResultScheduleDAO.saveInstance(dispatchResultSchedule);//若此句执行发生异常，已无法将上一句执行的结果进行回滚，产生数据一致性问题
}

说明：若在这个Service层的方法上不加任何事务注解，则事务的边界为DAO层的方法。即当程序执行完第一个DAO方法的调用后，事务已经被提交了。（可以通过pl/sql developer工具连接到数据库后，发现此时记录已经被插入到表中了来验证）。因此，第二句的DAO层的方法如果一旦执行错误，已经无法将上一句DAO层方法以及插入到数据库中的数据进行回滚，导致数据一致性问题。

Spring通过@Transactional注解实现声明式事务。一般事务的边界定义在Service层的方法中。

1
2
3
4
5
6
7
@Override
@Transactional
public void SaveDispatchInfoService(GxluProjectInfo projInfo, GxluDispatchResultSchedule dispatchResultSchedule) throws Exception
{
     projectInfoDAO.updateOrderInfoByOrderId(projInfo);//此句执行完后，事务没有被提交。
     gxluDispatchResultScheduleDAO.saveInstance(dispatchResultSchedule);//此句若执行失败，若抛出的异常为RuntimeExcepition类型或其子型的异常对象，则上句DAO层语句执行的结果会被回滚。否则，上句执行的结果会被提交。这样也会导致业务原子信被破坏，导致数据不一致的情况。
}//当程序执完整个Service方法，且上述两句都执行成功，则事务才被提交

说明：若如上述代码一样，只加了一个默认的@Transactional标注，而不加任何标注参数。则此时，当第一个DAO层方法执行完成后，事务没有被提交（可以通过pl/sql developer工具连接到数据库后，发现此时记录没有被插入到表中来验证）。当程序执完整个Service方法，且上述两句DAO层方法都执行成功，则事务才被提交（可以通过pl/sql developer工具连接到数据库后，发现此时两条记录都已经被插入到表中来验证）。

若第二句DAO层方法执行失败，Spring会根据异常类型来做不同的处理，即：若执行失败，若抛出的异常为RuntimeExcepition类型或其子型的异常对象，则上句DAO层语句执行的结果会被回滚。否则，上句执行的结果会被提交。这样也会导致业务原子性被破坏，导致数据不一致的情况。

为了保证在Service层的方法中，无论遇到任何类型的异常，都让事务进行回滚，而不是让之前已经执行成功的语句提交，则必须在@Transactional注解中增加如下参数rollbackFor：

1
2
3
4
5
6
7
@Override
@Transactional(propagation=Propagation.REQUIRED, rollbackFor=Exception.class)
public void SaveDispatchInfoService(GxluProjectInfo projInfo, GxluDispatchResultSchedule dispatchResultSchedule) throws Exception
{
     projectInfoDAO.updateOrderInfoByOrderId(projInfo);
     gxluDispatchResultScheduleDAO.saveInstance(dispatchResultSchedule);
}

说明：由于Exception是所有异常类的超类，这样对于任何异常，Spring都会进行回滚，而不会将引发异常之前已经执行成功的提交掉。

对于那些我们在代码中主动抛出的异常，我们可以将rollbackFor参数指定为这些特定异常，即遇到该异常，就进行回滚操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Override
@Transactional(propagation=Propagation.REQUIRED, rollbackFor=ArcpipeException.class)
public void insertRouteConditions(List<GxluProjectInfo> projInfos) throws ArcpipeException,JAXBException,RemoteException,Exception
{
   //插入路由选择条件（起始、终止）到数据库
   for (GxluProjectInfo projInfo : projInfos)
   {
      projectInfoDAO.insertRouteCondition(projInfo);
   }

   //将选择条件推送给综资Webservice
   Body bodyOut=convertBean2dto(projInfos);
   String configConditionXml = JaxbUtil.convertToXml(bodyOut);
   String configConditionResultXml=configConditionItfService.submitConfigCondition2Purdo(configConditionXml);
   Body bodyIn = JaxbUtil.converyToJavaBean(configConditionResultXml, Body.class);
   if(!"1".equals(bodyIn.getConfigConditionResultInfo().getErrorCode()))
   {
       throw new ArcpipeException(); //若抛出该异常，则整个事务将被回滚
   }
}

说明：上述Service方法作为一个原子业务逻辑，实现了两个操作，一个是调用DAO层方法往数据库里面插入数据，另一个是调用另一个系统的Webservice接口，将数据推送过去。若第一个DAO层方法执行成功，而第二个操作由于网络等原因导致调用Webservice接口失败，则程序会主动抛出ArcpipeException异常，而由于事务注解中已经设置了参数rollbackFor=ArcpipeException.class，因此该事务会被回滚掉。

或者我们在自定义异常的时候，让自定义的异常继承自RuntimeException，这样抛出的时候才会被Spring默认的事务处理。

发表于 | 分类于 ， |

前言

用两个表（a_table、b_table），关联字段a_table.a_id和b_table.b_id来演示一下MySQL的内连接、外连接（ 左(外)连接、右(外)连接、全(外)连接）。

MySQL版本：Server version: 5.6.31 MySQL Community Server (GPL)

数据库表：a_table、b_table

主题：内连接、左连接（左外连接）、右连接（右外连接）、全连接（全外连接）、交叉连接

前提

建表语句：

1
2
3
4
5
CREATE TABLE `a_table` (
  `a_id` int(11) DEFAULT NULL,
  `a_name` varchar(10) DEFAULT NULL,
  `a_part` varchar(10) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1
2
3
4
5
CREATE TABLE `b_table` (
  `b_id` int(11) DEFAULT NULL,
  `b_name` varchar(10) DEFAULT NULL,
  `b_part` varchar(10) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8

表测试数据：

mysql1

内连接(等值连接)

关键字：inner join on

语句：

1
select * from a_table a inner join b_table b on a.a_id = b.b_id

执行结果：

mysql2

说明：组合两个表中的记录，返回关联字段相符的记录，也就是返回两个表的交集（阴影）部分。

mysql3

左连接

关键字：left join on / left outer join on

语句：

1
select * from a_table a left join b_table b on a.a_id = b.b_id

执行结果：

mysql4

说明：

left join 是left outer join的简写，它的全称是左外连接，是外连接中的一种。

左(外)连接，左表(a_table)的记录将会全部表示出来，而右表(b_table)只会显示符合搜索条件的记录，并且右表记录不足的地方均为NULL。

mysql5

右连接

关键字：right join on / right outer join on

语句：

1
select * from a_table a right outer join b_table b on a.a_id = b.b_id

执行结果：

mysql6

说明：

right join是right outer join的简写，它的全称是右外连接，是外连接中的一种。

与左(外)连接相反，右(外)连接，左表(a_table)只会显示符合搜索条件的记录，而右表(b_table)的记录将会全部表示出来，并且左表记录不足的地方均为NULL。

mysql7

全连接

MySql不支持全连接查询，可以用union代替.

为做全连接演示，所以在Oracle新建两张：

表message1：

mysql9

表message2：

mysql10

关键字：FULL JOIN

语句：

1
2
3
select * from message1 a
FULL JOIN message2 b
on a.id=b.id

查询结果如图所示：

mysql11

全连接的图片效果：

mysql8

总结：Full outer join展示的是a表和b表的全部信息(a和b的并集)。但需要注意的是，对于没有匹配的记录(即a.id和b.id没有一一对应的)，则会以null做为值。可以使用IF NULL判断。

交叉连接(笛卡尔积)

  1. 不带where条件子句，它返回的是被连接的两个表的笛卡尔积，返回结果的行数等于两个表行数的乘积。

    例如上表中：message1表的3条数据*message2表的4条数据，最后得到12条数据，就是下面笛卡尔积查询出来的总记录数。

    查询语句：

    1
    2
    select * from message1 a
    cross JOIN message2 b

    查询结果如图所示：

    mysql12

  2. 如果带where，返回或显示的是匹配条件成立的行数。

    查询语句：

    1
    2
    3
    4
    select * from message1 a
    cross JOIN message2 b
    where
    a.id=b.id

    查询结果如图所示：

    mysql13

    总结：
    1.CROSS JOIN(笛卡尔积)是两个表每一个字段相互匹配，得出的结果就是笛卡尔积。笛卡尔积也等同于交叉连接。

    2.CROSS JOIN(笛卡尔积)带条件查询， 查询结果跟等值连接(也叫内连接)、where连接的查询结果是一样，并且后面加条件只能用where，不能用on。

部分JOIN连接简单优化

部分指的是：inner join、left join和right join

优化方法：

a.找出驱动表和被驱动表，在被驱动表上建立索引，可提高连接性能。
b.内连接inner join和左连接left join差不多,都需要优化右表。而右连接right join需要优化左表。
比较：
左连接和内连接优于右连接，左连接和内连接的比较取决于需求，单纯看性能是差不多的。

备注：
索引一般为（主键、唯一索引、前缀索引等）
左连接left join中，左表为驱动表，右表为被驱动表；右连接right join中，右表为驱动表，左表为被驱动表。

参考：

https://blog.csdn.net/plg17/article/details/78758593

https://blog.csdn.net/qq_39629277/article/details/82882004