Java 集合框架源码解析

知识体系结构

容器包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

Collection 容器

结构图

List

ArrayList

ArrayList 继承了 AbstractList 抽象基类，实现了 List 接口

底层通过数组实现，顺序存储结构，基于动态数组实现，支持随机访问

底层数据结构

transient Object[] elementData; // 用于存储的数组

private int size; // ArrayList 的初始容量

构造器

构造器	描述
ArrayList()	构造一个初始容量为10的空列表。
ArrayList(int initialCapacity)	构造具有指定初始容量的空列表。
ArrayList(Collection<? extends E> c)	按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

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

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

方法概要

变量和类型	方法	描述
void	add(int index, E element)	将指定元素插入此列表中的指定位置。
boolean	add(E e)	将指定的元素追加到此列表的末尾。
boolean	addAll(int index, Collection<? extends E> c)	从指定位置开始，将指定集合中的所有元素插入此列表。
boolean	addAll(Collection<? extends E> c)	将指定集合中的所有元素按指定集合的Iterator返回的顺序附加到此列表的末尾。
void	clear()	从此列表中删除所有元素。
Object	clone()	返回此 ArrayList实例的浅表副本。
boolean	contains(Object o)	如果此列表包含指定的元素，则返回 true 。
void	ensureCapacity(int minCapacity)	如有必要，增加此 ArrayList实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
void	forEach(Consumer<? super E> action)	对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常。
E	get(int index)	返回此列表中指定位置的元素。
int	indexOf(Object o)	返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
boolean	isEmpty()	如果此列表不包含任何元素，则返回 true 。
Iterator	iterator()	以适当的顺序返回此列表中元素的迭代器。
int	lastIndexOf(Object o)	返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
ListIterator	listIterator()	返回此列表中元素的列表迭代器（按适当顺序）。
ListIterator	listIterator(int index)	从列表中的指定位置开始，返回列表中元素的列表迭代器（按正确顺序）。
E	remove(int index)	删除此列表中指定位置的元素。
boolean	remove(Object o)	从该列表中删除指定元素的第一个匹配项（如果存在）。
boolean	removeAll(Collection<?> c)	从此列表中删除指定集合中包含的所有元素。
boolean	removeIf(Predicate<? super E> filter)	删除此集合中满足给定谓词的所有元素。
protected void	removeRange(int fromIndex, int toIndex)	从此列表中删除索引介于 fromIndex （含）和 toIndex （独占）之间的所有元素。
boolean	retainAll(Collection<?> c)	仅保留此列表中包含在指定集合中的元素。
E	set(int index, E element)	用指定的元素替换此列表中指定位置的元素。
int	size()	返回此列表中的元素数。
Spliterator	spliterator()	在此列表中的元素上创建late-binding和故障快速 Spliterator。
List	subList(int fromIndex, int toIndex)	返回指定的 fromIndex （包含）和 toIndex （不包括）之间的此列表部分的视图。
Object[]	toArray()	以适当的顺序（从第一个元素到最后一个元素）返回包含此列表中所有元素的数组。
T[]	toArray(T[] a)	以适当的顺序返回包含此列表中所有元素的数组（从第一个元素到最后一个元素）; 返回数组的运行时类型是指定数组的运行时类型。
void	trimToSize()	将此 ArrayList实例的容量调整为列表的当前大小。

自动扩容

向数组添加元素时，会对当前剩余空间进行检查，如果新添加的元素个数超过剩余空间，数组将自我进行扩容，通过 ensureCapacity(int minCapacity) 方法实现

数组扩容时，会将老数组中的元素重新拷贝至一份新数组中，int newCapacity = oldCapacity + (oldCapacity >> 1); 这行语句使用位运算，将原数组的 oldCapacity 二进制位向右移动一位，即原数的一半与 oldCapacity 求和作为 newCapacity 的值，每次扩容 newCapacity 大约是 oldCapacity 的 1.5 倍

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩大为大约 1.5 倍
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

trimToSize

创建一个刚好能包括所有元素的数组并拷贝过去

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

indexOf

// 正向查找返回第一个与之相等的索引
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

lastIndexOf

// 逆向查找返回第一个与之相等的索引
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

elementData

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

get

// 根据索引查找元素
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

set

// 根据索引直接赋值
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

add

// 直接在末尾添加
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

// 在相应索引处添加
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

fastRemove

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

remove

// 调用 fastRemove() 根据索引删除
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

// 同样调用 fastRemove() 删除指定元素的第一个匹配项
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

addAll

// 直接在末尾添加添加集合中所有元素
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

// 在相应索引处添加集合中所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

removeAll

// 移除所有元素
public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

Vector

Vector 继承了 AbstractList 抽象基类，实现了 List 接口

类似于 ArrayList，但其是同步的，线程安全，如果不需要线程安全，建议使用 ArrayList 代替 Vector

但也不是绝对的线程安全：

private static Vector<Integer> vector = new Vector<>();
 
public static void main(String args[]) throws Excption{
    while(true){
        for(int i=0; i<10; i++){
            vector.add(i);
        }
        Thread removeT = new Thread(new Runnable() {
            @Override
            public void run() {
                for(int i=0; i<vector.size(); i++){
                    vector.remove(i); // 移除 i 位置的元素
                }
            }
        });
        Thread getT = new Thread(new Runnable() {
            @Override
            public void run() {
                for(int i=0; i<vector.size(); i++){
                    System.out.println(vector.get(i)); // 获取 i 位置的元素
                }
            }
        });
        getT.start();
        removeT.start();
        while(Thread.activeCount()>20);
    }
}

如上代码，如果第一个线程在第二个线程之前把 i 位置上的元素移除了，由于第二个线程的 i 已经确定，如果此时的 i 正好是数组的最后一位， get() 方法二次获取就会发生数组下标越界的异常

构造器

构造器	描述
Vector()	构造一个空向量，使其内部数据数组的大小为 10 ，其标准容量增量为零。
Vector(int initialCapacity)	构造一个具有指定初始容量且容量增量等于零的空向量。
Vector(int initialCapacity, int capacityIncrement)	构造具有指定初始容量和容量增量的空向量。
Vector(Collection<? extends E> c)	按照集合的迭代器返回的顺序构造一个包含指定集合元素的向量。

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}

方法概要

变量和类型	方法	描述
void	add(int index, E element)	将指定元素插入此Vector中的指定位置。
boolean	add(E e)	将指定的元素追加到此Vector的末尾。
boolean	addAll(int index, Collection<? extends E> c)	将指定Collection中的所有元素插入到此Vector中的指定位置。
boolean	addAll(Collection<? extends E> c)	将指定Collection中的所有元素追加到此Vector的末尾，按照指定Collection的Iterator返回的顺序。
void	addElement(E obj)	将指定的组件添加到此向量的末尾，将其大小增加1。
int	capacity()	返回此向量的当前容量。
void	clear()	从此Vector中删除所有元素。
Object	clone()	返回此向量的副本。
boolean	contains(Object o)	如果此向量包含指定的元素，则返回 true 。
boolean	containsAll(Collection<?> c)	如果此Vector包含指定Collection中的所有元素，则返回true。
void	copyInto(Object[] anArray)	将此向量的组件复制到指定的数组中。
E	elementAt(int index)	返回指定索引处的组件。
Enumeration	elements()	返回此向量的组件的枚举。
void	ensureCapacity(int minCapacity)	如有必要，增加此向量的容量，以确保它至少可以容纳由minimum capacity参数指定的组件数。
boolean	equals(Object o)	将指定的Object与此Vector进行比较以获得相等性。
E	firstElement()	返回此向量的第一个组件（索引 0处的项）。
void	forEach(Consumer<? super E> action)	对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常。
E	get(int index)	返回此Vector中指定位置的元素。
int	hashCode()	返回此Vector的哈希码值。
int	indexOf(Object o)	返回此向量中第一次出现的指定元素的索引，如果此向量不包含该元素，则返回-1。
int	indexOf(Object o, int index)	返回此向量中第一次出现的指定元素的索引，从 index向前搜索，如果找不到该元素，则返回-1。
void	insertElementAt(E obj, int index)	将指定对象作为此向量中的组件插入指定的 index 。
boolean	isEmpty()	测试此向量是否没有组件。
Iterator	iterator()	以适当的顺序返回此列表中元素的迭代器。
E	lastElement()	返回向量的最后一个组件。
int	lastIndexOf(Object o)	返回此向量中指定元素最后一次出现的索引，如果此向量不包含该元素，则返回-1。
int	lastIndexOf(Object o, int index)	返回此向量中最后一次出现的指定元素的索引，从 index向后搜索，如果找不到该元素，则返回-1。
ListIterator	listIterator()	返回此列表中元素的列表迭代器（按适当顺序）。
ListIterator	listIterator(int index)	从列表中的指定位置开始，返回列表中元素的列表迭代器（按正确顺序）。
E	remove(int index)	删除此Vector中指定位置的元素。
boolean	remove(Object o)	删除此向量中第一次出现的指定元素如果向量不包含该元素，则不会更改。
boolean	removeAll(Collection<?> c)	从此Vector中删除指定Collection中包含的所有元素。
void	removeAllElements()	从此向量中移除所有组件并将其大小设置为零。
boolean	removeElement(Object obj)	从此向量中移除参数的第一个（索引最低）事件。
void	removeElementAt(int index)	删除指定索引处的组件。
boolean	removeIf(Predicate<? super E> filter)	删除此集合中满足给定谓词的所有元素。
protected void	removeRange(int fromIndex, int toIndex)	从此列表中删除索引介于 fromIndex （含）和 toIndex （独占）之间的所有元素。
void	replaceAll(UnaryOperator operator)	将该列表的每个元素替换为将运算符应用于该元素的结果。
boolean	retainAll(Collection<?> c)	仅保留此Vector中包含在指定Collection中的元素。
E	set(int index, E element)	用指定的元素替换此Vector中指定位置的元素。
void	setElementAt(E obj, int index)	将此向量的指定 index处的组件设置为指定对象。
void	setSize(int newSize)	设置此向量的大小。
int	size()	返回此向量中的组件数。
Spliterator	spliterator()	在此列表中的元素上创建 late-binding 和失败快速 Spliterator 。
List	subList(int fromIndex, int toIndex)	返回此List的部分在fromIndex（包含）和toIndex（独占）之间的视图。
Object[]	toArray()	以正确的顺序返回包含此Vector中所有元素的数组。
T[]	toArray(T[] a)	以正确的顺序返回包含此Vector中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。
String	toString()	返回此Vector的字符串表示形式，包含每个元素的String表示形式。
void	trimToSize()	修剪此向量的容量为向量的当前大小。

LinkedList

LinkedList 继承了 AbstractSequentialList 抽象基类，实现了 List 和 Deque 接口

基于双向链表实现，只能通过顺序访问，可以快速地在链表中间插入和删除元素

对 List 和 Deque 接口的实现使得 LinkedList 可以看作一个顺序容器，也可以看作一个栈或者队列，如果需要用到栈或者队列可以考虑 LinkedList，不过一般优先考虑的是 ArrayDeque，它比 LinkedList 作为栈或队列使用时具有更好的性能

底层数据结构

transient int size = 0; // 长度

transient Node<E> first; // 头指针

transient Node<E> last; // 尾指针

Node 作为内部私有类：

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()	构造一个空列表。
LinkedList(Collection<? extends E> c)	按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

// 空 list
public LinkedList() {
}

// 通过一个 Collection 集合进行赋值
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

方法概要

变量和类型	方法	描述
void	add(int index, E element)	将指定元素插入此列表中的指定位置。
boolean	add(E e)	将指定的元素追加到此列表的末尾。
boolean	addAll(int index, Collection<? extends E> c)	从指定位置开始，将指定集合中的所有元素插入此列表。
boolean	addAll(Collection<? extends E> c)	将指定集合中的所有元素按指定集合的迭代器返回的顺序附加到此列表的末尾。
void	addFirst(E e)	在此列表的开头插入指定的元素。
void	addLast(E e)	将指定的元素追加到此列表的末尾。
void	clear()	从此列表中删除所有元素。
Object	clone()	返回此 LinkedList的浅表副本。
boolean	contains(Object o)	如果此列表包含指定的元素，则返回 true 。
Iterator	descendingIterator()	以相反的顺序返回此双端队列中元素的迭代器。
E	element()	检索但不删除此列表的头部（第一个元素）。
E	get(int index)	返回此列表中指定位置的元素。
E	getFirst()	返回此列表中的第一个元素。
E	getLast()	返回此列表中的最后一个元素。
int	indexOf(Object o)	返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
int	lastIndexOf(Object o)	返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
ListIterator	listIterator(int index)	从列表中的指定位置开始，返回此列表中元素的列表迭代器（按正确顺序）。
boolean	offer(E e)	将指定的元素添加为此列表的尾部（最后一个元素）。
boolean	offerFirst(E e)	在此列表的前面插入指定的元素。
boolean	offerLast(E e)	在此列表的末尾插入指定的元素。
E	peek()	检索但不删除此列表的头部（第一个元素）。
E	peekFirst()	检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。
E	peekLast()	检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。
E	poll()	检索并删除此列表的头部（第一个元素）。
E	pollFirst()	检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。
E	pollLast()	检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。
E	pop()	弹出此列表所代表的堆栈中的元素。
void	push(E e)	将元素推送到此列表所表示的堆栈上。
E	remove()	检索并删除此列表的头部（第一个元素）。
E	remove(int index)	删除此列表中指定位置的元素。
boolean	remove(Object o)	从该列表中删除指定元素的第一个匹配项（如果存在）。
E	removeFirst()	从此列表中删除并返回第一个元素。
boolean	removeFirstOccurrence(Object o)	删除此列表中第一次出现的指定元素（从头到尾遍历列表时）。
E	removeLast()	从此列表中删除并返回最后一个元素。
boolean	removeLastOccurrence(Object o)	删除此列表中最后一次出现的指定元素（从头到尾遍历列表时）。
E	set(int index, E element)	用指定的元素替换此列表中指定位置的元素。
int	size()	返回此列表中的元素数。
Spliterator	spliterator()	在此列表中的元素上创建 late-binding 和故障快速 Spliterator 。
Object[]	toArray()	以适当的顺序（从第一个元素到最后一个元素）返回包含此列表中所有元素的数组。
T[]	toArray(T[] a)	以适当的顺序返回包含此列表中所有元素的数组（从第一个元素到最后一个元素）; 返回数组的运行时类型是指定数组的运行时类型。

getFirst

// 取链表头部的元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

getLast

// 取链表尾部的元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

unlinkFirst

// 首元素断链
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

unlinkLast

// 尾元素断链
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

unlink

// 断链
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) { // 如果是头节点
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) { // 如果是尾节点
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

removeFirst

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

removeLast

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

linkFirst

// 首元素建立连接
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

linkLast

// 尾元素建立连接
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

linkBefore

// 插入在某节点前面
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; // 保存插入位置的前驱
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode; // 插入位置的前驱改为新节点
    if (pred == null)
        first = newNode; // 插入位置为 0 
    else
        pred.next = newNode; 插入位置前驱的后继赋值
    size++;
    modCount++;
}

node

// 查找相应索引的节点
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) { // 根据索引大小决定从头还是尾进行查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

addFirst

public void addFirst(E e) {
	linkFirst(e);
}

addLast

public void addLast(E e) {
	linkLast(e);
}

add

有两个方法，一个是直接在末尾插入元素，还一个是在指定索引下插入元素

// 直接在末尾插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在指定索引下插入元素
public void add(int index, E element) {
    checkPositionIndex(index); // index >= 0 && index <= size

    if (index == size) // 插入链表的索引在末尾
        linkLast(element);
    else
        linkBefore(element, node(index)); // 通过 index 找到要插入的位置
}

remove

两种实现方法，一种是直接移除链表头部元素，还一种是移除指定索引的元素

// 移除链表头部元素
public E remove() {
    return removeFirst();
}

// 移除指定索引元素
public E remove(int index) {
    checkElementIndex(index); // index >= 0 && index < size
    return unlink(node(index));
}

// 移除第一个出现的指定元素
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

addAll

直接一次性把一堆元素添加在指定索引位置

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

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // index >= 0 && index <= size

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) { // 插入位置在末尾
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        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;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) { // 如果插入位置是末尾
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew; // 更新大小
    modCount++;
    return true;
}

get

// 取 index 位置的元素
public E get(int index) {
    checkElementIndex(index); // index >= 0 && index < size
    return node(index).item;
}

set

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

indexOf

// 从前往后查找第一个与之相等的数
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

lastIndexOf

// 从后往前查找第一个与之相等的数
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

peek

// 返回第一个元素
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

element

// 返回第一个元素
public E element() {
    return getFirst();
}

poll

// 返回并删除第一个元素
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

offer

// 添加元素
public boolean offer(E e) {
    return add(e);
}

offerFirst

// 添加元素到链表头部
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

offerLast

// 添加元素到链表尾部
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

peekFirst

// 返回首元素
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

peekLast

// 返回尾元素
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

pollFirst

// 删除首元素
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

pollLast

// 删除尾元素
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

push

// 压入栈顶
public void push(E e) {
    addFirst(e);
}

pop

// 移除栈顶元素
public E pop() {
    return removeFirst();
}

removeFirstOccurrence

// 移除第一个相同的元素
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

removeLastOccurrence

// 移除最后一个相同的元素
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Set

TreeSet

基于红黑树实现，支持有序性操作，例如根据一个范围查找元素

查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 为 O(logN)

TreeSet 的底层实际是 TreeMap 的套壳，使用 TreeMap 的 key 来存储元素

底层数据结构

private transient NavigableMap<E,Object> m; // 实则 Map 的套壳

构造器

构造器	描述
TreeSet()	构造一个新的空树集，根据其元素的自然顺序进行排序。
TreeSet(Collection<? extends E> c)	构造一个新的树集，其中包含指定集合中的元素，并根据其元素的 自然顺序进行排序 。
TreeSet(Comparator<? super E> comparator)	构造一个新的空树集，根据指定的比较器进行排序。
TreeSet(SortedSet s)	构造一个包含相同元素并使用与指定有序集相同排序的新树集。

// 底层 Map
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

// 以自然排序的方式创建一个新的 TreeMap，根据该 TreeMap 创建一个 TreeSet，使用 TreeMap 的 key 来保存 Set 集合中的元素
public TreeSet() {
    this(new TreeMap<>());
}

// 以自定义排序的方式创建一个新的 TreeMap，根据该 TreeMap 创建一个 TreeSet，使用 TreeMap 的 key 来保存 Set 集合中的元素
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

// 先调用无参构造器，以自然排序的方式创建一个 TreeSet，再通过 addAll 方法赋值
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

// 先调用自定义排序构造器，以自定义排序的方式创建一个 TreeSet，再通过 addAll 方法赋值
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

方法概要

变量和类型	方法	描述
boolean	add(E e)	如果指定的元素尚不存在，则将其添加到此集合中。
boolean	addAll(Collection<? extends E> c)	将指定集合中的所有元素添加到此集合中。
E	ceiling(E e)	返回此set中大于或等于给定元素的 null元素，如果没有这样的元素，则 null 。
void	clear()	从该集中删除所有元素。
Object	clone()	返回此 TreeSet实例的浅表副本。
boolean	contains(Object o)	如果此set包含指定的元素，则返回 true 。
Iterator	descendingIterator()	以降序返回此集合中元素的迭代器。
NavigableSet	descendingSet()	返回此set中包含的元素的逆序视图。
E	first()	返回此集合中当前的第一个（最低）元素。
E	floor(E e)	返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则 null 。
SortedSet	headSet(E toElement)	返回此set的部分视图，其元素严格小于 toElement 。
NavigableSet	headSet(E toElement, boolean inclusive)	返回此set的部分视图，其元素小于（或等于，如果 inclusive为true） toElement 。
E	higher(E e)	返回此集合中的最小元素严格大于给定元素，如果没有这样的元素，则 null 。
boolean	isEmpty()	如果此集合不包含任何元素，则返回 true 。
Iterator	iterator()	以升序返回此集合中元素的迭代器。
E	last()	返回此集合中当前的最后一个（最高）元素。
E	lower(E e)	返回此集合中的最大元素严格小于给定元素，如果没有这样的元素，则 null 。
E	pollFirst()	检索并删除第一个（最低）元素，如果此组为空，则返回 null 。
E	pollLast()	检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 。
boolean	remove(Object o)	如果存在，则从该集合中移除指定的元素。
int	size()	返回此集合中的元素数（基数）。
Spliterator	spliterator()	在此集合中的元素上创建 late-binding 和故障快速 Spliterator 。
NavigableSet	subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	返回此set的部分视图，其元素范围为 fromElement到 toElement 。
SortedSet	subSet(E fromElement, E toElement)	返回此set的部分视图，其元素范围从 fromElement （含）到 toElement （独占）。
SortedSet	tailSet(E fromElement)	返回此set的部分视图，其元素大于或等于 fromElement 。
NavigableSet	tailSet(E fromElement, boolean inclusive)	返回此set的部分视图，其元素大于（或等于，如果 inclusive为true） fromElement 。

具体方法在后文的 TreeMap 中介绍

HashSet

基于哈希表实现，支持快速查找，但不支持有序性操作。

失去了元素的插入顺序信息，使用 Iterator 遍历 HashSet 得到的结果是不确定的

HashSet 的底层实际是 HashMap 的套壳，使用 HashMap 的 key 来存储元素

底层数据结构

private transient HashMap<E,Object> map;

构造器

构造器	描述
HashSet()	构造一个新的空集; 支持HashMap实例具有默认初始容量（16）和加载因子（0.75）。
HashSet(int initialCapacity)	构造一个新的空集; 支持HashMap实例具有指定的初始容量和默认加载因子（0.75）。
HashSet(int initialCapacity, float loadFactor)	构造一个新的空集; 支持HashMap实例具有指定的初始容量和指定的加载因子。
HashSet(Collection<? extends E> c)	构造一个包含指定集合中元素的新集合。

// 实例化 HashMap
public HashSet() {
    map = new HashMap<>();
}

// 实例化并赋值
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

// 初始化 HashMap
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

// 初始化 HashMap
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 初始化 HashMap
//  不对外公开的构造方法，default修饰，实际上是提供给LinkedHashSet使用
//  dummy 参数无实际意义，仅作标识作用（为了和前面第三个构造方法进行区分）
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

方法概要

变量和类型	方法	描述
boolean	add(E e)	如果指定的元素尚不存在，则将其添加到此集合中。
void	clear()	从该集中删除所有元素。
Object	clone()	返回此 HashSet实例的浅表副本：未克隆元素本身。
boolean	contains(Object o)	如果此set包含指定的元素，则返回 true 。
boolean	isEmpty()	如果此集合不包含任何元素，则返回 true 。
Iterator	iterator()	返回此set中元素的迭代器。
boolean	remove(Object o)	如果存在，则从该集合中移除指定的元素。
int	size()	返回此集合中的元素数（基数）。
Spliterator	spliterator()	在此集合中的元素上创建 late-binding 和失败快速 Spliterator 。

具体方法在后文的 HashMap 中介绍

LinkedHashSet

基于双向链表实现，只能顺序访问，可以快速地在链表中间插入和删除元素

LinkedList 还可以用作栈、队列和双向队列

LinkedHashSet 的底层实际是 LinkedHashMap 的套壳，使用 LinkedHashMap 的 key 来存储元素

构造器

构造器	描述
LinkedHashSet()	使用默认初始容量（16）和加载因子（0.75）构造一个新的空链接哈希集。
LinkedHashSet(int initialCapacity)	使用指定的初始容量和默认加载因子（0.75）构造一个新的空链接哈希集。
LinkedHashSet(int initialCapacity, float loadFactor)	使用指定的初始容量和加载因子构造一个新的空链接哈希集。
LinkedHashSet(Collection<? extends E> c)	构造一个新的链接哈希集，其具有与指定集合相同的元素。

// 构造方法全部都是调用Hashset的构造方法
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

方法概要

变量和类型	方法	描述
Spliterator	spliterator()	在此集合中的元素上创建 late-binding 和失败快速 Spliterator 。

具体方法在后文的 LinkedHashMap 中介绍

Stack && Queue

Java 中有个叫做 Stack 的类，没有叫做 Queue 的类，只有叫做 Queue 的接口，Stack 类官方已经不推荐使用，所以如果要选择实现栈与队列，优先考虑效率更高的 ArrayDeque（次选是 LinkedList）

ArrayDeque

底层通过数组实现，为了满足同时在数组两端插入或删除，该数组也是循环数组，数组的任何一点都可能被看作头或者尾

ArrayDeque 是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步

该容器不允许放入 null 元素。

head 指向循环数组的第一个有效元素，tail 指向第一个可以插入元素的空位

底层数据结构

transient Object[] elements;

transient int head;

transient int tail;

构造器

构造器	描述
ArrayDeque()	构造一个空数组deque，其初始容量足以容纳16个元素。
ArrayDeque(int numElements)	构造一个空数组deque，其初始容量足以容纳指定数量的元素。
ArrayDeque(Collection<? extends E> c)	按照集合的迭代器返回的顺序构造一个包含指定集合元素的双端队列。

// 空构造器
public ArrayDeque() {
    elements = new Object[16];
}

// 构造一个指定大小的数组
public ArrayDeque(int numElements) {
    elements =
        new Object[(numElements < 1) ? 1 :
                   (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                   numElements + 1];
}

// 构造一个包含 Collection 集合所有元素的数组
public ArrayDeque(Collection<? extends E> c) {
    this(c.size());
    copyElements(c);
}

private void copyElements(Collection<? extends E> c) {
    c.forEach(this::addLast);
}

方法概要

变量和类型	方法	描述
boolean	add(E e)	在此双端队列的末尾插入指定的元素。
boolean	addAll(Collection<? extends E> c)	在此双端队列的末尾添加指定集合中的所有元素，就好像通过在每个双 端子上调用 addLast(E)一样 ，按照集合的迭代器返回它们的顺序。
void	addFirst(E e)	在此双端队列的前面插入指定的元素。
void	addLast(E e)	在此双端队列的末尾插入指定的元素。
void	clear()	从此双端队列中删除所有元素。
ArrayDeque	clone()	返回此双端队列的副本。
boolean	contains(Object o)	如果此双端队列包含指定的元素，则返回 true 。
E	element()	检索但不删除此双端队列表示的队列的头部。
void	forEach(Consumer<? super E> action)	对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常。
E	getFirst()	检索但不删除此双端队列的第一个元素。
E	getLast()	检索但不删除此双端队列的最后一个元素。
boolean	isEmpty()	如果此双端队列不包含任何元素，则返回 true 。
Iterator	iterator()	返回此双端队列中元素的迭代器。
boolean	offer(E e)	在此双端队列的末尾插入指定的元素。
boolean	offerFirst(E e)	在此双端队列的前面插入指定的元素。
boolean	offerLast(E e)	在此双端队列的末尾插入指定的元素。
E	peek()	检索但不删除此双端队列表示的队列的头部，如果此双端队列为空，则返回 null 。
E	poll()	检索并删除此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素），如果此双端队列为空，则返回 null 。
E	pop()	从此双端队列表示的堆栈中弹出一个元素。
void	push(E e)	将元素推送到此双端队列表示的堆栈上。
E	remove()	检索并删除此双端队列表示的队列的头部。
boolean	remove(Object o)	从此双端队列中删除指定元素的单个实例。
boolean	removeAll(Collection<?> c)	删除此集合的所有元素，这些元素也包含在指定的集合中（可选操作）。
E	removeFirst()	检索并删除此双端队列的第一个元素。
boolean	removeFirstOccurrence(Object o)	删除此双端队列中第一次出现的指定元素（从头到尾遍历双端队列时）。
boolean	removeIf(Predicate<? super E> filter)	删除此集合中满足给定谓词的所有元素。
E	removeLast()	检索并删除此双端队列的最后一个元素。
boolean	removeLastOccurrence(Object o)	删除此双端队列中最后一次出现的指定元素（从头到尾遍历双端队列时）。
boolean	retainAll(Collection<?> c)	仅保留此集合中包含在指定集合中的元素（可选操作）。
int	size()	返回此双端队列中的元素数。
Spliterator	spliterator()	在此双端队列中的元素上创建late-binding和失败快速 Spliterator 。
Object[]	toArray()	以适当的顺序（从第一个元素到最后一个元素）返回一个包含此双端队列中所有元素的数组。
T[]	toArray(T[] a)	以适当的顺序（从第一个元素到最后一个元素）返回一个包含此双端队列中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。

扩容函数

private void grow(int needed) {
    final int oldCapacity = elements.length;
    int newCapacity;
    // 如果容量小于 64，则扩大为双倍 + 2，否则扩大为 1.5 倍
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
    if (jump < needed
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
        newCapacity = newCapacity(needed, jump);
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
    if (tail < head || (tail == head && es[head] != null)) {
        int newSpace = newCapacity - oldCapacity;
        // 将头部元素拷贝到数组尾部，并将空间置为 null
        System.arraycopy(es, head,
                         es, head + newSpace,
                         oldCapacity - head);
        for (int i = head, to = (head += newSpace); i < to; i++)
            es[i] = null;
    }
}

private int newCapacity(int needed, int jump) {
    final int oldCapacity = elements.length, minCapacity;
    if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
        if (minCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        return Integer.MAX_VALUE;
    }
    if (needed > jump)
        return minCapacity;
    return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
        ? oldCapacity + jump
        : MAX_ARRAY_SIZE;
}

dec

// 计算循环索引，维持双端数组
static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;
    return i;
}

inc

// 计算循环索引，维持双端数组
static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;
    return i;
}

addFirst

// 将元素插入数组头部
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e; // 计算循环索引，--head
    if (head == tail)
        grow(1); // 扩容
}

addLast

// 将元素插入数组尾部
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[tail] = e;
    if (head == (tail = inc(tail, es.length))) // 计算循环索引，++tail
        grow(1);
}

addAll

将集合中的所有元素插入 ArrayDeque 的尾部

public boolean addAll(Collection<? extends E> c) {
    final int s, needed;
    if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
        grow(needed);
    copyElements(c);
    return size() > s;
}

private void copyElements(Collection<? extends E> c) {
    c.forEach(this::addLast);
}

offerFirst

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

offerLast

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

removeFirst

public E removeFirst() {
    E e = pollFirst();
    if (e == null)
        throw new NoSuchElementException();
    return e;
}

removeLast

public E removeLast() {
    E e = pollLast();
    if (e == null)
        throw new NoSuchElementException();
    return e;
}

pollFirst

public E pollFirst() {
    final Object[] es;
    final int h;
    E e = elementAt(es = elements, h = head);
    if (e != null) {
        es[h] = null;
        head = inc(h, es.length);
    }
    return e; // 返回并删除
}

pollLast

public E pollLast() {
    final Object[] es;
    final int t;
    E e = elementAt(es = elements, t = dec(tail, es.length));
    if (e != null)
        es[tail = t] = null;
    return e;
}

getFirst

public E getFirst() {
    E e = elementAt(elements, head);
    if (e == null)
        throw new NoSuchElementException();
    return e;
}

static final <E> E elementAt(Object[] es, int i) {
	return (E) es[i];
}

getLast

public E getLast() {
    final Object[] es = elements;
    E e = elementAt(es, dec(tail, es.length));
    if (e == null)
        throw new NoSuchElementException();
    return e;
}

static final <E> E elementAt(Object[] es, int i) {
	return (E) es[i];
}

peekFirst

// 取队首
public E peekFirst() {
    return elementAt(elements, head);
}

static final <E> E elementAt(Object[] es, int i) {
	return (E) es[i];
}

peekLast

public E peekLast() {
    final Object[] es;
    return elementAt(es = elements, dec(tail, es.length));
}

static final <E> E elementAt(Object[] es, int i) {
	return (E) es[i];
}

delete

// 数组拷贝进行删除
boolean delete(int i) {
    final Object[] es = elements;
    final int capacity = es.length;
    final int h, t;
    // number of elements before to-be-deleted elt
    final int front = sub(i, h = head, capacity);
    // number of elements after to-be-deleted elt
    final int back = sub(t = tail, i, capacity) - 1;
    if (front < back) {
        // move front elements forwards
        if (h <= i) {
            System.arraycopy(es, h, es, h + 1, front);
        } else { // Wrap around
            System.arraycopy(es, 0, es, 1, i);
            es[0] = es[capacity - 1];
            System.arraycopy(es, h, es, h + 1, front - (i + 1));
        }
        es[h] = null;
        head = inc(h, capacity);
        return false;
    } else {
        // move back elements backwards
        tail = dec(t, capacity);
        if (i <= tail) {
            System.arraycopy(es, i + 1, es, i, back);
        } else { // Wrap around
            System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
            es[capacity - 1] = es[0];
            System.arraycopy(es, 1, es, 0, t - 1);
        }
        es[tail] = null;
        return true;
    }
}

removeFirstOccurrence

public boolean removeFirstOccurrence(Object o) {
    if (o != null) {
        final Object[] es = elements;
        for (int i = head, end = tail, to = (i <= end) ? end : es.length;
             ; i = 0, to = end) {
            for (; i < to; i++)
                if (o.equals(es[i])) {
                    delete(i);
                    return true;
                }
            if (to == end) break;
        }
    }
    return false;
}

removeLastOccurrence

public boolean removeLastOccurrence(Object o) {
    if (o != null) {
        final Object[] es = elements;
        for (int i = tail, end = head, to = (i >= end) ? end : 0;
             ; i = es.length, to = end) {
            for (i--; i > to - 1; i--)
                if (o.equals(es[i])) {
                    delete(i);
                    return true;
                }
            if (to == end) break;
        }
    }
    return false;
}

add

将元素插入到 ArrayDeque 的尾部

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

offer

public boolean offer(E e) {
    return offerLast(e);
}

remove

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

poll

public E poll() {
    return pollFirst();
}

element

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

peek

public E peek() {
    return peekFirst();
}

push

public void push(E e) {
    addFirst(e);
}

pop

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

PriorityDeque

基于堆结构实现，可完成优先队列的操作

Java 中的优先队列保证每次取最小元素，基于小根堆实现，而 C++ 则是基于大根堆实现，默认返回最大元素，不过都可以根据需要自定义比较器在构造时传入，按需求进行返回

PriorityDeque 实现了 AbstractQueue 抽象基类，间接实现了 Queue 接口，不允许放入 null

底层通过数组实现的小根堆

底层数据结构

transient Object[] queue;

构造器

构造器	描述
PriorityQueue()	使用默认初始容量（11）创建PriorityQueue ，根据其 natural ordering 对其元素进行排序。
PriorityQueue(int initialCapacity)	创建具有指定初始容量的PriorityQueue ，该容量根据其 natural ordering 对其元素进行排序。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)	创建具有指定初始容量的 PriorityQueue ，该容量根据指定的比较器对其元素进行排序。
PriorityQueue(Collection<? extends E> c)	创建包含指定集合中的元素的 PriorityQueue 。
PriorityQueue(Comparator<? super E> comparator)	创建具有默认初始容量的 PriorityQueue ，其元素根据指定的比较器进行排序。
PriorityQueue(PriorityQueue<? extends E> c)	创建包含指定优先级队列中的元素的 PriorityQueue 。
PriorityQueue(SortedSet<? extends E> c)	创建一个 PriorityQueue其中包含指定有序集合中的元素。

// 构造默认大小的 PriorityQueue
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 构造指定大小的 PriorityQueue
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

// 构造自定义比较器的 PriorityQueue
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

// 构造指定大小，自定义比较器的 PriorityQueue
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

// 构造指定集合元素的 PriorityQueue
public PriorityQueue(Collection<? extends E> c) {
	// 排序集合
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    // 优先队列
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

// 通过优先队列构造优先队列
public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}

// 通过排序集合构造优先队列
public PriorityQueue(SortedSet<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

// 初始化
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = ensureNonEmpty(c.toArray());
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}

// 初始化
private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] es = c.toArray();
    int len = es.length;
    if (c.getClass() != ArrayList.class)
        es = Arrays.copyOf(es, len, Object[].class);
    if (len == 1 || this.comparator != null)
        for (Object e : es)
            if (e == null)
                throw new NullPointerException();
    this.queue = ensureNonEmpty(es);
    this.size = len;
}

方法概要

变量和类型	方法	描述
boolean	add(E e)	将指定的元素插入此优先级队列。
void	clear()	从此优先级队列中删除所有元素。
Comparator<? super E>	comparator()	返回用于为了在这个队列中的元素，或比较null如果此队列根据所述排序 natural ordering 的元素。
boolean	contains(Object o)	如果此队列包含指定的元素，则返回 true 。
void	forEach(Consumer<? super E> action)	对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常。
Iterator	iterator()	返回此队列中元素的迭代器。
boolean	offer(E e)	将指定的元素插入此优先级队列。
boolean	remove(Object o)	从此队列中删除指定元素的单个实例（如果存在）。
boolean	removeAll(Collection<?> c)	删除此集合的所有元素，这些元素也包含在指定的集合中（可选操作）。
boolean	removeIf(Predicate<? super E> filter)	删除此集合中满足给定谓词的所有元素。
boolean	retainAll(Collection<?> c)	仅保留此集合中包含在指定集合中的元素（可选操作）。
Spliterator	spliterator()	在此队列中的元素上创建 late-binding 和故障快速 Spliterator 。
Object[]	toArray()	返回包含此队列中所有元素的数组。
T[]	toArray(T[] a)	返回包含此队列中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。

扩容函数

// 创建一个更大的数组然后复制
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

siftUp

// 上浮函数
// 新插入的元素通过比较器不断比较当前点的 parent 找到相应的位置
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

// 有自定义比较器
private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}

// 无自定义比较器
private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

siftDown

// 下沉函数
// 返回根元素，末尾元素赋给根元素，数组长度减一，根元素不断下沉直至找到对应位置
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x, queue, size, comparator);
    else
        siftDownComparable(k, x, queue, size);
}

private static <T> void siftDownUsingComparator(
    int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
    // assert n > 0;
    int half = n >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = es[child];
        int right = child + 1;
        if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
            c = es[child = right];
        if (cmp.compare(x, (T) c) <= 0)
            break;
        es[k] = c;
        k = child;
    }
    es[k] = x;
}

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    // assert n > 0;
    Comparable<? super T> key = (Comparable<? super T>)x;
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        if (right < n &&
            ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
            c = es[child = right];
        if (key.compareTo((T) c) <= 0)
            break;
        es[k] = c;
        k = child;
    }
    es[k] = key;
}

add

public boolean add(E e) {
    return offer(e);
}

offer

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}

peek

public E peek() {
    return (E) queue[0];
}

indexOf

// 私有函数
private int indexOf(Object o) {
    if (o != null) {
        final Object[] es = queue;
        for (int i = 0, n = size; i < n; i++)
            if (o.equals(es[i]))
                return i;
    }
    return -1;
}

removeAt

// 移除相应索引的元素
E removeAt(int i) {
    // assert i >= 0 && i < size;
    final Object[] es = queue;
    modCount++;
    int s = --size;
    if (s == i) // 移除最后一个元素
        es[i] = null;
    else {
        E moved = (E) es[s];
        es[s] = null;
        siftDown(i, moved);
        if (es[i] == moved) {
            siftUp(i, moved);
            if (es[i] != moved)
                return moved;
        }
    }
    return null;
}

remove

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

removeEq

void removeEq(Object o) {
    final Object[] es = queue;
    for (int i = 0, n = size; i < n; i++) {
        if (o == es[i]) {
            removeAt(i);
            break;
        }
    }
}

poll

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

Map 容器

结构图

Map

TreeMap

基于红黑树实现，时间复杂度为 O(lgn)

出于性能原因，TreeMap 是非同步的

实现 AbstractMap 抽象基类，间接实现 Map 接口

底层数据结构

private transient Entry<K,V> root;

private transient int size = 0;

private transient int modCount = 0;

构造器

构造器	描述
TreeMap()	使用其键的自然顺序构造一个新的空树图。
TreeMap(Comparator<? super K> comparator)	构造一个新的空树图，根据给定的比较器排序。
TreeMap(Map<? extends K,? extends V> m)	构造一个新的树映射，其中包含与给定映射相同的映射，根据其键的 自然顺序排序 。
TreeMap(SortedMap<K,? extends V> m)	构造一个包含相同映射的新树映射，并使用与指定有序映射相同的顺序。

public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
    }
}

方法概要

变量和类型	方法	描述
Map.Entry<K,V>	ceilingEntry(K key)	返回与大于或等于给定键的最小键关联的键 - 值映射，如果没有此键，则 null 。
K	ceilingKey(K key)	返回大于或等于给定键的 null键，如果没有这样的键，则 null 。
void	clear()	从此映射中删除所有映射。
Object	clone()	返回此 TreeMap实例的浅表副本。
boolean	containsKey(Object key)	如果此映射包含指定键的映射，则返回 true 。
boolean	containsValue(Object value)	如果此映射将一个或多个键映射到指定值，则返回 true 。
NavigableSet	descendingKeySet()	返回此映射中包含的键的反向顺序 NavigableSet 视图。
NavigableMap<K,V>	descendingMap()	返回此映射中包含的映射的逆序视图。
Set<Map.Entry<K,V>>	entrySet()	返回此映射中包含的映射的 Set 视图。
Map.Entry<K,V>	firstEntry()	返回与此映射中的最小键关联的键 - 值映射，如果映射为空，则 null 。
K	firstKey()	返回此映射中当前的第一个（最低）键。
Map.Entry<K,V>	floorEntry(K key)	返回与小于或等于给定键的最大键关联的键 - 值映射，如果没有此键，则 null 。
K	floorKey(K key)	返回小于或等于给定键的最大键，如果没有这样的键，则 null 。
V	get(Object key)	返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
SortedMap<K,V>	headMap(K toKey)	返回此映射的部分视图，其键严格小于 toKey 。
NavigableMap<K,V>	headMap(K toKey, boolean inclusive)	返回此映射的部分视图，其键小于（或等于，如果 inclusive为真） toKey 。
Map.Entry<K,V>	higherEntry(K key)	返回与严格大于给定键的最小键关联的键 - 值映射，如果没有此键，则 null 。
K	higherKey(K key)	返回严格大于给定键的最小键，如果没有这样的键，则返回 null 。
Set	keySet()	返回此映射中包含的键的 Set 视图。
Map.Entry<K,V>	lastEntry()	返回与此映射中的最大键关联的键 - 值映射，如果映射为空，则 null 。
K	lastKey()	返回此映射中当前的最后一个（最高）键。
Map.Entry<K,V>	lowerEntry(K key)	返回与严格小于给定键的最大键相关联的键 - 值映射，如果没有这样的键，则 null 。
K	lowerKey(K key)	返回严格小于给定键的最大键，如果没有这样键，则返回 null 。
NavigableSet	navigableKeySet()	返回此映射中包含的键的 NavigableSet视图。
Map.Entry<K,V>	pollFirstEntry()	删除并返回与此映射中的最小键关联的键 - 值映射，如果映射为空，则 null 。
Map.Entry<K,V>	pollLastEntry()	删除并返回与此映射中的最大键关联的键 - 值映射，如果映射为空，则 null 。
V	put(K key, V value)	将指定的值与此映射中的指定键相关联。
void	putAll(Map<? extends K,? extends V> map)	将指定映射中的所有映射复制到此映射。
V	remove(Object key)	如果存在，则从此TreeMap中删除此键的映射。
int	size()	返回此映射中键 - 值映射的数量。
NavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	返回此映射部分的视图，其键范围为 fromKey至 toKey 。
SortedMap<K,V>	subMap(K fromKey, K toKey)	返回此映射部分的视图，其键的范围从 fromKey （包括 toKey ）到 toKey （独占）。
SortedMap<K,V>	tailMap(K fromKey)	返回此映射的部分视图，其键大于或等于 fromKey 。
NavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)	返回此映射的部分视图，其键大于（或等于，如果 inclusive为真） fromKey 。
Collection	values()	返回此映射中包含的值的 Collection 视图。

rotateLeft

// 左旋
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

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

colorOf

// 查看节点颜色
private static <K,V> boolean colorOf(Entry<K,V> p) {
    return (p == null ? BLACK : p.color);
}

parentOf

// 查看节点双亲
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
    return (p == null ? null: p.parent);
}

setColor

// 设置节点颜色
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

leftOf

// 左孩子
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
    return (p == null) ? null: p.left;
}

rightOf

// 右孩子
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
    return (p == null) ? null: p.right;
}

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

fixAfterDeletion

// 删除后的调整函数
private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
    
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            Entry<K,V> sib = leftOf(parentOf(x));
    
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
    
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
    setColor(x, BLACK);
}

getEntry

// 取节点
final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

getEntryUsingComparator

// 使用比较器取节点
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

getFirstEntry

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

getLastEntry

final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

get

// 根据指定的 key 返回相应的 value
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

firstKey

public K firstKey() {
    return key(getFirstEntry());
}

lastKey

public K lastKey() {
    return key(getLastEntry());
}

buildFromSorted

private void buildFromSorted(int size, Iterator<?> it,
                             java.io.ObjectInputStream str,
                             V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    this.size = size;
    root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                           it, str, defaultVal);
}

private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                                         int redLevel,
                                         Iterator<?> it,
                                         java.io.ObjectInputStream str,
                                         V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    /*
     * Strategy: The root is the middlemost element. To get to it, we
     * have to first recursively construct the entire left subtree,
     * so as to grab all of its elements. We can then proceed with right
     * subtree.
     *
     * The lo and hi arguments are the minimum and maximum
     * indices to pull out of the iterator or stream for current subtree.
     * They are not actually indexed, we just proceed sequentially,
     * ensuring that items are extracted in corresponding order.
     */

    if (hi < lo) return null;

    int mid = (lo + hi) >>> 1;

    Entry<K,V> left  = null;
    if (lo < mid)
        left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                               it, str, defaultVal);

    // extract key and/or value from iterator or stream
    K key;
    V value;
    if (it != null) {
        if (defaultVal==null) {
            Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
            key = (K)entry.getKey();
            value = (V)entry.getValue();
        } else {
            key = (K)it.next();
            value = defaultVal;
        }
    } else { // use stream
        key = (K) str.readObject();
        value = (defaultVal != null ? defaultVal : (V) str.readObject());
    }

    Entry<K,V> middle =  new Entry<>(key, value, null);

    // color nodes in non-full bottommost level red
    if (level == redLevel)
        middle.color = RED;

    if (left != null) {
        middle.left = left;
        left.parent = middle;
    }

    if (mid < hi) {
        Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                           it, str, defaultVal);
        middle.right = right;
        right.parent = middle;
    }

    return middle;
}

putAll

public void putAll(Map<? extends K, ? extends V> map) {
    int mapSize = map.size();
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {
        Comparator<?> c = ((SortedMap<?,?>)map).comparator();
        if (c == comparator || (c != null && c.equals(comparator))) {
            ++modCount;
            try {
                buildFromSorted(mapSize, map.entrySet().iterator(),
                                null, null);
            } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
            }
            return;
        }
    }
    super.putAll(map);
}

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();
        @SuppressWarnings("unchecked")
            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;
}

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

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

HashMap

基于哈希表实现，由数组 + 链表 + 红黑树组成

底层数据结构

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

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

transient int size;

transient int modCount;

构造器

构造器	描述
HashMap()	使用默认初始容量（16）和默认加载因子（0.75）构造一个空 HashMap 。
HashMap(int initialCapacity)	使用指定的初始容量和默认加载因子（0.75）构造一个空 HashMap 。
HashMap(int initialCapacity, float loadFactor)	使用指定的初始容量和加载因子构造一个空 HashMap 。
HashMap(Map<? extends K,? extends V> m)	构造一个新的 HashMap ，其映射与指定的 Map相同。

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

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

方法概要

变量和类型	方法	描述
void	clear()	从此映射中删除所有映射。
Object	clone()	返回此 HashMap实例的浅表副本：未克隆键和值本身。
V	compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	尝试计算指定键及其当前映射值的映射（如果没有当前映射， null ）。
V	computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)	如果指定的键尚未与值关联（或映射到 null ），则尝试使用给定的映射函数计算其值并将其输入此映射，除非 null 。
V	computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	如果指定键的值存在且为非null，则尝试在给定键及其当前映射值的情况下计算新映射。
boolean	containsKey(Object key)	如果此映射包含指定键的映射，则返回 true 。
boolean	containsValue(Object value)	如果此映射将一个或多个键映射到指定值，则返回 true 。
Set<Map.Entry<K,V>>	entrySet()	返回此映射中包含的映射的 Set 视图。
V	get(Object key)	返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
boolean	isEmpty()	如果此映射不包含键 - 值映射，则返回 true 。
Set	keySet()	返回此映射中包含的键的 Set 视图。
V	merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)	如果指定的键尚未与值关联或与null关联，则将其与给定的非空值关联。
V	put(K key, V value)	将指定的值与此映射中的指定键相关联。
void	putAll(Map<? extends K,? extends V> m)	将指定映射中的所有映射复制到此映射。
V	remove(Object key)	从此映射中删除指定键的映射（如果存在）。
int	size()	返回此映射中键 - 值映射的数量。
Collection	values()	返回此映射中包含的值的 Collection 视图。

扩容函数

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

getNode

// 取节点
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

containsKey

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

putVal

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)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, 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)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                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)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

putMapEntries

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putAll

public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

removeNode

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)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                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)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

remove

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

containsValue

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (Node<K,V> e : tab) {
            for (; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

keySet

// 返回 key 的集合
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

values

// 返回 value 的集合
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

final class Values extends AbstractCollection<V> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<V> iterator()     { return new ValueIterator(); }
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator<V> spliterator() {
        return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

entrySet

// 返回节点的 set 集合
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

LinkedHashMap

使用双向链表来维护元素的顺序

继承了 HashMap， 实现了 Map 接口，允许放入 null，也允许插入 value 为 null 的元素

可以将 LinkedHashMap 看作是采用 LinkedList 增强的 HashMap

底层数据结构

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

构造器

构造器	描述
LinkedHashMap()	使用默认初始容量（16）和加载因子（0.75）构造一个空的插入排序 LinkedHashMap实例。
LinkedHashMap(int initialCapacity)	构造一个具有指定初始容量和默认加载因子（0.75）的空插入排序 LinkedHashMap实例。
LinkedHashMap(int initialCapacity, float loadFactor)	使用指定的初始容量和加载因子构造一个空的插入排序 LinkedHashMap实例。
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)	使用指定的初始容量，加载因子和排序模式构造一个空的 LinkedHashMap实例。
LinkedHashMap(Map<? extends K,? extends V> m)	构造一个插入有序的 LinkedHashMap实例，其实例与指定的映射相同。

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

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

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

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

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

方法概要

变量和类型	方法	描述
boolean	containsValue(Object value)	如果此映射将一个或多个键映射到指定值，则返回 true 。
Set<Map.Entry<K,V>>	entrySet()	返回此映射中包含的映射的Set视图。
V	get(Object key)	返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
Set	keySet()	返回此映射中包含的键的Set视图。
protected boolean	removeEldestEntry(Map.Entry<K,V> eldest)	如果此地图应删除其最 true则返回 true 。
Collection	values()	返回此映射中包含的值的 Collection 视图。

containsValue

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

get

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

afterNodeAccess

// 插入节点
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;
        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.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

keySet

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new LinkedKeySet();
        keySet = ks;
    }
    return ks;
}

final class LinkedKeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<K> iterator() {
        return new LinkedKeyIterator();
    }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator()  {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super K> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

values

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new LinkedValues();
        values = vs;
    }
    return vs;
}

final class LinkedValues extends AbstractCollection<V> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<V> iterator() {
        return new LinkedValueIterator();
    }
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator<V> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED);
    }
    public final void forEach(Consumer<? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

entrySet

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new LinkedEntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}