文前说明

作为码农中的一员，需要不断的学习，我工作之余将一些分析总结和学习笔记写成博客与大家一起交流，也希望采用这种方式记录自己的学习之旅。

本文仅供学习交流使用，侵权必删。
不用于商业目的，转载请注明出处。

1. 概述

• List、Set、Map 是接口，前两个继承至 Collection 接口，Map 为独立接口。
• List 的实现有 ArrayList、Vector、LinkedList。
• Set 的实现有 HashSet、LinkedHashSet、TreeSet。
• Map 的实现有 Hashtable、LinkedHashMap、HashMap、TreeMap。

2. 原理

2.1 Collection

• 继承了 Iterable 接口，使得集合里的元素能够使用 forEach 循环语句。
• Collection 是集合层次结构的根接口。
• 所有的 Collection 的实现类都是间接实现其子接口来实现。
  • 所有的实现类应该提供两个标准的构造方法。
• 所有的子类接口或实现类都应直接的或间接的定义 equals() 方法。
• 实现类重写的 equals() 和 hashCode() 方法应该具有这样的一个原则。
  • 如果 equals() 返回 true，那么两个对象的 hashcode() 值应该保持相等。
• 默认方法实现（继承或其它）不应用任何同步协议。
  • 如果 Collection 实现具有特定的同步协议，那么应该覆盖默认实现以应用该协议。

方法	说明
int size()	返回此集合中的元素数量。
boolean isEmpty()	判断集合元素是否为空。
boolean contains(Object o)	判断此集合是否包含指定的元素，包含则返回 true，反之。
Iterator<E> iterator()	返回此集合中元素的迭代器，不保证元素返回的顺序（除非此集合是提供保证的某个类的实例）。
Object[] toArray()	将此集合中的元素转换成数组并返回该数组，该方法作为基于数组和集合之间的桥梁的 API。
<T> T[] toArray(T[] a)	返回指定类型数组。
boolean add(E e)	此集合添加指定元素。
boolean remove(Object o)	删除指定元素。
boolean containsAll(Collection<?> c)	判断是否包含特定集合，如果存在则返回 true，反之。
boolean addAll(Collection<? extends E> c)	添加指定集合。
boolean removeAll(Collection<?> c)	删除指定集合。
default boolean removeIf(Predicate<? super E> filter)	移除此集合中满足给定条件的所有元素。
boolean retainAll(Collection<?> c)	仅保留指定类型的集合。
void clear()	清空集合元素。
boolean equals(Object o)	将指定的对象与此集合进行相等比较。
int hashCode()	返回集合的哈希值，用于比较相等与否。

2.2 List

• List 是一个接口，继承自 Collection 接口，定义了一组元素是 有序的、可重复 的集合。
  • 增加了位置相关方法，List 的元素是有序的，有 get(index)、set(index,object)、add(index,object)、remove(index) 方法。

方法	说明
E get(int index)	返回指定位置的元素。
E set(int index, E element)	在指定位置将传入的元素替换当前 list 在此位置的元素。
void add(int index, E element)	在指定位置来将传入的元素添加在当前 list 里面。
E remove(int index)	将指定位置的元素移除。

• 增加搜索方法，indexOf()，lastIndexOf()。

方法	说明
int indexOf(Object o)	返回此列表中指定元素的第一次出现的索引，或如果该列表不包含元素，则返回 -1。
int lastIndexOf(Object o)	返回此列表中指定元素的最后一个出现的索引，或如果该列表不包含元素，则返回 -1。

• 增加范围性操作，使用 subList() 方法对 list 进行任意范围操作。

方法	说明
List<E> subList(int fromIndex, int toIndex)	返回一个列表，这个列表根据传入的开始地址和结束地址，然后在 list 里面截取。

2.3 Set

• Set 集合与 List 一样，都是继承自 Collection 接口。
  • 方法与 Collection 接口保持一致。
  • Set 集合中的元素不能重复，即元素唯一。
  • Set 集合没有 get() 方法，只能通过迭代器（Iterator）来遍历元素，不能随机访问。

2.4 Map

• Map 接口中键和值一一映射，可以通过键来获取值。
  • 给定一个键和一个值，可以将该值存储在一个 Map 对象。之后，可以通过键来访问对应的值。
  • 当访问的值不存在的时候，方法就会抛出一个 NoSuchElementException 异常。

2.5 ArrayList

• ArrayList 是一种变长的集合类，是 List 接口的实现类，基于定长数组实现。
• ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组。
• 由于 ArrayList 底层基于数组实现，所以其可以保证在 O(1) 复杂度下完成随机查找操作。
• ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的错误。

//无参构造方法，ArrayList 的初始化长度为 10，这是一个静态常量
private static final int DEFAULT_CAPACITY = 10;
​
//空的对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
​
//保存 ArrayList 数据的对象数组缓冲区，elementData的初始容量为 10，大小会根据 ArrayList 容量的增长而动态的增长。
private transient Object[] elementData;
//集合的长度
private int size;

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = EMPTY_ELEMENTDATA;
}

• 初始化底层数组 elementData。
• 在可知 ArrayList 插入元素数量的情况下，可使用有参构造方法。按需分配，避免浪费。

2.5.1 插入（add）

/** 在元素序列尾部插入 */
public boolean add(E e) {
    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将新元素插入序列尾部
    elementData[size++] = e;
    return true;
}

/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index 及其之后的所有元素都向后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. 将新元素插入至 index 处
    elementData[index] = element;
    size++;
}

//判断是否出现下标是否越界
private void rangeCheckForAdd(int index) {
  //如果下标超过了集合的尺寸 或者 小于 0 就是越界  
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

• 如果是在元素序列的尾部插入，只需两个步骤即可。
  • 检测数组是否有足够的空间插入。
  • 将新元素插入至序列尾部。

尾部添加元素

• 在元素序列指定位置（假设该位置合理）插入，则需要三个步骤。
  • 检测数组是否有足够的空间。
  • 将 index 及其之后的所有元素向后移一位。
  • 将新元素插入至 index 处。

指定位置插入元素

• 将新元素插入至序列指定位置，需要先将该位置及其之后的元素都向后移动一位，为新元素腾出位置。

  • 这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。

• 在 ArrayList 中，当空间用完，其会按照原数组空间的 1.5 倍进行扩容。

//初始长度是 10，size 默认值 0，假定添加的是第一个元素，那么 minCapacity=1 这是最小容量 如果小于这个容量就会报错
//如果底层数组就是默认数组，那么选一个大的值，就是 10
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //调用另一个方法ensureExplicitCapacity
        ensureExplicitCapacity(minCapacity);
    }
​
    private void ensureExplicitCapacity(int minCapacity) {
        //记录修改的次数
        modCount++;
​
        // overflow-conscious code
        //如果传过来的值大于初始长度 执行 grow 方法（参数为传递的值）扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 //扩容
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新的容量是在原有的容量基础上 +50% 右移一位就是二分之一
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新容量小于最小容量，按照最小容量进行扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //调用工具类 Arrays 的 copyOf 方法扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
​
//Arrays
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;
}

• 其中很多都是边界检查。

2.5.2 删除（remove）

• 删除指定位置的元素或删除指定元素，无法避免移动元素（除非从元素序列的尾部删除）。
• 支持两种删除元素的方式。
  • 按照下标删除。
  • 按照元素删除，会删除和参数匹配的第一个元素。

public E remove(int index) {
  //下标越界检查
  rangeCheck(index);
  //修改次数统计
  modCount++;
  //获取这个下标上的值
  E oldValue = elementData(index);
  //计算出需要移动的元素个数 （因为需要将后续元素左移一位，此处计算出来的是后续元素的位数）
  int numMoved = size - index - 1;
  //如果这个值大于 0，说明后续有元素需要左移，0 说明被移除的对象就是最后一位元素
  if (numMoved > 0)
    //所有元素左移一位  覆盖掉 index 位置上的元素
    System.arraycopy(elementData, index+1, elementData, index,numMoved);
  // 将最后一个元素赋值为 null  这样可以被 GC 回收
  elementData[--size] = null; // clear to let GC do its work
  //返回 index 位置上的元素
  return oldValue;
}
​
//移除特定元素
public boolean remove(Object o) {
  //如果元素是 null 遍历数组移除第一个 null
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        //遍历找到第一个 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 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
}

• 删除操作，有以下几步。
  • 获取指定位置 index 处的元素值。
  • 将 index + 1 及之后的元素向前移动一位。
  • 将最后一个元素置空，并将 size 值减 1。
  • 返回被删除值，完成删除操作。

移除元素

• 往 ArrayList 插入大量元素后，又删除很多元素，此时底层数组会空闲处大量的空间。
  • 因为 ArrayList 没有自动缩容机制，会导致底层数组大量的空闲空间不能被释放，造成浪费。
• ArrayList 提供了手动触发 ArrayList 缩容的机制。

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
}

缩容机制

2.5.3 遍历

• ArrayList 实现了 RandomAccess 接口（该接口是个标志性接口），表明具有随机访问的能力。
  • ArrayList 底层基于数组实现，所以可在常数阶的时间内完成随机访问，效率很高。
• 通过以下方式访问会比 forEach 循环（forEach 最终会被转换成迭代器遍历的形式）遍历效率高。

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

2.5.4 小结

• 底层数组实现，使用默认构造方法初始化出来的容量是 10。
• 扩容的长度是在原长度基础上加二分之一。
• 实现了 RandomAccess 接口，底层又是数组，get() 读取元素性能很好。
• 线程不安全，所有的方法均不是同步方法也没有加锁，因此多线程下慎用。
• 顺序添加很方便。
• 删除和插入需要复制数组，性能很差（可以使用 LinkindList）。
• elementData 用 transient 修饰是对 序列化 的设计。

JDK 1.7 相比于 JDK 1.6

• 第一个优势在于 懒初始化，懒初始化指的是默认构造方法构造的集合类，占据尽可能少的内存空间，在第一次进行包含有添加语义的操作时，才进行真正的初始化工作。

//1.6，两个构造的区别很明显
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<String>(0); // la.elementData = new Object[0], la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<String>(); // lb.elementData = new Object[10], lb.elementData.length = 10
        lb.add("111"); // lb.elementDate.length = 10，这里没有进行扩容，后续再按照通用扩容策略执行扩容操作
    }
}
 
//1.7，两个构造在第一次进行添加时才有区别
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<>(0); // la.elementData = new Object[0], la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<>(); // lb.elementData = EMPTY_ELEMENTDATA, lb.elementData.length = 0
        lb.add("111"); // lb.elementDate.length = 10，这里一次性扩容了 10 个，后续再按照通用扩容策略执行扩容操作
    }
}

//1.8 同 1.7
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<>(0); // la.elementData = EMPTY_ELEMENTDATA, la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<>(); // lb.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, lb.elementData.length = 0
        lb.add("111"); // lb.elementDate.length = 10，这里一次性扩容了 10 个，后续再按照通用扩容策略执行扩容操作
    }
}

• 第二个优化在于扩容相关的完善，避免了过早溢出。
• 第三个优化在于一些方法不再直接使用父类的通用实现，改为利用数组特性的更有效率的实现。
• 这里可以查看上面两点的 具体优化。

JDK 1.8 相比于 JDK 1.7

• 优势在于避免过早的开辟数组空间，采用了空数组的复用。
  • JDK 1.8 增加了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组。
    • 无参构造函数，赋值为新增的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组。
    • 含参构造函数，如果等于 0，则赋值为 EMPTY_ELEMENTDATA 的空数组。

// 1.7 跟 1.6 一样
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
}
 
// 1.8
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; // 重用空数组优化
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

• Collection 拷贝构造方法。

// jdk 1.6
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
 
// jdk 1.7
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
 
// jdk 1.8
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

• c.toArray might (incorrectly) not return Object[] 目的在于考虑了 elementData.getClass() 的对象不是 Object[] 的情况。
  • 以下代码情况 toArray() 返回的是 String[]。

List<String> list = Arrays.asList("abc");
// class java.util.Arrays$ArrayList
System.out.println(list.getClass());
// class [Ljava.lang.String;
Object[] objArray = list.toArray();
System.out.println(objArray.getClass());
objArray[0] = new Object(); // cause ArrayStoreException

ArrayList 和 Vector 的区别

• ArrayList 是线程不安全的，Vector 是线程安全的。
• 扩容 ArrayList 扩 0.5 倍，Vector 扩 1 倍。
• Collections 工具类中有一个 synchronizedList 方法，可以把 list 变为线程安全的集合。

2.6 Vector

• Vector 是 矢量队列，同样实现了 List、RandomAccess 接口。
  • 是一个队列，支持相关的添加、删除、修改、遍历等功能。
  • 提供了随机访问功能。
• 和 ArrayList 不同，Vector 中的操作是 线程安全 的。

// 保存Vector中数据的数组
protected Object[] elementData;

// 实际数据的数量
protected int elementCount;

// 容量增长系数
protected int capacityIncrement;

//指定数组的初始化大小，和增长系数。容量不能小于 0
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

//指定容量，增长系数未 0
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//采用默认 容量 10 增长系数为 0
public Vector() {
    this(10);
}

//使用另一个集合构造改集合
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray 可能（错误地）不返回 Object []
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

2.6.1 添加（add）

• Vector 的 add() 操作跟 ArrayList 不同在于通过 synchronized 进行了修饰保证线程安全，其他跟 ArrayList 保持一致，在 add() 元素的时候会先 grow() 新的容量。

//指定位置插入元素
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                + " > " + elementCount);
    }
    //是否需要扩容
    ensureCapacityHelper(elementCount + 1);
    //通过 arraycopy方 法在插入位置向后移动以为，方便元素插入
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

//添加元素
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

//添加元素
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

//指定位置添加元素
public void add(int index, E element) {
    insertElementAt(element, index);
}

//Vectory 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //新的数组长度 = 旧数组长度 + 增长系数大于 0 加增长系数，否则 + 旧数组长度
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
            capacityIncrement : oldCapacity);
    //如果计算后还不够就 = 最小扩容数
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果大于最大扩容数
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //最大看扩容量为 Integer.MAX_VALUE
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.6.2 删除（remove）

• Vector 的 remove() 操作也通过 synchronized 进行修饰，其他的 remove() 动作和 ArrayList 保持一致。

//移除指定位置的元素
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j 是删除元素在数组中的位置
    int j = elementCount - index - 1;
    if (j > 0) {
        //移动数组位置：新数组位置 = 原数组移除元素的后一位都通过 copy 向前移动一位
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    //copy 多出一位，设置为 null 让 GC 回收
    elementData[elementCount] = null; /* to let GC do its work */
}

//移除元素
public synchronized boolean removeElement(Object obj) {
    modCount++;
    //通过 indexOf 获取在数组中的位置
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

//删除当前数组中的所有元素
public synchronized void removeAllElements() {
    modCount++;
    //让 GC 回收
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

//移除匹配元素
public boolean remove(Object o) {
    return removeElement(o);
}

//指定位置移除元素 并返回被移除的元素
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

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

    return oldValue;
}

//清空集合当前的所有数据
public void clear() {
    removeAllElements();
}

//移除 Vectory 中 fromIndex 到 toIndex 位置上的所有元素
protected synchronized void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = elementCount - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
            numMoved);

    // Let GC do its work
    int newElementCount = elementCount - (toIndex-fromIndex);
    while (elementCount != newElementCount)
        elementData[--elementCount] = null;
}

//移除当前所在光标的元素
public void remove() {
    if (lastRet == -1)
        throw new IllegalStateException();
    synchronized (Vector.this) {
        checkForComodification();
        Vector.this.remove(lastRet);
        expectedModCount = modCount;
    }
    cursor = lastRet;
    lastRet = -1;
}

@Override
@SuppressWarnings("unchecked")
public synchronized boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final int size = elementCount;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // 移位幸存元素留在被移除元素留下的空间
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let GC do its work
        }
        elementCount = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

2.6.3 总结

• Vector 查找与迭代器同样使用了 synchronized 变量进行了修饰保证线程安全。
• Vector 是同步的而 ArrayList 不是， Vector 在一些必要的方法上都加了 synchronized 关键字，但是这也会加大系统开销。
• Vector 中有一个 elements() 方法用以返回一个 Enumeration，以匿名内部类的方式实现。

public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

• Enumeration 接口和 Iterator 类似，产生先于 Iterator，都用作于对集合进行迭代，没有删除功能，已经被 Iterator 取代。
  • Iterator 是 Fast-Fail（快速失败）的，但 Enumeration 不是。

fail-fast

• 快速失败（fail-fast），是 Java 集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，就可能会触发 fail-fast 机制，抛出 ConcurrentModificationException 异常。
  • 快速失败迭代器只是尽最大努力抛出 ConcurrentModificationException。

2.7 LinkedList

• LinkedList 继承自 AbstractSequentialList 抽象类，而不是像 ArrayList 和 Vector 那样继承
  AbstractList，它提供了对序列的连续访问的抽象，不支持随机访问。
• LinkedList 的底层是 Deque 双向链表。
• JDK 1.7 相比于 JDK 1.6 去除了头结点。
  • JDK 1.6 使用一个带有头结点的双向循环链表，头结点不存储实际数据，循环链表指的是能够只通过一个方向的指针重新遍历到自己这个结点的链表。

JDK 1.6 实现方式

• JDK 1.7 之后使用不带头结点的普通的双向链表，增加两个结点指针 first、last 分别指向首尾结点，该优化可以节省一部分的空间。

JDK 1.7 之后实现方式

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;// 最后一个元素

public LinkedList() {}//无参构造函数
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//将c中的元素都添加到此列表中
}

Node 结点

• Node 结点有三个属性。
  • item 代表结点值。
  • prev 代表前一个结点。
  • next 代表后一个结点。

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

• 每个结点都有一个前驱和后继结点，并且在 LinkedList 中定义了两个变量分别指向链表中的第一个和最后一个结点。

transient Node<E> first;
transient Node<E> last;

2.7.1 添加（add）

• LInkedList 添加操作时每个新添加的对象都会被放到新建的 Node 对象中，Node 对象中包含加入的对象和前后指针属性（pred 和 next，pred 和 next 都是 Node 对象，直接存放的就是当前对象的前一个结点对象和后一个结点对象，最后一个结点的 next 值为 null），然后将原来最后一个 last 结点的 next 指针指向新加入的对象，即可。
• LinkedList 在某个位置插入元素是通过将原位置结点的前一个结点的后一个指针指向新插入的元素，然后将原位置的结点的前一个指针指向新元素来实现的，相当于插入元素后后面的元素后移了，但是不是像 ArrayList 那样将所有插入位置后面的元素都后移，此处只是改变其前后结点的指向。

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;//链表最后一个结点
    final Node<E> newNode = new Node<>(l, e, null);//建立结点对象，前一个（perv属性）是last，后一个（next属性）是null，中间item数据是输入的参数e
    last = newNode;
    if (l == null)
        first = newNode; //如果最后一个结点 为null表示链表为空，则添加数据时将新加的数据作为第一个结点
    else
        l.next = newNode; //如果链表不为空则将最后一个链表的next属性指向新添加的结点
    size++; //链表长度自增1
    modCount++;
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//判断index是否越界，越界则抛出异常
    Object[] a = c.toArray();
    int numNew = a.length;//要插入的集合的长度
    if (numNew == 0)
        return false;
    Node<E> pred, succ;//声明pred和succ两个Node对象，用于标识要插入元素的前一个结点和最后一个结点
    if (index == size) { //如果size等于原数组长度则表示在结尾添加
        succ = null;
        pred = last;
    } else {
        succ = node(index);//index位置上的Node对象
        pred = succ.prev;
    }
    for (Object o : a) { //遍历要插入的集合
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode; //如果要插入的位置的前一个结点为null表示是第一个结点，则直接将newNode赋给第一个结点
        else
            pred.next = newNode; //将要插入的集合元素结点对象赋给此位置原结点对象的前一个对象的后一个，即更改前一个结点对象的next指针指到新插入的结点上
        pred = newNode;//更改指向后将新结点对象赋给pred作为下次循环中新插入结点的前一个对象结点，依次循环
    }
    //此时pred代表集合元素的插入完后的最后一个结点对象
    if (succ == null) { //结尾添加的话在添加完集合元素后将最后一个集合的结点对象pred作为last
        last = pred;
    } else {
        pred.next = succ;//将集合元素的最后一个结点对象的next指针指向原index位置上的Node对象
        succ.prev = pred;//将原index位置上的pred指针对象指向集合的最后一个对象
    }
    size += numNew;
    modCount++;
    return true;
}

Node<E> node(int index) {
    if (index < (size >> 1)) { //判断index是否小于size的一半，如果小于则从头遍历结点，否则从结尾遍历结点
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next; //从first第一个结点开始，依次将后一个结点赋给x
        return x; //返回index位置上的Node对象，下同理
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.7.2 删除（remove）

• LinkedList 删除通过将 index 位置上的前一个结点的 next 指向 index 位置的后一个结点，同时将后一个结点的 pred 指向前一个结点，然后将 index 位置上的 Node 结点对象属性都置空来实现，置空后的 Node 对象会被 GC 回。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;//将传入的结点的下一个结点对象赋给其之前前一个结点的下一个结点对象，即将传入的结点对象跳过
        x.prev = null;//将传入对象的前一个结点对象置空使其前一个指针不指向任何元素
    }
    if (next == null) {
        last = prev;//如果next为null表示是最后一个元素，直接将pred结点赋给last
    } else {
        next.prev = prev;
        x.next = null;//将传入结点的后一个结点置空，使其后一个结点指针不指向任何元素
    }
    x.item = null;//将传入的结点对象上的对象置空，也就是整个Node对象中的属性都为空了，后面会被GC回收
    size--;
    modCount++;
    return element;
}

2.7.3 查询

• 查询通过 node 方法实现的，而 node 方法是通过先判断 index 位置是在整个链表的前一半还是后一半来遍历前一半或者后一半元素来获取 index 位置上的元素。

public E get(int index) {
    checkElementIndex(index);//检查索引越界情况
    return node(index).item;//返回该index位置上的结点对象的item属性，即该位置上的实际值
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 视其与中值得差距，决定从前遍历还是从后遍历。
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 循环index次 迭代到所需要的元素
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        // 循环size-1-index次
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.7.4 小结

LinkedList 和 ArrayList 的区别

• ArrayList 基于数组， LinkedList 基于双向链表，对于随机访问， ArrayList 比较占优势，LinkedList 插入、删除元素比较快。
• LinkedList 没有实现自己的 Iterator，但是有 ListIterator 和 DescendingIterator。
• LinkedList 需要更多的内存，ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个结点中存储的是实际的数据和前后结点的位置。
• ArrayList 和 LinkedList 都是非同步的集合，和 ArrayList 一样，LinkedList 也是非线程安全的。
• LinkedList 基于双向链表实现，元素都可以为 null。

2.8 HashSet

• HashSet 是基于 HashMap 来实现的，底层采用了 HashMap 来保存元素，主要使用到的是 HashMap 的 key。
• HashSet 是 没有重复元素 的集合，不保证元素的顺序，允许使用 null 元素。
• HashSet 是 非同步的。
• HashSet 通过 iterator() 返回的迭代器是 fail-fast 的。
• HashMap 相关原理可以查看 【Java 并发笔记】ConcurrentHashMap（1.7） 相关整理 和 【Java 并发笔记】ConcurrentHashMap（1.8） 相关整理。

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
   * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
   * default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
      map = new HashMap<>();
}

• 由于 Set 只使用到了 HashMap 的 key，所以定义一个静态的常量 Object 类 PRESENT（所有写入 map 的 value 值），来充当 HashMap 的 value。之所以不定义为 null 是为了从根源上避免 NullPointerException 的出现。

2.8.1 构造函数

/**
 * 使用 HashMap 的默认容量大小 16 和默认加载因子 0.75 初始化 map，构造一个 HashSet
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * 构造一个指定 Collection 参数的 HashSet，这里不仅仅是 Set，只要实现 Collection 接口的容器都可以
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math. max((int) (c.size()/.75f) + 1, 16));
   // 使用Collection实现的Iterator迭代器，将集合c的元素一个个加入HashSet中
   addAll(c);
}

/**
 * 使用指定的初始容量大小和加载因子初始化map，构造一个HashSet
 */
public HashSet( int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * 使用指定的初始容量大小和默认的加载因子0.75初始化map，构造一个HashSet
 */
public HashSet( int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

/**
 * 不对外公开的一个构造方法（默认default修饰），底层构造的是LinkedHashMap，dummy只是一个标示参数，无具体意义
 */
HashSet( int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

2.8.2 添加（add）

• 由于 HashMap 的 key 不能重复，每当有重复的值写入到 HashSet 时，value 会被覆盖，但 key 不会受到影响，保证了 HashSet 中只能存放不重复的元素。
• 如果指定的元素尚不存在，则将其添加到此集合中。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

addAll

• addAll(Collection<? extends E> c) 在父类 AbstractCollection 中定义。

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

2.8.3 删除（remove）

• 如果存在，则从该集合中移除指定的元素，一旦调用返回，该集合将不包含该元素。

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

removeAll

• removeAll(Collection<?> c) 是父类 AbstractSet 中定义。

public boolean removeAll(Collection<?> c) {
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

2.9 LinkedHashMap（JDK 1.7）

• LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。
• 除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。
• LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。
• LinkedHashMap 继承自 HashMap，所以底层仍然是基于拉链式散列结构，在该结构的基础上，增加了一条双向链表，使得可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • 相比 HashMap，多了两个属性，一个 before，一个 after。next 和 after 有时候会指向同一个 entry，有时候 next 指向 null，而 after 指向 entry。

LinkedHashMap 中的 Entry 对象

Entry 的继承体系

• LinkedHashMap 内部类 Entry 继承自 HashMap 内部类为 Entry，并新增了两个引用，分别是 before 和 after，用于维护双向链表。

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

2.9.1 构造方法

• LinkedHashMap 所有的构造方法里都调用了父类相关的构造方法，在父类构造中有调用 init() 方法，LinkedHashMap 覆盖了该方法，因此初始化先执行父类相关的操作，再执行自己的 init() 方法。

//使用父类中的构造，初始化容量和加载因子，该初始化容量是指数组大小。
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//一个参数的构造
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//无参构造
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//接受map类型的值转换为LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
//参数accessOrder 是存储顺序，LinkedHashMap。
//true：指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 
//false：指定迭代的顺序是按照插入顺序迭代，通过插入元素的顺序来迭代所有元素
//其他三个构造方法默认使用插入顺序。
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

• LinkedHashMap 默认使用的是 插入顺序。

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

• init() 方法主要是将 header 实例化，实例化之后就会出现一个 Entry 类型的 header 的指针,其 before 和 after 都指向自己。

header 实例

• 这个 header，hash 值为 -1，其他都为 null，也就是说这个 header 不放在数组中，只是用来指示开始元素和标志结束元素的。
• header 的目的是为了记录第一个插入的元素，在遍历的时候能够找到第一个元素。

2.9.2 链表的创建

• LinkedHashMap 本身并没有覆写父类的 put 方法，而是直接使用了父类的实现。
• LinkedHashMap 覆写了 addEntry() 、createEntry()、addBefore() 方法。
• LinkedHashMap 的 Entry 之间按照元素的 put 的先后顺序形成了双向循环链表。
• LinkedHashMap 每次添加元素时都能通过 header 找到上一次添加的元素，通过 after 和 before 记录当前元素前面的 entry 与后面的 entry 的联系。

void addEntry(int hash, K key, V value, int bucketIndex) {
    //调用create方法，将新元素以双向链表的的形式加入到映射中
    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);
    }
}

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

• 调用的 e.addBefore(header) 是修改链表，将 e 结点添加到 header 结点之前，让新的 Entry 和原链表生成一个双向链表。
• LinkedHashMap 的实现是 HashMap + LinkedList 的实现方式，以 HashMap 维护数据结构，以 LinkList 的方式维护数据插入顺序。

增加第一个元素步骤

增加第一个元素

• after = existingEntry，即新增的 Entry 的 after = header 地址，即 after = 0x00000000。
• before = existingEntry.before，即新增的 Entry 的 before 是 header 的 before 的地址，header 的 before 此时是 0x00000000，因此新增的 Entry 的 before = 0x00000000。
• before.after = this，新增的 Entry 的 before 此时为 0x00000000 即 header，header 的 after = this，即 header 的 after = 0x00000001。
• after.before = this，新增的 Entry 的 after 此时为 0x00000000 即 header，header 的 before = this，即 header 的 before = 0x00000001。
• header 与新增的 Entry 的一个双向链表形成。

增加第二个元素步骤

增加第二个元素

• 从 table 的角度看，新的 Entry 需要插入到对应的 bucket 里，当有哈希冲突时，采用头插法将新的 Entry 插入到冲突链表的头部。
• 从 header 的角度看，新的 Entry 需要插入到双向链表的尾部（双向链表的头与尾是有连接的）。

2.9.3 元素的读取

• LinkedHashMap 重写了父类 HashMap 的 get() 方法，实际在调用父类 getEntry() 方法取得查找的元素后，再判断当排序模式 accessOrder 为 true 时（即按访问顺序排序），先将当前结点从链表中移除，然后再将当前结点插入到链表尾部。
• 由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

/**
 * 通过key获取value，与HashMap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前结点移到链表尾部(头结点的前一个结点)
 */
public V get(Object key) {
    // 调用父类HashMap的getEntry()方法，取得要查找的元素。  
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    // 记录访问顺序。
    e.recordAccess(this);
    return e.value;
}

/**
 * 在HashMap的put和get方法中，会调用该方法，在HashMap中该方法为空
 * 在LinkedHashMap中，当按访问顺序排序时，该方法会将当前结点插入到链表尾部(头结点的前一个结点)，否则不做任何事
 */
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //当LinkedHashMap按访问排序时
    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;
}

2.9.4 LRU

• LinkedHashMap 可以用来作缓存，LRUCache 是基于 LRU 算法的 Cache（缓存）。

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 功能都是源自 LinkedHashMap。
  • LinkedHashMap 首先是一个 Map，Map 是基于 K-V 的，和缓存一致。
  • LinkedHashMap 提供了一个 boolean 值可以让用户指定是否实现 LRU。
• LRU（即 Least Recently Used）最近最少使用，当缓存满时，会优先删除那些最近最不常访问的数据。

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

accessOrder 值	说明
false	所有的 Entry 按照插入的顺序排列。
true	所有的 Entry 按照访问的顺序排列。

• 每次访问都将访问的数据移动到双向队列的尾部，那么每次需要淘汰数据的时候，双向队列最头的数据即最不常访问的数据。
• 基于 accessOrder = true 的情况的执行过程。

基于 accessOrder = true 的情况的执行过程

• accessOrder 为 true 时，使用的是访问顺序，访问次数最少到访问次数最多，此时要做特殊处理。
  • 处理机制是访问一次，先将自己删除了，然后在把自己添加，这样，近期访问的少的就在链表的开始，最近访问的元素就会在链表的末尾。
  • 如果为 false，默认的是插入顺序，直接通过链表的特点就能依次找到插入元素，不用做特殊处理。

2.9.5 LinkedHashMap（JDK 1.8）

• 因为 LinkedHashMap 很多方法直接继承自 HashMap，而 HashMap 在 JDK1.7 和 JDK 1.8 中实现有区别，因此维护双向链表覆写的方法也不一致。
• JDK 1.8 中 HashMap 底层基于拉链式散列结构，该结构由数组和链表或红黑树组成，LinkedHashMap 在上面结构的基础上，增加了一条双向链表。
• LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node，并新增了两个引用，分别是 before 和 after，同时，TreeNode 继承 LinkedHashMap 的内部类 Entry 后，就具备了和其他 Entry 一起组成链表的能力。
  • 虽然 TreeNode 多了两个用不到的引用，但与 TreeNode 通过继承获取的组成链表的能力相比，这点浪费是值得的。
  • TreeNode 对象的大小约是普通 Node 对象的 2 倍，仅在桶（bin）中包含足够多的结点时再使用。当桶中的结点数量变少时（取决于删除和扩容），TreeNode 会被转成 Node。当用户实现的 hashCode 方法具有良好分布性时，树类型的桶将会很少被使用。 TreeNode 使用的并不多，浪费那点空间是可接受的。

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

LinkedHashMap 中的 Entry 对象

2.9.5.1 链表的创建

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

// 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 覆盖 newNode() 方法，创建了 Entry，并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。

HashMap 原始数据结构 LinkedHashMap 在上面结构的基础上，增加了一条双向链表

2.9.5.2 链表结点的删除

• 与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现。
• 在删除结点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表，而是在删除结点后，回调方法 afterNodeRemoval() 被调用。LinkedHashMap 覆写该方法，并在该方法中完成移除被删除结点的操作。

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

• 删除过程做了三件事。
  • 根据 hash 定位到桶位置。
  • 遍历链表或调用红黑树相关的删除方法。
  • 从 LinkedHashMap 维护的双链表中移除要删除的结点。

待删除结点 3 从单链表中移除该结点 从双向链表中移除该结点

2.9.5.3 元素的读取

• 同样的初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可按访问顺序维护链表。
• 当调用 get()、getOrDefault()、replace() 等方法时，会将访问的结点移动到链表的尾部。

// 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;
        else
            last = b;
    
        if (last == null)
            head = p;
        else {
            // 将 p 接在链表的最后
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

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

2.9.5.4 LRU

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

• 通过覆写 removeEldestEntry() 方法可以实现自定义策略的 LRU 缓存，与 JDK 1.7 中一致。

2.10 LinkedHashSet

• LinkedHashSet 继承自 HashSet，它的添加、删除、查询等方法都是直接使用 HashSet 的，唯一的不同是使用 LinkedHashMap 存储元素。

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

// 只传入容量, 装载因子默认为 0.75
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

// 使用默认容量 16, 默认装载因子 0.75
public LinkedHashSet() {
    super(16, .75f, true);
}

// 将集合 c 中的所有元素添加到 LinkedHashSet 中
// HashSet中使用的是Math.max((int) (c.size()/.75f) + 1, 16)
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
     map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

• LinkedHashSet 不支持按 访问顺序 对元素排序，只能按 插入顺序 排序。

2.11 TreeSet

• TreeSet 的底层是用 TreeMap 实现的。
• 构造方法中会创建一个 TreeMap 实例，用于存放元素。
• TreeSet 也提供了制定比较器的构造函数，如果没有提供比较器，则采用 key 的自然顺序进行比较大小，如果指定的比较器，则采用指定的比较器，进行 key 值大小的比较。

//相同包下可以访问的构造方法，将指定的m赋值为m 
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
//无参构造方法，创建一个空的TreeMap对象，并调用上面的构造方法
public TreeSet() {
    this(new TreeMap<E,Object>());
}
//指定比较器，并用指定的比较器创建TreeMap对象
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
//将指定的集合C转化为TreeSet
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
//将SortedMap中的元素转化为TreeMap对象
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

• add() 方法和 remove() 方法调用 TreeMap 的方法进行实现。

//返回 m 包含的键值对的数量
public int size() {
    return m.size();
}

//是否为空
public boolean isEmpty() {
    return m.isEmpty();
}

//是否包含指定的key
public boolean contains(Object o) {
    return m.containsKey(o);
}

//添加元素，调用m.put方法实现
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

//删除方法，调用m.remove()方法实现
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

//清除集合
public void clear() {
    m.clear();
}

//将一个集合中的所有元素添加到TreeSet中
public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
        Comparator<? super E> mc = map.comparator();
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);
            return true;
        }
    }
    return super.addAll(c);
}

//返回子集合，通过 m.subMap()方法实现
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

//返回set的头部
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

//返回尾部
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

//返回子Set
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

//返回set的头部
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

//返回set的尾部
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}
//返回m使用的比较器
public Comparator<? super E> comparator() {
    return m.comparator();
}

//返回第一个元素
public E first() {
    return m.firstKey();
}
//返回最后一个元素
public E last() {
    return m.lastKey();
}

//返回set中小于e的最大的元素
public E lower(E e) {
    return m.lowerKey(e);
}

//返回set中小于/等于e的最大元素
public E floor(E e) {
    return m.floorKey(e);
}

//返回set中大于/等于e的最大元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}

//返回set中大于e的最小元素
public E higher(E e) {
    return m.higherKey(e);
}

//获取TreeSet中第一个元素，并从Set中删除该元素
public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

//获取TreeSet中最后一个元素，并从Set中删除该元素
public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

//克隆方法
public Object clone() {
    TreeSet<E> clone = null;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }

    clone.m = new TreeMap<>(m);
    return clone;
}

//将对象写入到输出流中。
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden stuff
    s.defaultWriteObject();

    // Write out Comparator
    s.writeObject(m.comparator());

    // Write out size
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    for (E e : m.keySet())
        s.writeObject(e);
}

//从输入流中读取对象的信息
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    s.defaultReadObject();

    // Read in Comparator
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    TreeMap<E,Object> tm;
    if (c==null)
        tm = new TreeMap<>();
    else
        tm = new TreeMap<>(c);
    m = tm;

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

    tm.readTreeSet(size, s, PRESENT);
}

• TreeSet 是一个 有序 的集合，基于 TreeMap 实现，支持 自然排序 和 定制排序。
• TreeSet 是 非同步 的，线程不安全 的。

参考资料

https://www.imooc.com/article/23044
https://segmentfault.com/a/1190000012964859
https://blog.csdn.net/shelleylittlehero/article/details/82954474