集合

这个分类中，将会写写Java中的集合。集合是Java中非常重要而且基础的内容，因为任何数据必不可少的就是该数据是如何存储的，集合的作用就是以一定的方式组织、存储数据。这里写的集合，一部分是比较常见的、一部分是不常用但是我个人平时见到过的，一些比较相似的集合（比如HashMap和Hashtable）就只讲一个，突出它们之间的区别即可。

最后，要指出一点，对于集合，我认为关注的点主要有四点：

• 是否允许空
• 是否允许重复数据
• 是否有序，有序的意思是读取数据的顺序和存放数据的顺序是否一致
• 是否线程安全

ArrayList

ArrayList是最常见以及每个Java开发者最熟悉的集合类了，顾名思义，ArrayList就是一个以数组形式实现的集合，以一张表格来看一下ArrayList里面有哪些基本的元素：

元 素	作 用
private transient Object[] elementData;	ArrayList是基于数组的一个实现，elementData就是底层的数组
private int size;	ArrayList里面元素的个数，这里要注意一下，size是按照调用add、remove方法的次数进行自增或者自减的，所以add了一个null进入ArrayList，size也会加1

四个关注点在ArrayList上的答案

关 注 点	结论
ArrayList是否允许空	允许
ArrayList是否允许重复数据	允许
ArrayList是否有序	有序
ArrayList是否线程安全	非线程安全

添加元素

有这么一段代码：

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("000");
    list.add("111");
}

看下底层会做什么，进入add方法的源码来看一下：

public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

先不去管第2行的ensureCapacity方法，这个方法是扩容用的，底层实际上在调用add方法的时候只是给elementData的某个位置添加了一个数据而已，用一张图表示的话是这样的：

多说一句，我这么画图有一定的误导性。elementData中存储的应该是堆内存中元素的引用，而不是实际的元素，这么画给人一种感觉就是说elementData数组里面存放的就是实际的元素，这是不太严谨的。不过这么画主要是为了方便起见，只要知道这个问题就好了。

扩容

我们看一下，构造ArrayList的时候，默认的底层数组大小是10：

public ArrayList() {
this(10);
}

那么有一个问题来了，底层数组的大小不够了怎么办？答案就是扩容，这也就是为什么一直说ArrayList的底层是基于动态数组实现的原因，动态数组的意思就是指底层的数组大小并不是固定的，而是根据添加的元素大小进行一个判断，不够的话就动态扩容，扩容的代码就在ensureCapacity里面：

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
           // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
}
}

看到扩容的时候把元素组大小先乘以3，再除以2，最后加1。可能有些人要问为什么？我们可以想：

• 如果一次性扩容扩得太大，必然造成内存空间的浪费
• 如果一次性扩容扩得不够，那么下一次扩容的操作必然比较快地会到来，这会降低程序运行效率，要知道扩容还是比较耗费性能的一个操作

所以扩容扩多少，是JDK开发人员在时间、空间上做的一个权衡，提供出来的一个比较合理的数值。最后调用到的是Arrays的copyOf方法，将元素组里面的内容复制到新的数组里面去：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
       T[] copy = ((Object)newType == (Object)Object[].class)
           ? (T[]) new Object[newLength]
           : (T[]) Array.newInstance(newType.getComponentType(), newLength);
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
}

用一张图来表示就是这样的：

删除元素

接着我们看一下删除的操作。ArrayList支持两种删除方式：

• 按照下标删除
• 按照元素删除，这会删除ArrayList中与指定要删除的元素匹配的第一个元素

int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
             numMoved);
elementData[--size] = null; // Let gc do its work

其实做的事情就是两件:

• 把指定元素后面位置的所有元素，利用System.arraycopy方法整体向前移动一个位置
• 最后一个位置的元素指定为null，这样让gc可以去回收它

比方说有这么一段代码：

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("111");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("555");
    list.add("666");
    list.add("777");
    list.add("888");
    list.remove("333");
}

用图表示是这样的：

插入元素

看一下ArrayList的插入操作，插入操作调用的也是add方法，比如：

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("111");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("555");
    list.add("666");
    list.add("777");
    list.add("888");
    list.add(2, "000");
    System.out.println(list);
}

有一个地方不要搞错了，第12行的add方法的意思是，往第几个元素后面插入一个元素，像第12行就是往第二个元素后面插入一个000。看一下运行结果也证明了这一点：

[111, 222, 000, 333, 444, 555, 666, 777, 888]

还是看一下插入的时候做了什么：

public void add(int index, E element) {
if (index > size || index < 0)
    throw new IndexOutOfBoundsException(
    "Index: "+index+", Size: "+size);
    ensureCapacity(size+1);  // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
         size - index);
elementData[index] = element;
size++;
}

看到插入的时候，按照指定位置，把从指定位置开始的所有元素利用System.arraycopy方法做一个整体的复制，向后移动一个位置（当然先要用ensureCapacity方法进行判断，加了一个元素之后数组会不会不够大），然后指定位置的元素设置为需要插入的元素，完成了一次插入的操作。用图表示这个过程是这样的：

ArrayList的优缺点

从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下：

• ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快
• ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已

不过ArrayList的缺点也十分明显：

• 删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
• 插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

因此，ArrayList比较适合顺序添加、随机访问的场景。

ArrayList和Vector的区别

ArrayList是线程非安全的，这很明显，因为ArrayList中所有的方法都不是同步的，在并发下一定会出现线程安全问题。那么我们想要使用ArrayList并且让它线程安全怎么办？一个方法是用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List，比如：

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
    System.out.println(synchronizedList.get(i));
}

另一个方法就是Vector，它是ArrayList的线程安全版本，其实现90%和ArrayList都完全一样，区别在于：

• Vector是线程安全的，ArrayList是线程非安全的
• Vector可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2，源代码是这样的：

int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                 capacityIncrement : oldCapacity);

为什么ArrayList的elementData是用transient修饰的？

最后一个问题，我们看一下ArrayList中的数组，是这么定义的：

private transient Object[] elementData;

不知道大家有没有想过，为什么elementData是使用transient修饰的呢？关于这个问题，说说我的看法。我们看一下ArrayList的定义：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

看到ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么？因为序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法：

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
        // Write out array length
       s.writeInt(elementData.length);
    // Write out all elements in the proper order.
for (int i=0; i<size; i++)
           s.writeObject(elementData[i]);
    if (modCount != expectedModCount) {
           throw new ConcurrentModificationException();
    }
}

每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素，这样：

• 加快了序列化的速度
• 减小了序列化之后的文件大小

不失为一种聪明的做法，如果以后开发过程中有遇到这种情况，也是值得学习、借鉴的一种思路。

LinkedList

LinkedList是基于链表实现的，所以先讲解一下什么是链表。链表原先是C/C++的概念，是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。

这么讲可能有点抽象，先提一句，LinkedList是一种双向链表，双向链表我认为有两点含义：

1、链表中任意一个存储单元都可以通过向前或者向后寻址的方式获取到其前一个存储单元和其后一个存储单元

2、链表的尾节点的后一个节点是链表的头结点，链表的头结点的前一个节点是链表的尾节点

LinkedList既然是一种双向链表，必然有一个存储单元，看一下LinkedList的基本存储单元，它是LinkedList中的一个内部类：

private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
...
}

看到LinkedList的Entry中的E element，就是它真正存储的数据。Entry<E> next和Entry<E> previous表示的就是这个存储单元的前一个存储单元的引用地址和后一个存储单元的引用地址。

四个关注点在LinkedList上的答案

关 注 点	结论
LinkedList是否允许空	允许
LinkedList是否允许重复数据	允许
LinkedList是否有序	有序
LinkedList是否线程安全	非线程安全

添加元素

首先看下LinkedList添加一个元素是怎么做的，假如我有一段代码：

public static void main(String[] args)
{
    List<String> list = new LinkedList<String>();
    list.add("111");
    list.add("222");
}

逐行分析main函数中的三行代码是如何执行的，首先是第3行，看一下LinkedList的源码：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
        header.next = header.previous = header;
    }
    ...
}

看到，new了一个Entry出来名为header，Entry里面的previous、element、next都为null，执行构造函数的时候，将previous和next的值都设置为header的引用地址，还是用画图的方式表示。32位JDK的字长为4个字节，而目前64位的JDK一般采用的也是4字长，所以就以4个字长为单位。header引用地址的字长就是4个字节，假设是0x00000000，那么执行完List<String> list = new LinkedList<String>()之后可以这么表示：

接着看第4行add一个字符串"111"做了什么：

public boolean add(E e) {
addBefore(e, header);
    return true;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

第2行new了一个Entry出来，可能不太好理解，根据Entry的构造函数，我把这句话"翻译"一下，可能就好理解了：

1、newEntry.element = e;

2、newEntry.next = header.next;

3、newEntry.previous = header.previous;

header.next和header.previous上图中已经看到了，都是0x00000000，那么假设new出来的这个Entry的地址是0x00000001，继续画图表示：

一共五步，每一步的操作步骤都用数字表示出来了：

1、新的entry的element赋值为111;

2、新的entry的next是header的next，header的next是0x00000000，所以新的entry的next即0x00000000;

3、新的entry的previous是header的previous，header的previous是0x00000000，所以新的entry的next即0x00000000;

4、"newEntry.previous.next = newEntry"，首先是newEntry的previous，由于newEntry的previous为0x00000000，所以newEntry.previous表示的是header，header的next为newEntry，即header的next为0x00000001;

5、"newEntry.next.previous = newEntry"，和4一样，把header的previous设置为0x00000001;

为什么要这么做？还记得双向链表的两个特点吗，一是任意节点都可以向前和向后寻址，二是整个链表头的previous表示的是链表的尾Entry，链表尾的next表示的是链表的头Entry。现在链表头就是0x00000000这个Entry，链表尾就是0x00000001，可以自己看图观察、思考一下是否符合这两个条件。

最后看一下add了一个字符串"222"做了什么，假设新new出来的Entry的地址是0x00000002，画图表示：

还是执行的那5步，图中每一步都标注出来了，只要想清楚previous、next各自表示的是哪个节点就不会出问题了。

至此，往一个LinkedList里面添加一个字符串"111"和一个字符串"222"就完成了。从这张图中应该理解双向链表比较容易：

1、中间的那个Entry，previous的值为0x00000000，即header；next的值为0x00000002，即tail，这就是任意一个Entry既可以向前查找Entry，也可以向后查找Entry

2、头Entry的previous的值为0x00000002，即tail，这就是双向链表中头Entry的previous指向的是尾Entry

3、尾Entry的next的值为0x00000000，即header，这就是双向链表中尾Entry的next指向的是头Entry

查看元素

看一下LinkedList的代码是怎么写的：

public E get(int index) {
    return entry(index).element;
}

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

这段代码就体现出了双向链表的好处了。双向链表增加了一点点的空间消耗（每个Entry里面还要维护它的前置Entry的引用），同时也增加了一定的编程复杂度，却大大提升了效率。

由于LinkedList是双向链表，所以LinkedList既可以向前查找，也可以向后查找，第6行~第12行的作用就是：当index小于数组大小的一半的时候（size >> 1表示size / 2，使用移位运算提升代码运行效率），向后查找；否则，向前查找。

这样，在我的数据结构里面有10000个元素，刚巧查找的又是第10000个元素的时候，就不需要从头遍历10000次了，向后遍历即可，一次就能找到我要的元素。

删除元素

看完了添加元素，我们看一下如何删除一个元素。和ArrayList一样，LinkedList支持按元素删除和按下标删除，前者会删除从头开始匹配的第一个元素。用按下标删除举个例子好了，比方说有这么一段代码：

public static void main(String[] args)
{
    List<String> list = new LinkedList<String>();
    list.add("111");
    list.add("222");
    list.remove(0);
}

也就是我想删除"111"这个元素。看一下第6行是如何执行的：

public E remove(int index) {
    return remove(entry(index));
}

private E remove(Entry<E> e) {
if (e == header)
    throw new NoSuchElementException();

        E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
       e.next = e.previous = null;
       e.element = null;
size--;
modCount++;
       return result;
}

当然，首先是找到元素在哪里，这和get是一样的。接着，用画图的方式来说明比较简单：

比较简单，只要找对引用地址就好了，每一步的操作也都详细标注在图上了。

这里我提一点，第3步、第4步、第5步将待删除的Entry的previous、element、next都设置为了null，这三步的作用是让虚拟机可以回收这个Entry。

但是，这个问题我稍微扩展深入一点：按照Java虚拟机HotSpot采用的垃圾回收检测算法----根节点搜索算法来说，即使previous、element、next不设置为null也是可以回收这个Entry的，因为此时这个Entry已经没有任何地方会指向它了，tail的previous与header的next都已经变掉了，所以这块Entry会被当做"垃圾"对待。之所以还要将previous、element、next设置为null，我认为可能是为了兼容另外一种垃圾回收检测算法----引用计数法，这种垃圾回收检测算法，只要对象之间存在相互引用，那么这块内存就不会被当作"垃圾"对待。

插入元素

插入元素就不细讲了，看一下删除元素的源代码：

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

如果朋友们理解了前面的内容，我认为这两个方法对你来说，应该是很容易看懂的。

LinkedList和ArrayList的对比

老生常谈的问题了，这里我尝试以自己的理解尽量说清楚这个问题，顺便在这里就把LinkedList的优缺点也给讲了。

1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList

2、基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存

3、数据遍历的速度，看最后一部分，这里就不细讲了，结论是：使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些

4、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：

（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址

（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。

从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作。

最后一点，一切都是纸上谈兵，在选择了List后，有条件的最好可以做一些性能测试，比如在你的代码上下文记录List操作的时间消耗。

对LinkedList以及ArrayList的迭代

ArrayList使用最普通的for循环遍历，LinkedList使用foreach循环比较快，看一下两个List的定义：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

注意到ArrayList是实现了RandomAccess接口而LinkedList则没有实现这个接口，关于RandomAccess这个接口的作用，可以看一下JDK API (opens new window)

为此，我写一段代码证明一下这一点，注意，虽然上面的例子用的Iterator，但是做foreach循环的时候，编译器默认会使用这个集合的Iterator。测试代码如下：

public class TestMain
{
    private static int SIZE = 111111;
    
    private static void loopList(List<Integer> list)
    {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++)
        {
            list.get(i);
        }
        System.out.println(list.getClass().getSimpleName() + "使用普通for循环遍历时间为" + 
                (System.currentTimeMillis() - startTime) + "ms");
        
        startTime = System.currentTimeMillis();
        for (Integer i : list)
        {
            
        }
        System.out.println(list.getClass().getSimpleName() + "使用foreach循环遍历时间为" + 
                (System.currentTimeMillis() - startTime) + "ms");
    }
    
    public static void main(String[] args)
    {
        List<Integer> arrayList = new ArrayList<Integer>(SIZE);
        List<Integer> linkedList = new LinkedList<Integer>();
        
        for (int i = 0; i < SIZE; i++)
        {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        loopList(arrayList);
        loopList(linkedList);
        System.out.println();
    }
}

我截取三次运行结果：

ArrayList使用普通for循环遍历时间为6ms
ArrayList使用foreach循环遍历时间为12ms
LinkedList使用普通for循环遍历时间为38482ms
LinkedList使用foreach循环遍历时间为11ms

ArrayList使用普通for循环遍历时间为5ms
ArrayList使用foreach循环遍历时间为12ms
LinkedList使用普通for循环遍历时间为43287ms
LinkedList使用foreach循环遍历时间为9ms

ArrayList使用普通for循环遍历时间为4ms
ArrayList使用foreach循环遍历时间为12ms
LinkedList使用普通for循环遍历时间为22370ms
LinkedList使用foreach循环遍历时间为5ms

有了JDK API的解释，这个结果并不让人感到意外，最最想要提出的一点是：如果使用普通for循环遍历LinkedList，在大数据量的情况下，其遍历速度将慢得令人发指。

CopyOnWriteArrayList

第一次见到CopyOnWriteArrayList，是在研究JDBC的时候，每一个数据库的Driver都是维护在一个CopyOnWriteArrayList中的，为了证明这一点，贴两段代码，第一段在com.mysql.jdbc.Driver下，也就是我们写Class.forName("...")中的内容：

public class Driver extends NonRegisteringDriver
  implements java.sql.Driver
{
  public Driver()
    throws SQLException
  {
  }

  static
  {
    try
    {
      DriverManager.registerDriver(new Driver());
    } catch (SQLException E) {
      throw new RuntimeException("Can't register driver!");
    }
  }
}

看到com.mysql.jdbc.Driver调用了DriverManager的registerDriver方法，这个类在java.sql.DriverManager下：

public class DriverManager
{
  private static final CopyOnWriteArrayList<DriverInfo> registeredDrivers = new CopyOnWriteArrayList();
  private static volatile int loginTimeout = 0;
  private static volatile PrintWriter logWriter = null;
  private static volatile PrintStream logStream = null;
  private static final Object logSync = new Object();
  static final SQLPermission SET_LOG_PERMISSION = new SQLPermission("setLog");
   ...
}

看到所有的DriverInfo都在CopyOnWriteArrayList中。既然看到了CopyOnWriteArrayList，我自然免不了要研究一番为什么JDK使用的是这个List。

首先提两点：

1、CopyOnWriteArrayList位于java.util.concurrent包下，可想而知，这个类是为并发而设计的

2、CopyOnWriteArrayList，顾名思义，Write的时候总是要Copy，也就是说对于CopyOnWriteArrayList，任何可变的操作（add、set、remove等等）都是伴随复制这个动作的，后面会解读CopyOnWriteArrayList的底层实现机制

四个关注点在CopyOnWriteArrayList上的答案

关 注 点	结论
LinkedList是否允许空	允许
LinkedList是否允许重复数据	允许
LinkedList是否有序	有序
LinkedList是否线程安全	线程安全

如何向CopyOnWriteArrayList中添加元素

对于CopyOnWriteArrayList来说，增加、删除、修改、插入的原理都是一样的，所以用增加元素来分析一下CopyOnWriteArrayList的底层实现机制就可以了。先看一段代码：

public static void main(String[] args)
{
    List<Integer> list = new CopyOnWriteArrayList<Integer>();
    list.add(1);
    list.add(2);
}

看一下这段代码做了什么，先是第3行的实例化一个新的CopyOnWriteArrayList：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /** The lock protecting all mutators */
    transient final ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;
    ...
}

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

final void setArray(Object[] a) {
    array = a;
}

看到，对于CopyOnWriteArrayList来说，底层就是一个Object[] array，然后实例化一个CopyOnWriteArrayList，就是这样，Object array指向一个数组大小为0的数组。接着看一下，第4行的add一个整数1做了什么，add的源代码是：

public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
    Object[] elements = getArray();
    int len = elements.length;
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    newElements[len] = e;
    setArray(newElements);
    return true;
} finally {
    lock.unlock();
}
}

画一张图表示一下：

每一步都清楚地表示在图上了，一次add大致经历了几个步骤：

1、加锁

2、拿到原数组，得到新数组的大小（原数组大小+1），实例化出一个新的数组来

3、把原数组的元素复制到新数组中去

4、新数组最后一个位置设置为待添加的元素（因为新数组的大小是按照原数组大小+1来的）

5、把Object array引用指向新数组

6、解锁

整个过程看起来比较像ArrayList的扩容。有了这个基础，我们再来看一下第5行的add了一个整数2做了什么，这应该非常简单了，还是画一张图来表示：

和前面差不多，就不解释了。

另外，插入、删除、修改操作也都是一样，每一次的操作都是以对Object[] array进行一次复制为基础的，如果上面的流程看懂了，那么研究插入、删除、修改的源代码应该不难。

普通List的缺陷

常用的List有ArrayList、LinkedList、Vector，其中前两个是线程非安全的，最后一个是线程安全的。我有一种场景，两个线程操作了同一个List，分别对同一个List进行迭代和删除，就如同下面的代码：

public static class T1 extends Thread
{
    private List<Integer> list;
    
    public T1(List<Integer> list)
    {
        this.list = list;
    }
    
    public void run()
    {
        for (Integer i : list)
        {
        }
    }
}
    
public static class T2 extends Thread
{
    private List<Integer> list;
    
    public T2(List<Integer> list)
    {
        this.list = list;
    }
    
    public void run()
    {
        for (int i = 0; i < list.size(); i++)
        {
            list.remove(i);
        }
    }
}

首先我在这两个线程中放入ArrayList并启动这两个线程：

public static void main(String[] args)
{
    List<Integer> list = new ArrayList<Integer>();
    
    for (int i = 0; i < 10000; i++)
    {
        list.add(i);
    }
    
    T1 t1 = new T1(list);
    T2 t2 = new T2(list);
    t1.start();
    t2.start();
}

运行结果为：

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
    at java.util.AbstractList$Itr.next(AbstractList.java:343)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

把ArrayList换成LinkedList，main函数的代码就不贴了，运行结果为：

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
    at java.util.LinkedList$ListItr.next(LinkedList.java:696)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

可能有人觉得，这两个线程都是线程非安全的类，所以不行。其实这个问题和线程安不安全没有关系，换成Vector看一下运行结果：

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
    at java.util.AbstractList$Itr.next(AbstractList.java:343)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

Vector虽然是线程安全的，但是只是一种相对的线程安全而不是绝对的线程安全，它只能够保证增、删、改、查的单个操作一定是原子的，不会被打断，但是如果组合起来用，并不能保证线程安全性。比如就像上面的线程1在遍历一个Vector中的元素、线程2在删除一个Vector中的元素一样，势必产生并发修改异常，也就是fail-fast。

CopyOnWriteArrayList的作用

把上面的代码修改一下，用CopyOnWriteArrayList：

public static void main(String[] args)
{
    List<Integer> list = new CopyOnWriteArrayList<Integer>();
        
    for (int i = 0; i < 10; i++)
    {
        list.add(i);
    }
    
    T1 t1 = new T1(list);
    T2 t2 = new T2(list);
    t1.start();
    t2.start();
}

可以运行一下这段代码，是没有任何问题的。

看到我把元素数量改小了一点，因为我们从上面的分析中应该可以看出，CopyOnWriteArrayList的缺点，就是修改代价十分昂贵，每次修改都伴随着一次的数组复制；但同时优点也十分明显，就是在并发下不会产生任何的线程安全问题，也就是绝对的线程安全，这也是为什么我们要使用CopyOnWriteArrayList的原因。

另外，有两点必须讲一下。我认为CopyOnWriteArrayList这个并发组件，其实反映的是两个十分重要的分布式理念：

（1）读写分离

我们读取CopyOnWriteArrayList的时候读取的是CopyOnWriteArrayList中的Object[] array，但是修改的时候，操作的是一个新的Object[] array，读和写操作的不是同一个对象，这就是读写分离。这种技术数据库用的非常多，在高并发下为了缓解数据库的压力，即使做了缓存也要对数据库做读写分离，读的时候使用读库，写的时候使用写库，然后读库、写库之间进行一定的同步，这样就避免同一个库上读、写的IO操作太多。

（2）最终一致

对CopyOnWriteArrayList来说，线程1读取集合里面的数据，未必是最新的数据。因为线程2、线程3、线程4四个线程都修改了CopyOnWriteArrayList里面的数据，但是线程1拿到的还是最老的那个Object[] array，新添加进去的数据并没有，所以线程1读取的内容未必准确。不过这些数据虽然对于线程1是不一致的，但是对于之后的线程一定是一致的，它们拿到的Object[] array一定是三个线程都操作完毕之后的Object array[]，这就是最终一致。最终一致对于分布式系统也非常重要，它通过容忍一定时间的数据不一致，提升整个分布式系统的可用性与分区容错性。当然，最终一致并不是任何场景都适用的，像火车站售票这种系统用户对于数据的实时性要求非常非常高，就必须做成强一致性的。

最后总结一点，随着CopyOnWriteArrayList中元素的增加，CopyOnWriteArrayList的修改代价将越来越昂贵，因此，CopyOnWriteArrayList适用于读操作远多于修改操作的并发场景中。

HashMap

前面讲了ArrayList、LinkedList以及CopyOnWriteArrayList，就前两者而言，反映的是两种思想：

（1）ArrayList以数组形式实现，顺序插入、查找快，插入、删除较慢

（2）LinkedList以链表形式实现，顺序插入、查找较慢，插入、删除方便

那么是否有一种数据结构能够结合上面两种的优点呢？有，答案就是HashMap。

HashMap是一种非常常见、方便和有用的集合，是一种键值对（K-V）形式的存储结构，下面将还是用图示的方式解读HashMap的实现原理，

四个关注点在HashMap上的答案

关 注 点	结论
HashMap是否允许空	Key和Value都允许为空
HashMap是否允许重复数据	Key重复会覆盖、Value允许重复
HashMap是否有序	无序，特别说明这个无序指的是遍历HashMap的时候，得到的元素的顺序基本不可能是put的顺序
HashMap是否线程安全	非线程安全

添加数据

首先看一下HashMap的一个存储单元Entry：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    ...
}

LinkedList是一个双向链表，从HashMap的Entry看得出，Entry组成的是一个单向链表，因为里面只有Entry的后继Entry，而没有Entry的前驱Entry。就是下面这个结构：

Entry
K key
V value
Entry<K,V> next
int hash

接下来，假设我有这么一段代码：

public static void main(String[] args)
{
    Map<String, String> map = new HashMap<String, String>();
    map.put("111", "111");
    map.put("222", "222");
}

看一下做了什么。首先从第3行开始，new了一个HashMap出来：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

注意一下第5行的init()是个空方法，它是HashMap的子类比如LinkedHashMap构造的时候使用的。DEFAULT_INITIAL_CAPACITY为16，也就是说，HashMap在new的时候构造出了一个大小为16的Entry数组，Entry内所有数据都取默认值，如图示为：

看到new出了一个大小为16的Entry数组来。接着第4行，put了一个Key和Value同为111的字符串，看一下put的时候底层做了什么：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
       Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

看一下put方法的几个步骤：

1、第2行~第3行就是HashMap允许Key值为空的原因，空的Key会默认放在第0位的数组位置上

2、第4行拿到Key值的HashCode，由于HashCode是Object的方法，因此每个对象都有一个HashCode，对这个HashCode做一次hash计算。按照JDK源码注释的说法，这次hash的作用是根据给定的HashCode对它做一次打乱的操作，防止一些糟糕的Hash算法产生的糟糕的Hash值，至于为什么要防止糟糕的Hash值，HashMap添加元素的最后会讲到

3、第5行根据重新计算的HashCode，对Entry数组的大小取模得到一个Entry数组的位置。看到这里使用了&，移位加快一点代码运行效率。另外，这个取模操作的正确性依赖于length必须是2的N次幂，这个熟悉二进制的朋友一定理解，因此注意HashMap构造函数中，如果你指定HashMap初始数组的大小initialCapacity，如果initialCapacity不是2的N次幂，HashMap会算出大于initialCapacity的最小2的N次幂的值，作为Entry数组的初始化大小。这里为了讲解方便，我们假定字符串111和字符串222算出来的i都是1

4、第6行~第14行会先判断一下原数据结构中是否存在相同的Key值，存在则覆盖并返回，不执行后面的代码。注意一下recordAccess这个方法，它也是HashMap的子类比如LinkedHashMap用的，HashMap中这个方法为空。另外，注意一点，对比Key是否相同，是先比HashCode是否相同，HashCode相同再判断equals是否为true，这样大大增加了HashMap的效率，对HashCode不熟悉的朋友可以看一下我的这篇文章讲讲HashCode的作用

5、第16行的modeCount++是用于fail-fast机制的，每次修改HashMap数据结构的时候都会自增一次这个值

然后就到了关键的addEntry方法了：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

假设new出来的Entry地址为0x00000001，那么，put("111", "111")用图表示应该是这样的：

每一个新增的Entry都位于table[1]上，另外，里面的hash是rehash之后的hash而不是Key最原始的hash。看到table[1]上存放了111---->111这个键值对，它持有原table[1]的引用地址，因此可以寻址到原table[1]，这就是单向链表。 再看一下put("222", "222")做了什么，一张图就可以理解了：

新的Entry再次占据table[1]的位置，并且持有原table[1]，也就是111---->111这个键值对。

至此，HashMap进行put数据的过程就呈现清楚了。不过还有一个问题，就是HashMap如何进行扩容，再看一下addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

看到第4行~第5行，也就是说在每次放置完Entry之后都会判断是否需要扩容。这里不讲扩容是因为HashMap扩容在不正确的使用场景下将会导致死循环，这是一个值得探讨的话题，也是我工作中实际遇到过的一个问题，因此下一篇文章将会详细说明为什么不正确地使用HashMap会导致死循环。

删除数据

public static void main(String[] args)
{
    Map<String, String> map = new HashMap<String, String>();
    map.put("111", "111");
    map.put("222", "222");
    map.remove("111");
}

第6行删除元素，看一下删除元素的时候做了什么，第4行~第5行添加了两个键值对就沿用上面的图，HashMap删除指定键值对的源代码是：

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

分析一下remove元素的时候做了几步：

1、根据key的hash找到待删除的键值对位于table的哪个位置上

2、记录一个prev表示待删除的Entry的前一个位置Entry，e可以认为是当前位置

3、从table[i]开始遍历链表，假如找到了匹配的Entry，要做一个判断，这个Entry是不是table[i]：

（1）是的话，也就是第14行~第15行，table[i]就直接是table[i]的下一个节点，后面的都不需要动

（2）不是的话，也就是第16行~第17行，e的前一个Entry也就是prev，prev的next指向e的后一个节点，也就是next，这样，e所代表的Entry就被踢出了，e的前后Entry就连起来了

remove("111")用图表示就是：

整个过程只需要修改一个节点的next的值即可，非常方便。

修改数据

修改元素也是put，看一下源代码：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

这个其实前面已经提到过了，第6行~第14行就是修改元素的逻辑，如果某个Key已经在数据结构中存在的话，那么就会覆盖原value，也就是第10行的代码。

插入数据

所谓"插入元素"，在我的理解里，一定是基于数据结构是有序的前提下的。像ArrayList、LinkedList，再远点说就是数据库，一条一条都是有序的。

而HashMap，它的顺序是基于HashCode，HashCode是一个随机性很强的数字，所以HashMap中的Entry完全是随机存放的。HashMap又不像LinkedHashMap这样维护了插入元素的顺序，所以对HashMap这个数据结构谈插入元素是没有意义的。

所以，HashMap并没有插入的概念。

再谈HashCode的重要性

前面讲到了，HashMap中对Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那么为什么要防止糟糕的HashCode？

糟糕的HashCode意味着的是Hash冲突，即多个不同的Key可能得到的是同一个HashCode，糟糕的Hash算法意味着的就是Hash冲突的概率增大，这意味着HashMap的性能将下降，表现在两方面：

1、有10个Key，可能6个Key的HashCode都相同，另外四个Key所在的Entry均匀分布在table的位置上，而某一个位置上却连接了6个Entry。这就失去了HashMap的意义，HashMap这种数据结构性高性能的前提是，Entry均匀地分布在table位置上，但现在确是1 1 1 1 6的分布。所以，我们要求HashCode有很强的随机性，这样就尽可能地可以保证了Entry分布的随机性，提升了HashMap的效率。

2、HashMap在一个某个table位置上遍历链表的时候的代码：if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

看到，由于采用了"&&"运算符，因此先比较HashCode，HashCode都不相同就直接pass了，不会再进行equals比较了。HashCode因为是int值，比较速度非常快，而equals方法往往会对比一系列的内容，速度会慢一些。Hash冲突的概率大，意味着equals比较的次数势必增多，必然降低了HashMap的效率了。

HashMap的table为什么是transient的

一个非常细节的地方：

transient Entry[] table;

看到table用了transient修饰，也就是说table里面的内容全都不会被序列化，不知道大家有没有想过这么写的原因？

在我看来，这么写是非常必要的。因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的：

public native int hashCode();

这意味着的是：HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。再进一步说得明白些就是，可能同一个Key在虚拟机A上的HashCode=1，在虚拟机B上的HashCode=2，在虚拟机C上的HashCode=3。

这就有问题了，Java自诞生以来，就以跨平台性作为最大卖点，好了，如果table不被transient修饰，在虚拟机A上可以用的程序到虚拟机B上可以用的程序就不能用了，失去了跨平台性，因为：

1、Key在虚拟机A上的HashCode=100，连在table[4]上

2、Key在虚拟机B上的HashCode=101，这样，就去table[5]上找Key，明显找不到

整个代码就出问题了。因此，为了避免这一点，Java采取了重写自己序列化table的方法，在writeObject选择将key和value追加到序列化的文件最后面：

private void writeObject(java.io.ObjectOutputStream s)
        throws IOException
{
Iterator<Map.Entry<K,V>> i =
    (size > 0) ? entrySet0().iterator() : null;

// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();

// Write out number of buckets
s.writeInt(table.length);

// Write out size (number of Mappings)
s.writeInt(size);

    // Write out keys and values (alternating)
if (i != null) {
 while (i.hasNext()) {
    Map.Entry<K,V> e = i.next();
    s.writeObject(e.getKey());
    s.writeObject(e.getValue());
    }
    }
}

而在readObject的时候重构HashMap数据结构：

private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException
{
// Read in the threshold, loadfactor, and any hidden stuff
s.defaultReadObject();

// Read in number of buckets and allocate the bucket array;
int numBuckets = s.readInt();
table = new Entry[numBuckets];

    init();  // Give subclass a chance to do its thing.

// Read in size (number of Mappings)
int size = s.readInt();

// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i<size; i++) {
    K key = (K) s.readObject();
    V value = (V) s.readObject();
    putForCreate(key, value);
}
}

一种麻烦的方式，但却保证了跨平台性。

这个例子也告诉了我们：尽管使用的虚拟机大多数情况下都是HotSpot，但是也不能对其它虚拟机不管不顾，有跨平台的思想是一件好事。

HashMap和Hashtable的区别

HashMap和Hashtable是一组相似的键值对集合，它们的区别也是面试常被问的问题之一，我这里简单总结一下HashMap和Hashtable的区别：

1、Hashtable是线程安全的，Hashtable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是线程非安全的

2、Hashtable不允许空的value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制

3、上面两个缺点是最主要的区别，另外一个区别无关紧要，我只是提一下，就是两个的rehash算法不同，Hashtable的是：

private int hash(Object k) {
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

这个hashSeed是使用sun.misc.Hashing类的randomHashSeed方法产生的。HashMap的rehash算法上面看过了，也就是：

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);
}

LinkedHashMap

大多数情况下，只要不涉及线程安全问题，Map基本都可以使用HashMap，不过HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。HashMap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的Map。

这个时候，LinkedHashMap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。

四个关注点在LinkedHashMap上的答案

关 注 点	结 论
LinkedHashMap是否允许键值对为空	Key和Value都允许空
LinkedHashMap是否允许重复数据	Key重复会覆盖、Value允许重复
LinkedHashMap是否有序	有序
LinkedHashMap是否线程安全	非线程安全

LinkedHashMap基本数据结构

关于LinkedHashMap，先提两点：

1、LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序

2、LinkedHashMap的基本实现思想就是----多态。可以说，理解多态，再去理解LinkedHashMap原理会事半功倍；反之也是，对于LinkedHashMap原理的学习，也可以促进和加深对于多态的理解。

为什么可以这么说，首先看一下，LinkedHashMap的定义：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    ...
}

看到，LinkedHashMap是HashMap的子类，自然LinkedHashMap也就继承了HashMap中所有非private的方法。再看一下LinkedHashMap中本身的方法：

看到LinkedHashMap中并没有什么操作数据结构的方法，也就是说LinkedHashMap操作数据结构（比如put一个数据），和HashMap操作数据的方法完全一样，无非就是细节上有一些的不同罢了。

LinkedHashMap和HashMap的区别在于它们的基本数据结构上，看一下LinkedHashMap的基本数据结构，也就是Entry：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    ...
}

列一下Entry里面有的一些属性吧：

属性
K key
V value
Entry <K, V> next
int hash
Entry <K, V> before
Entry <K, V> after

其中前面四个，是从HashMap.Entry中继承过来的；后面两个，分是LinkedHashMap独有的。不要搞错了next和before、After，next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。

初始化LinkedHashMap

假如有这么一段代码：

public static void main(String[] args)
{
    LinkedHashMap<String, String> linkedHashMap =
            new LinkedHashMap<String, String>();
    linkedHashMap.put("111", "111");
    linkedHashMap.put("222", "222");
}

首先是第3行~第4行，new一个LinkedHashMap出来，看一下做了什么：

public LinkedHashMap() {
super();
    accessOrder = false;
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

void init() {
    header = new Entry<K,V>(-1, null, null, null);
    header.before = header.after = header;
}

/**
 * The head of the doubly linked list.
 */
private transient Entry<K,V> header;

这里出现了第一个多态：init()方法。尽管init()方法定义在HashMap中，但是由于：

1、LinkedHashMap重写了init方法

2、实例化出来的是LinkedHashMap

因此实际调用的init方法是LinkedHashMap重写的init方法。假设header的地址是0x00000000，那么初始化完毕，实际上是这样的：

LinkedHashMap添加元素

继续看LinkedHashMap添加元素，也就是put("111","111")做了什么，首先当然是调用HashMap的put方法：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

第17行又是一个多态，因为LinkedHashMap重写了addEntry方法，因此addEntry调用的是LinkedHashMap重写了的方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
    createEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed, else grow capacity if appropriate
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

因为LinkedHashMap由于其本身维护了插入的先后顺序，因此LinkedHashMap可以用来做缓存，第5行~第7行是用来支持FIFO算法的，这里暂时不用去关心它。看一下createEntry方法：

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

第2行~第4行的代码和HashMap没有什么不同，新添加的元素放在table[i]上，差别在于LinkedHashMap还做了addBefore操作，这四行代码的意思就是让新的Entry和原链表生成一个双向链表。假设字符串111放在位置table[1]上，生成的Entry地址为0x00000001，那么用图表示是这样的：

如果熟悉LinkedList的源码应该不难理解，还是解释一下，注意下existingEntry表示的是header：

1、after=existingEntry，即新增的Entry的after=header地址，即after=0x00000000

2、before=existingEntry.before，即新增的Entry的before是header的before的地址，header的before此时是0x00000000，因此新增的Entry的before=0x00000000

3、before.after=this，新增的Entry的before此时为0x00000000即header，header的after=this，即header的after=0x00000001

4、after.before=this，新增的Entry的after此时为0x00000000即header，header的before=this，即header的before=0x00000001

这样，header与新增的Entry的一个双向链表就形成了。再看，新增了字符串222之后是什么样的，假设新增的Entry的地址为0x00000002，生成到table[2]上，用图表示是这样的：

就不细解释了，只要before、after清除地知道代表的是哪个Entry的就不会有什么问题。

总得来看，再说明一遍，LinkedHashMap的实现就是HashMap+LinkedList的实现方式，以HashMap维护数据结构，以LinkList的方式维护数据插入顺序。

利用LinkedHashMap实现LRU算法缓存

前面讲了LinkedHashMap添加元素，删除、修改元素就不说了，比较简单，和HashMap+LinkedList的删除、修改元素大同小异，下面讲一个新的内容。

LinkedHashMap可以用来作缓存，比方说LRUCache，看一下这个类的代码，很简单，就十几行而已：

public class LRUCache extends LinkedHashMap
{
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

顾名思义，LRUCache就是基于LRU算法的Cache（缓存），这个类继承自LinkedHashMap，而类中看到没有什么特别的方法，这说明LRUCache实现缓存LRU功能都是源自LinkedHashMap的。LinkedHashMap可以实现LRU算法的缓存基于两点：

1、LinkedList首先它是一个Map，Map是基于K-V的，和缓存一致

2、LinkedList提供了一个boolean值可以让用户指定是否实现LRU

那么，首先我们了解一下什么是LRU：LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比方说数据a，1天前访问了；数据b，2天前访问了，缓存满了，优先会淘汰数据b。

我们看一下LinkedList带boolean型参数的构造方法：

public LinkedHashMap(int initialCapacity,
         float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

就是这个accessOrder，它表示：

（1）false，所有的Entry按照插入的顺序排列

（2）true，所有的Entry按照访问的顺序排列

第二点的意思就是，如果有1 2 3这3个Entry，那么访问了1，就把1移到尾部去，即2 3 1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最头的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最头的那个数据就是要淘汰的数据。

"访问"，这个词有两层意思：

1、根据Key拿到Value，也就是get方法

2、修改Key对应的Value，也就是put方法

首先看一下get方法，它在LinkedHashMap中被重写：

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

然后是put方法，沿用父类HashMap的：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

修改数据也就是第6行~第14行的代码。看到两端代码都有一个共同点：都调用了recordAccess方法，且这个方法是Entry中的方法，也就是说每次的recordAccess操作的都是某一个固定的Entry。

recordAccess，顾名思义，记录访问，也就是说你这次访问了双向链表，我就把你记录下来，怎么记录？把你访问的Entry移到尾部去。这个方法在HashMap中是一个空方法，就是用来给子类记录访问用的，看一下LinkedHashMap中的实现：

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

private void remove() {
    before.after = after;
    after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

看到每次recordAccess的时候做了两件事情：

1、把待移动的Entry的前后Entry相连

2、把待移动的Entry移动到尾部

当然，这一切都是基于accessOrder=true的情况下。最后用一张图表示一下整个recordAccess的过程吧：

代码演示LinkedHashMap按照访问顺序排序的效果

最后代码演示一下LinkedList按照访问顺序排序的效果，验证一下上一部分LinkedHashMap的LRU功能：

public static void main(String[] args)
{
    LinkedHashMap<String, String> linkedHashMap =
            new LinkedHashMap<String, String>(16, 0.75f, true);
    linkedHashMap.put("111", "111");
    linkedHashMap.put("222", "222");
    linkedHashMap.put("333", "333");
    linkedHashMap.put("444", "444");
    loopLinkedHashMap(linkedHashMap);
    linkedHashMap.get("111");
    loopLinkedHashMap(linkedHashMap);
    linkedHashMap.put("222", "2222");
    loopLinkedHashMap(linkedHashMap);
}
    
public static void loopLinkedHashMap(LinkedHashMap<String, String> linkedHashMap)
{
    Set<Map.Entry<String, String>> set = inkedHashMap.entrySet();
    Iterator<Map.Entry<String, String>> iterator = set.iterator();
    
    while (iterator.hasNext())
    {
        System.out.print(iterator.next() + "\t");
    }
    System.out.println();
}

注意这里的构造方法要用三个参数那个且最后的要传入true，这样才表示按照访问顺序排序。看一下代码运行结果：

111=111    222=222    333=333    444=444    
222=222    333=333    444=444    111=111    
333=333    444=444    111=111    222=2222   

代码运行结果证明了两点：

1、LinkedList是有序的

2、每次访问一个元素（get或put），被访问的元素都被提到最后面去了

TreeMap

HashMap与LinkedHashMap，它们保证了以O(1)的时间复杂度进行增、删、改、查，从存储角度考虑，这两种数据结构是非常优秀的。另外，LinkedHashMap还额外地保证了Map的遍历顺序可以与put顺序一致，解决了HashMap本身无序的问题。

尽管如此，HashMap与LinkedHashMap还是有自己的局限性----它们不具备统计性能，或者说它们的统计性能时间复杂度并不是很好才更准确，所有的统计必须遍历所有Entry，因此时间复杂度为O(N)。比如Map的Key有1、2、3、4、5、6、7，我现在要统计：

• 所有Key比3大的键值对有哪些
• Key最小的和Key最大的是哪两个

就类似这些操作，HashMap和LinkedHashMap做得比较差，此时我们可以使用TreeMap。TreeMap的Key按照自然顺序进行排序或者根据创建映射时提供的Comparator接口进行排序。TreeMap为增、删、改、查这些操作提供了log(N)的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的O(1)时间复杂度要差些；但是在统计性能上，TreeMap同样可以保证log(N)的时间开销，这又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。

因此总结而言：如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。

红黑树的一些基本概念

在讲TreeMap前还是先说一下红黑树的一些基本概念，这样可以更好地理解之后TreeMap的源代码。

二叉查找树是在生成的时候是非常容易失衡的，造成的最坏情况就是一边倒（即只有左子树/右子树），这样会导致树检索的效率大大降低。（关于树和二叉查找树可以看另一篇文章树型结构）

红黑树是为了维护二叉查找树的平衡而产生的一种树，根据维基百科的定义，红黑树有五个特性，但我觉得讲得不太易懂，我自己总结一下，红黑树的特性大致有三个（换句话说，插入、删除节点后整个红黑树也必须满足下面的三个性质，如果不满足则必须进行旋转）：

1. 根节点与叶节点都是黑色节点，其中叶节点为Null节点
2. 每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点
3. 从根节点到所有叶子节点上的黑色节点数量是相同的

上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是：

1. 红黑树中最短的可能路径是全部为黑色节点的路径
2. 红黑树中最长的可能路径是红黑相间的路径

此时（2）正好是（1）的两倍长。结果就是这个树大致上是平衡的，因为比如插入、删除和查找某个值这样的操作最坏情况都要求与树的高度成比例，这个高度的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树，最终保证了红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除。

下面展示一张红黑树的实例图：

可以看到根节点到所有NULL LEAF节点（即叶子节点）所经过的黑色节点都是2个。

另外从这张图上我们还能得到一个结论：红黑树并不是高度的平衡树。所谓平衡树指的是一棵空树或它的左右两个子树的高度差的绝对值不超过1，但是我们看：

• 最左边的路径0026-->0017-->0012-->0010-->0003-->NULL LEAF，它的高度为5
• 最后边的路径0026-->0041-->0047-->NULL LEAF，它的高度为3

左右子树的高度差值为2，因此红黑树并不是高度平衡的，它放弃了高度平衡的特性而只追求部分平衡，这种特性降低了插入、删除时对树旋转的要求，从而提升了树的整体性能。而其他平衡树比如AVL树虽然查找性能为性能是O(logn)，但是为了维护其平衡特性，可能要在插入、删除操作时进行多次的旋转，产生比较大的消耗。

四个关注点在TreeMap上的答案

关 注 点	结论
TreeMap是否允许键值对为空	Key不允许为空，Value允许为空
TreeMap是否允许重复数据	Key重复会覆盖，Value允许重复
TreeMap是否有序	按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序
TreeMap是否线程安全	非线程安全

TreeMap基本数据结构

TreeMap基于红黑树实现，既然是红黑树，那么每个节点中除了Key-->Value映射之外，必然存储了红黑树节点特有的一些内容，它们是：

1. 父节点引用
2. 左子节点引用
3. 右子节点引用
4. 节点颜色

TreeMap的节点Java代码定义为：

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        ...
}

由于颜色只有红色和黑色两种，因此颜色可以使用布尔类型（boolean）来表示，黑色表示为true，红色为false。

TreeMap添加数据流程总结

首先看一下TreeMap如何添加数据，测试代码为：

public class MapTest {

    @Test
    public void testTreeMap() {
        TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
        treeMap.put(10, "10");
        treeMap.put(85, "85");
        treeMap.put(15, "15");
        treeMap.put(70, "70");
        treeMap.put(20, "20");
        treeMap.put(60, "60");
        treeMap.put(30, "30");
        treeMap.put(50, "50");

        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }
    
}

本文接下来的内容会给出插入每条数据之后红黑树的数据结构是什么样子的。首先看一下treeMap的put方法的代码实现：

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

从这段代码，先总结一下TreeMap添加数据的几个步骤：

1. 获取根节点，根节点为空，产生一个根节点，将其着色为黑色，退出余下流程
2. 获取比较器，如果传入的Comparator接口不为空，使用传入的Comparator接口实现类进行比较；如果传入的Comparator接口为空，将Key强转为Comparable接口进行比较
3. 从根节点开始逐一依照规定的排序算法进行比较，取比较值cmp，如果cmp=0，表示插入的Key已存在；如果cmp>0，取当前节点的右子节点；如果cmp<0，取当前节点的左子节点
4. 排除插入的Key已存在的情况，第（3）步的比较一直比较到当前节点t的左子节点或右子节点为null，此时t就是我们寻找到的节点，cmp>0则准备往t的右子节点插入新节点，cmp<0则准备往t的左子节点插入新节点
5. new出一个新节点，默认为黑色，根据cmp的值向t的左边或者右边进行插入
6. 插入之后进行修复，包括左旋、右旋、重新着色这些操作，让树保持平衡性

第1~第5步都没有什么问题，红黑树最核心的应当是第6步插入数据之后进行的修复工作，对应的Java代码是TreeMap中的fixAfterInsertion方法，下面看一下put每个数据之后TreeMap都做了什么操作，借此来理清TreeMap的实现原理。

put(10, "10")

首先是put(10, "10")，由于此时TreeMap中没有任何节点，因此10为根且根节点为黑色节点，put(10, "10")之后的数据结构为：

put(85, "85")

接着是put(85, "85")，这一步也不难，85比10大，因此在10的右节点上，但是由于85不是根节点，因此会执行fixAfterInsertion方法进行数据修正，看一下fixAfterInsertion方法代码实现：

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

我们看第2行的代码，它将默认的插入的那个节点着色成为红色，这很好理解：

根据红黑树的性质（3），红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的，因此如果插入的节点着色为黑色，那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量，因此默认插入的节点必须是红色的，以此来维持红黑树的性质（3）

当然插入节点着色为红色节点后，有可能导致的问题是违反性质（2），即出现连续两个红色节点，这就需要通过旋转操作去改变树的结构，解决这个问题。

接着看第4行的判断，前两个条件都满足，但是因为85这个节点的父节点是根节点的，根节点是黑色节点，因此这个条件不满足，while循环不进去，直接执行一次30行的代码给根节点着色为黑色（因为在旋转过程中有可能导致根节点为红色，而红黑树的根节点必须是黑色，因此最后不管根节点是不是黑色，都要重新着色确保根节点是黑色的）。

那么put(85, "85")之后，整个树的结构变为：

fixAfterInsertion方法流程

在看put(15, "15")之前，必须要先过一下fixAfterInsertion方法。第5行～第21行的代码和第21行~第38行的代码是一样的，无非一个是操作左子树另一个是操作右子树而已，因此就看前一半：

while (x != null && x != root && x.parent.color == RED) {
    if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        Entry<K,V> y = rightOf(parentOf(parentOf(x)));
        if (colorOf(y) == RED) {
            setColor(parentOf(x), BLACK);
            setColor(y, BLACK);
            setColor(parentOf(parentOf(x)), RED);
            x = parentOf(parentOf(x));
        } else {
            if (x == rightOf(parentOf(x))) {
                x = parentOf(x);
                rotateLeft(x);
            }
            setColor(parentOf(x), BLACK);
            setColor(parentOf(parentOf(x)), RED);
            rotateRight(parentOf(parentOf(x)));
        }
    }
    ....
}

第2行的判断注意一下，用语言描述出来就是：判断当前节点的父节点与当前节点的父节点的父节点的左子节点是否同一个节点。翻译一下就是：当前节点是否左子节点插入，关于这个不明白的我就不解释了，可以自己多思考一下。对这整段代码我用流程图描述一下：

这里有一个左子树内侧插入与左子树点外侧插入的概念，我用图表示一下：

其中左边的是左子树外侧插入，右边的是左子树内侧插入，可以从上面的流程图上看到，对于这两种插入方式的处理是不同的，区别是后者也就是左子树内侧插入多一步左旋操作。

能看出，红黑树的插入最多只需要进行两次旋转，至于红黑树的旋转，后面结合代码进行讲解。

put(15, "15")

看完fixAfterInsertion方法流程之后，继续添加数据，这次添加的是put(15, "15")，15比10大且比85小，因此15最终应当是85的左子节点，默认插入的是红色节点，因此首先将15作为红色节点插入85的左子节点后的结构应当是：

但是显然这里违反了红黑树的性质（2），即连续出现了两个红色节点，因此此时必须进行旋转。回看前面fixAfterInsertion的流程，上面演示的是左子树插入流程，右子树一样，可以看到这是右子树内侧插入，需要进行两次旋转操作：

1. 对新插入节点的父节点进行一次右旋操作
2. 新插入节点的父节点着色为黑色，新插入节点的祖父节点着色为红色
3. 对新插入节点的祖父节点进行一次左旋操作

旋转是红黑树中最难理解也是最核心的操作，右旋和左旋是对称的操作，我个人的理解，以右旋为例，对某个节点x进行右旋，其实质是：

• 降低左子树的高度，增加右子树的高度
• 将x变为当前位置的右子节点

左旋是同样的道理，在旋转的时候一定要记住这两句话，这将会帮助我们清楚地知道在不同的场景下旋转如何进行。

先看一下（1）也就是"对新插入节点的父节点进行一次右旋操作"，源代码为rotateRight方法：

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
           root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

再用一张示例图表示一下右旋各节点的变化，旋转不会改变节点颜色，这里就不区分红色节点和黑色节点了，a是需要进行右旋的节点：

左旋与右旋是一个对称的操作，大家可以试试看把右图的b节点进行左旋，就变成了左图了。这里多说一句，旋转一定要说明是对哪个节点进行旋转，网上看很多文章讲左旋、右旋都是直接说旋转之后怎么样怎么样，我认为脱离具体的节点讲旋转是没有任何意义的。

这里可能会有的一个问题是：b有左右两个子节点分别为d和e，为什么右旋的时候要将右子节点e拿到a的左子节点而不是b的左子节点d？

一个很简单的解释是：如果将b的左子节点d拿到a的左子节点，那么b右旋后右子节点指向a，b原来的右子节点e就成为了一个游离的节点，游离于整个数据结构之外。

回到实际的例子，对85这个节点进行右旋之后还有一次着色操作（2），分别是将x的父节点着色为黑色，将x的祖父节点着色为红色，那么此时的树形结构应当为：

然后对节点10进行一次左旋操作（3），左旋之后的结构为：

最后不管根节点是不是黑色，都将根节点着色为黑色，那么插入15之后的数据结构就变为了上图，满足红黑树的三条特性。

put(70, "70")

put(70, "70")就很简单了，70是85的左子节点，由于70的父节点以及叔父节点都是红色节点，因此直接将70的父节点85、将70的叔父节点10着色为黑色即可，70这个节点着色为红色，即满足红黑树的特性，插入70之后的结构图为：

put(20, "20")

put(20, "20")，插入的位置应当是70的左子节点，默认插入红色，插入之后的结构图为：

问题很明显，出现了连续两个红色节点，20的插入位置是一种左子树外侧插入的场景，因此只需要进行着色+对节点85进行一次右旋即可，着色+右旋之后数据结构变为：

put(60, "60")

下面进行put(60, "60")操作，节点60插入的位置是节点20的右子节点，由于节点60的父节点与叔父节点都是红色节点，因此只需要将节点60的父节点与叔父节点着色为黑色，将节点60的组父节点着色为红色即可。

那么put(60, "60")之后的结构为：

put(30, "30")

put(30, "30")，节点30应当为节点60的左子节点，因此插入节点30之后应该是这样的：

显然这里违反了红黑树性质（2）即连续出现了两个红色节点，因此这里要进行旋转。

put(30, "30")的操作和put(15, "15")的操作类似，同样是右子树内侧插入的场景，那么需要进行两次旋转：

1. 对节点30的父节点节点60进行一次右旋
2. 右旋之后对节点60的祖父节点20进行一次左旋 右旋+着色+左旋之后，put(30, "30")的结果应当为：

put(50, "50")

下一个操作是put(50, "50")，节点50是节点60的左子节点，由于节点50的父亲节点与叔父节点都是红色节点，因此只需要将节点50的父亲节点与叔父节点着色为黑色，将节点50的祖父节点着色为红色即可：

节点50的父节点与叔父节点都是红色节点（注意不要被上图迷糊了！上图是重新着色之后的结构而不是重新着色之前的结构，重新着色之前的结构为上上图），因此插入节点50只需要进行着色，本身这样的操作是没有任何问题的，但问题的关键在于，着色之后出现了连续的红色节点，即节点30与节点70。这就是为什么fixAfterInsertion方法的方法体是while循环的原因：

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
    ...
    }
}

因为这种着色方式是将插入节点的祖父节点着色为红色，因此着色之后必须将当前节点指向插入节点的祖父节点，判断祖父节点与父节点是否连续红色的节点，是就进行旋转，重新让红黑树平衡。

接下来的问题就是怎么旋转了。我们可以把节点15-->节点70-->节点30连起来看，是不是很熟悉？这就是上面重复了两次的右子树内侧插入的场景，那么首先对节点70进行右旋，右旋后的结果为：

下一步，节点70的父节点着色为黑色，节点70的祖父节点着色为红色（这一步不理解或者忘了为什么的，可以去看一下之前对于fixAfterInsertion方法的解读），重新着色后的结构为：

最后一步，对节点70的父节点节点15进行一次左旋，左旋之后的结构为：

重新恢复红黑树的性质：

1. 根节点为黑色节点
2. 没有连续红色节点
3. 根节点到所有叶子节点经过的黑色节点都是2个

红黑树移除节点

移除操作比较复杂，具体移除的操作要进行几次旋转和移除的节点在红黑树中的位置有关，这里也不特意按照旋转次数选择节点了，就找三种位置举例演示红黑树移除操作如何进行：

• 移除根节点，例子就是移除节点30
• 移除中间节点，例子就是移除节点70
• 移除最底下节点，例子就是移除节点85

首先来过一下TreeMap的remove方法：

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

第2行的代码是获取待移除的节点Entry，做法很简单，拿key与当前节点按指定算法做一个比较获取cmp，cmp=0表示当前节点就是待移除的节点；cmp>0，取右子节点继续比较；cmp<0，取左子节点继续比较。

接着重点跟一下第7行的deleteEntry方法：

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

方法第3行~第30行与第30行~第57行是对称的，因此只分析一下前半部分也就是第3行~第30行的代码。第三行的代码**"x == leftOf(parentOf(x))"很显然判断的是x是否其父节点的左子节点**。其流程图为：

从上图中，首先可以得出一个重要的结论：红黑树移除节点最多需要三次旋转。

先看一下删除数据修正之前的结构图：

p指向右下角的黑色节点85，对此节点进行修正，上面的流程图是p是父节点的左子节点的流程，这里的p是父节点的右子节点，没太大区别。

sib取父节点的左子节点即节点60，节点60是一个黑色节点，因此这里不需要进行一次旋转。

接着，sib的左右子节点不是黑色节点且sib的左子节点为红色节点，因此这里只需要进行一次旋转的流程：

1. 将sib着色为它父节点的颜色
2. p的父节点着色为黑色
3. sib的左子节点着色为黑色
4. p的父节点右旋

经过这样四步操作之后，红黑树的结构变为：

最后一步的操作在fixAfterDeletion方法的外层，节点85的父节点不为空，因此将节点85的父节点置空，最终移除节点70之后的数据结构为：

移除最底下节点

最后看看移除最底下节点的场景，以移除节点85为例，节点85根据代码以节点p称呼。

节点p没有左右子节点，因此节点p不需要进行选择继承者的操作；同样的由于节点p没有左右子节点，因此选择出来的replacement为null。

接着由于replacement为null但是节点p是一个黑色节点，黑色节点需要进行删除修正流程：

1. 节点p是父节点的右子节点，那么节点sib为父节点的左子节点50
2. sib是黑色的，因此不需要进行一次右旋
3. sib的左子节点是红色的，因此这里需要进行的操作是将sib着色为p父节点的颜色红色、将p的父节点着色为黑色、将sib的左子节点着色为黑色、将p的父节点进行一次右旋 这么做之后，树形结构变为：

最后还是一样，回到fixAfterDeletion方法外层的代码，将p的父节点置为null，即节点p就不在当前数据结构中了，完成移除，红黑树最终的结构为：

文章来源：https://www.cnblogs.com/xrq730/category/759081.html