四、集合

集合和数组区别

• （1）数组定长，集合不定长
• （2）数组可存基础数据类型和引用类型，集合只能存引用类型

位置：java.util.*;

这是一位仁兄的笔记，师出同门，点我跳转~

1、Collection 精简类图

小拓展：List和 Set区别

• List有下标，存放有序可重复的数据
• Set无下标，存放无序不可重复数据

---

2、Collection

2.1、Collection接口

public interface Collection<E> extends Iterable<E> {// 查询操作/*** 返回此集合中的元素数。* 如果此集合超过Integer.MAX_VALUE个元素，返回Integer.MAX_VALUE*/int size();/* 如果此集合不包含元素，则返回true */boolean isEmpty();/*** 如果此集合包含指定的元素，则返回true* 更正式地说，当且仅当此集合包含至少一个元素e（o==null？e==null:o.equals（e））时，返回true*/boolean contains(Object o);/*** 返回此集合中元素的迭代器。对于返回元素的顺序没有任何保证（除非此集合是提供保证的某个类的实例）*/Iterator<E> iterator();/*** 返回包含此集合中所有元素的数组。* 返回的数组将是“安全的”，因为此集合不维护对它的引用。* （换句话说，即使此集合由数组支持，此方法也必须分配新数组）。因此，调用者可以自由修改返回的数组*/Object[] toArray();/*** 返回包含此集合中所有元素的数组；返回数组的运行时类型是指定数组的运行时间类型。* 如果集合符合指定的数组，则在其中返回。否则，将使用指定数组的运行时类型和此集合的大小分配新数组。** 如果此集合适合指定的具有空闲空间的数组（即，数组中的元素比此集合多），则数组中紧随集合结尾的元素* 将设置为空。（只有当调用者知道此集合不包含任何空元素时，这才有助于确定此集合的长度。）** 如果此集合对迭代器返回其元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素。** 与toArray（）方法一样，该方法充当基于数组和基于集合的API之间的桥梁。* 此外，该方法允许精确控制输出阵列的运行时类型，并且在某些情况下，可以用于节省分配成本。** 假设x是已知只包含字符串的集合。以下代码可用于将集合转储到新分配的字符串数组中：* 			String[] y = x.toArray(new String[0]);* 注意，toArray（new Object[0]）在函数上与toArray()相同。*/<T> T[] toArray(T[] a);// 修改操作/* 添加一个元素 */boolean add(E e);/* 移除指定元素 */boolean remove(Object o);// 批量操作/*** 如果此集合包含指定集合的所有元素，则返回true* 栗子：a有1,2,3；b有2,3,5；a.containsAll(b) = false*/boolean containsAll(Collection<?> c);/*** 移除当前集合与含传入集合元素相同的元素* 栗子：a有1,2,3；b有2,3,5；a.removeAll(b) = 1*/boolean removeAll(Collection<?> c);/*** 移除此集合中满足给定断言的所有元素。迭代期间或断言引发的错误或运行时异常会被传递给调用方* @since 1.8*/default boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);boolean removed = false;final Iterator<E> each = iterator();while (each.hasNext()) {if (filter.test(each.next())) {each.remove();removed = true;}}return removed;}/*** 仅保留当前集合与含传入集合元素相同的元素* 栗子：a有1,2,3；b有2,3,5；a.removeAll(b) = 2，3*/boolean retainAll(Collection<?> c);/* 移除当前集合所有元素 */void clear();// 比较和散列/* 将指定的对象与此集合进行相等性比较. */boolean equals(Object o);/* 返回此集合的哈希代码值. */int hashCode();/*** 在此集合中的元素上创建{@link Spliterator}.* @since 1.8*/@Overridedefault Spliterator<E> spliterator() {return Spliterators.spliterator(this, 0);}/*** 返回一个序列｛@code Stream｝，该集合作为其源.n* @since 1.8*/default Stream<E> stream() {return StreamSupport.stream(spliterator(), false);}/*** 返回一个可能并行的｛@code Stream｝，该集合作为其源。允许此方法返回顺序流.* @since 1.8*/default Stream<E> parallelStream() {return StreamSupport.stream(spliterator(), true);}
}

2.2、Iterator 迭代器

说到 Collection 就不得不提一嘴迭代器 Iterator

public interface Iterator<E> {/* 如果迭代具有更多元素，则返回 true */boolean hasNext();/* 返回迭代中的下一个元素 */E next();/* 从底层集合中删除此迭代器返回的最后一个元素 */default void remove() {throw new UnsupportedOperationException("remove");}/* 对每个剩余元素执行给定的操作，直到所有元素都被处理或动作引发异常 */default void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (hasNext())action.accept(next());}
}

2.3、遍历

①通过增强 for 遍历集合

for(Object o : collection){System.out.println(o);
}

②通过迭代器遍历集合

Iterator it = collection.iterator();
while(it.hasNext()) {System.out.println(it.next());//调用一次next就会获取下一个元素一次，如果循环内多次调用超界就会报错//System.out.println(it.next()); // 迭代过程中不能使用集合的移除操作，会报并发修改异常// java.util.CocurrentModificationException// collection.remove(it);it.remove(); // 迭代时移除必须使用迭代器提供的移除方法
}

---

3、Collection > List

特点：有序、有下标、可重复

3.1、List 接口

注：下面代码只显示父接口没有的

public interface List<E> extends Collection<E> {/*** 将指定集合中的所有元素插入到此列表中的指定位置* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加其索引）* 新元素将按照指定集合的迭代器返回的顺序出现在该列表中* 如果在操作进行过程中修改了指定的集合，则此操作的行为未定义* （请注意，如果指定的集合是此列表，并且它是非空的，则会发生这种情况）*/boolean addAll(int index, Collection<? extends E> c);/*** 用对该元素应用运算符的结果替换此列表的每个元素* 运算符引发的错误或运行时异常将被中继到调用者* @since 1.8*/default void replaceAll(UnaryOperator<E> operator) {Objects.requireNonNull(operator);final ListIterator<E> li = this.listIterator();while (li.hasNext()) {li.set(operator.apply(li.next()));}}/*** 根据指定的{@link-Comparator}诱导的顺序对该列表排序* @since 1.8*/@SuppressWarnings({"unchecked", "rawtypes"})default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}// 位置访问操作/* 返回此列表中指定位置的元素 */E get(int index);/* 用指定的元素替换此列表中指定位置的元素 */E set(int index, E element);/*** 在此列表中的指定位置插入指定元素* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）*/void add(int index, E element);/*** 删除此列表中指定位置的元素* 将任何后续元素向左移动（从其索引中减去一个）* 返回从列表中删除的元素*/E remove(int index);// 搜索操作/*** 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回-1* 更正式地说，返回最低索引 i 以使（o==null ? get(i)==null : o.equals(get(i))）* 如果没有这样的索引，则为-1*/int indexOf(Object o);/*** 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1* 更正式地说，返回最高索引 i 以使(o==null ? get(i)==null : o.equals(get(i)))* 如果没有这样的索引，则为-1*/int lastIndexOf(Object o);// 列表迭代器/* 返回列表中元素的列表迭代器（按正确顺序）*/ListIterator<E> listIterator();/*** 从列表中的指定位置开始，返回此列表中元素的列表迭代器（按正确顺序）* 指定的索引指示初始调用｛@link ListIterator#next next｝将返回的第一个元素* 对｛@link ListIterator#previous previous｝的初始调用将返回具有指定索引减1的元素*/ListIterator<E> listIterator(int index);// 视图/*** 返回此列表在指定的fromIndex（包含）和toIndex（不包含）之间的部分的视图* 最直观的写法：[fromIndex, toIndex)* （如果fromIndex和toIndex相等，返回的列表为空）* 返回的列表由该列表支持，因此返回列表中的非结构更改将反映在该列表中，反之亦然* 返回的列表支持此列表支持的所有可选列表操作** 这种方法不需要显式范围操作（通常存在于数组中）* 任何需要列表的操作都可以通过传递子列表视图而不是整个列表来用作范围操作* 例如，以下习惯用法从列表中删除一系列元素：*      list.subList(from, to).clear();* 可以为indexOf和lastIndexOf构造类似的习惯用法，集合类中的所有算法都可以应用于子列表** 如果支持列表（即，此列表）在结构上被修改，而不是通过返回的列表，则此方法返回的列表的语义将变得未定义* （结构修改是指改变此列表的大小，或以某种方式干扰列表，从而导致正在进行的迭代可能产生不正确的结果）*/List<E> subList(int fromIndex, int toIndex);
}

3.2、ListIterator 系列表迭代器

说到 List 就不得不提一嘴系列表迭代器 ListIterator，在Collection的迭代器基础上做了增强

public interface ListIterator<E> extends Iterator<E> {// 查询操作/*** 如果此列表迭代器在正向遍历列表时具有更多元素，则返回{@code true}* （换句话说，如果{@link #next}返回元素而不是抛出异常，则返回{@code true}）*/boolean hasNext();/*** 返回列表中的下一个元素并前进光标位置* 该方法可以重复调用以遍历列表，或者与对｛@link #previous｝的调用混合使用以来回* （注意，交替调用{@code-next}和{@code-previous}将重复返回相同的元素）*/E next();/*** 如果此列表迭代器在反向遍历列表时具有更多元素，则返回{@code true}* （换句话说，如果{@link #previous}返回元素而不是抛出异常，则返回{@code true}）*/boolean hasPrevious();/*** 返回列表中的上一个元素并向后移动光标位置* 可以重复调用此方法以向后遍历列表，或者与对{@link35;next}的调用混合使用以来回遍历* （注意，交替调用{@code-next}和{@code-previous}将重复返回相同的元素）*/E previous();/*** 返回后续调用｛@link #next｝将返回的元素索引* （如果列表迭代器位于列表末尾，则返回列表大小）*/int nextIndex();/*** 返回后续调用{@link #previous}将返回的元素索引* （如果列表迭代器位于列表的开头，则返回-1）*/int previousIndex();// 修改操作/*** 从列表中删除｛@link #next｝或｛@link #previous｝返回的最后一个元素* 每次调用｛@code next｝或｛@code previous｝只能进行一次此调用* 只有在上次调用｛@code next｝或｛@code previous｝后未调用｛@link #add｝，才能执行此操作*/void remove();/*** 用指定的元素替换{@link #next} 或 {@link #previous}返回的最后一个元素* 只有在上一次调用｛@code next｝或｛@code previous｝后，* 既没有调用{@link #remove}也没有调用{@link #add}，才能进行此调用*/void set(E e);/*** 将指定的元素插入列表* 元素被插入到{@link #next}将返回的元素（如果有）之前，* 以及{@link #previous}返回的元素之后（如果有）* （如果列表不包含元素，新元素将成为列表上的唯一元素）* 新元素插入隐式光标之前：对{@code next}的后续调用将不受影响，* 对{@code previous}后续调用将返回新元素* （此调用将调用{@code nextIndex} 或 {@code previousIndex}返回的值增加一）*/void add(E e);
}

3.3、循环

①普通for循环

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

②增强for循环

for(Object o : list){Sysout.out.println(o)
}

③迭代器 Iterator

Iterator it = list.iterator();
while(it.hasNext()) {System.out.println(it.next());//调用一次next就会获取下一个元素一次，如果循环内多次调用超界就会报错//System.out.println(it.next()); // 迭代过程中不能使用集合的移除操作，会报并发修改异常// java.util.CocurrentModificationException// collection.remove(it);it.remove(); // 迭代时移除必须使用迭代器提供的移除方法
}

④系列表迭代器 ListIterator

ListIterator li = list.iterator();
// 从前往后
while(li.hasNext()) {System.out.println(li.nextIndex + "--" + li.next());//调用一次next就会获取下一个元素一次，如果循环内多次调用超界就会报错//System.out.println(li.nextIndex + "--" + li.next()); // 迭代过程中不能使用集合的移除操作，会报并发修改异常// java.util.CocurrentModificationException// collection.remove(li);li.remove(); // 迭代时移除必须使用迭代器提供的移除方法
}// 从后往前
while(li.hasPrevious()) {System.out.println(li.previousIndex + "--" + li.previous());
}

3.4、List 的实现类

3.4.1、ArrayList

存储结构：数组
性质：连续内存，查询快，增删慢

Jdk1.2加入，运行效率快，线程不安全

注意：没向ArrayList添加任何元素时，容量为 0，添加一个之后给默认容量 DEFAULT_CAPACITY = 10；每次扩容 newCapacity = oldCapacity + (oldCapacity >> 1)

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{/* 默认初始容量 */private static final int DEFAULT_CAPACITY = 10;/* 用于空实例的共享空数组实例 */private static final Object[] EMPTY_ELEMENTDATA = {};/*** 用于默认大小的空实例的共享空数组实例* 我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 存储ArrayList元素的数组缓冲区* TArrayList的容量是该数组缓冲区的长度* 当添加第一个元素时，任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的* 空ArrayList将扩展为 DEFAULT_CAPACITY*/transient Object[] elementData; // non-private to simplify nested class access/* ArrayList的大小（它包含的元素数）*/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);}}/*** 构造初始容量为10的空列表.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/* 按照集合迭代器返回元素的顺序构造包含指定集合元素的列表 */public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray 可能（错误地）不返回 Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 替换为空数组this.elementData = EMPTY_ELEMENTDATA;}}/*** 将此 ArrayList 实例的容量修剪为列表的当前大小* 应用程序可以使用此操作最小化 ArrayList 实例的存储*/public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}/* 如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳最小容量参数指定的元素数 */public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// 任何大小，如果不是默认元素表? 0// 大于默认空表的默认值，它应该已经是默认大小: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}/* 要分配的数组的最大大小 */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/* 增加容量，以确保它至少可以容纳最小容量参数指定的元素数 */private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity 通常接近 size，因此这是一个 win:elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // 溢出throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}/* 返回此列表中的元素数 */public int size() {return size;}/* 如果此列表不包含元素，则返回 true */public boolean isEmpty() {return size == 0;}/* 如果此列表包含指定元素，则返回 true */public boolean contains(Object o) {return indexOf(o) >= 0;}/* 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回-1 */public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}/* 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1 */public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}/* 返回此 ArrayList 实例的浅拷贝（元素本身不会被复制）*/public Object clone() {try {ArrayList<?> v = (ArrayList<?>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// 这不应该发生，因为我们是可克隆的throw new InternalError(e);}}/* 返回一个数组，该数组包含该列表中的所有元素（从第一个元素到最后一个元素）*/public Object[] toArray() {return Arrays.copyOf(elementData, size);}/*** 返回一个数组，该数组包含该列表中的所有元素（从第一个元素到最后一个元素）；* 返回数组的运行时类型是指定数组的运行时间类型* 如果列表符合指定的数组，则返回该数组* 否则，将使用指定数组的运行时类型和此列表的大小分配新数组*/@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) {if (a.length < size)// 创建 a 的运行时类型的新数组，但我的内容：return (T[]) Arrays.copyOf(elementData, size, a.getClass());System.arraycopy(elementData, 0, a, 0, size);if (a.length > size)a[size] = null;return a;}// 位置访问操作@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}/* 返回此列表中指定位置的元素 */public E get(int index) {rangeCheck(index);return elementData(index);}/* 将列表中指定位置的元素替换为指定元素 */public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}/* 将指定的元素追加到此列表的末尾 */public boolean add(E e) {ensureCapacityInternal(size + 1);  // 递增 modCount!!elementData[size++] = e;return true;}/*** 在此列表中的指定位置插入指定元素* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）*/public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // 递增 modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}/*** 删除此列表中指定位置的元素* 将任何后续元素向左移动（从其索引中减去一）*/public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // 明确让GC完成它的工作return oldValue;}/*** 从列表中删除指定元素的第一个匹配项（如果存在）。如果列表不包含元素，则该元素保持不变** 更正式地说，删除索引最低的元素 i 以便* (o==null ? get(i)==null : o.equals(get(i)))（如果存在这样的元素）* 如果此列表包含指定元素，则返回<tt>true</tt>（或者等效地，如果此列表由于调用而更改）*/public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}/* 私有的 remove 方法跳过边界检查，并且不返回已移除的值 */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; // 明确让GC完成它的工作}/* 从列表中删除所有元素。此调用返回后，列表将为空 */public void clear() {modCount++;// 明确让GC完成它的工作for (int i = 0; i < size; i++)elementData[i] = null;size = 0;}/*** 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾* 如果在操作过程中修改了指定集合，则此操作的行为未定义* （这意味着如果指定的集合是此列表，并且此列表为非空，则此调用的行为是未定义的）*/public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}/*** 从指定位置开始，将指定集合中的所有元素插入此列表* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加其索引）* 新元素将按指定集合的迭代器返回的顺序显示在列表中*/public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // 递增 modCountint numMoved = size - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;}/*** 从该列表中删除其索引介于｛@code fromIndex｝（包含）和｛@code toIndex}（独占）之间的所有元素，* 将任何后续元素向左移动（减少其索引）* 此调用通过{@code（toIndex- fromIndex）}元素缩短列表* （如果{@code toIndex == fromIndex}，则此操作无效）*/protected void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved = size - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);// 明确让GC完成它的工作int newSize = size - (toIndex-fromIndex);for (int i = newSize; i < size; i++) {elementData[i] = null;}size = newSize;}/*** 检查给定索引是否在范围内。如果不是，则抛出适当的运行时异常* 此方法不检查索引是否为负：它总是在数组访问之前使用，如果索引为负，* 则抛出 ArrayIndexOutOfBoundsException*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/* add和addAll使用的rangeCheck版本 */private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 构造 IndexOutOfBoundsException 详细信息* 在许多可能的错误处理代码重构中，这种“概述”在服务器和客户机虚拟机上都表现得最好*/private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}/* 从此列表中删除指定集合中包含的所有元素 */public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}/*** 仅保留此列表中包含在指定集合中的元素* 换句话说，从列表中删除指定集合中不包含的所有元素*/public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;int r = 0, w = 0;boolean modified = false;try {for (; r < size; r++)if (c.contains(elementData[r]) == complement)elementData[w++] = elementData[r];} finally {// 保持与 AbstractCollection 的行为兼容性，即使 c.contains() 抛出异常if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;}if (w != size) {// 明确让GC完成它的工作for (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}/* 将 ArrayList 实例的状态保存到流中（即序列化）*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// 写出元素计数和任何隐藏的东西int expectedModCount = modCount;s.defaultWriteObject();// 将大小写为与 clone() 行为兼容性的容量s.writeInt(size);// 按正确顺序写出所有元素for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}/* 从流中重构 ArrayList 实例（即反序列化）*/private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData = EMPTY_ELEMENTDATA;// 阅读大小和任何隐藏的东西s.defaultReadObject();// 读取容量s.readInt(); // ignoredif (size > 0) {// 类似于 clone(), 根据大小而不是容量分配数组ensureCapacityInternal(size);Object[] a = elementData;// 按正确顺序读入所有元素for (int i=0; i<size; i++) {a[i] = s.readObject();}}}/*** 返回列表中元素的列表迭代器（按正确顺序），从列表中的指定位置开始* 指定的索引指示初始调用 {@link ListIterator#next next}将返回的第一个元素* 对 {@link ListIterator#previous previous} 的初始调用将返回指定索引减去1的元素*/public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index);return new ListItr(index);}/* 返回列表中元素的列表迭代器（按正确顺序）*/public ListIterator<E> listIterator() {return new ListItr(0);}/* 按正确顺序返回此列表中元素的迭代器 */public Iterator<E> iterator() {return new Itr();}/* AbstractList.Itr 的优化版本 */private class Itr implements Iterator<E> {int cursor;       // 要返回的下一个元素的索引int lastRet = -1; // 返回的最后一个元素的索引-1.如没有int expectedModCount = modCount;public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}@Override@SuppressWarnings("unchecked")public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);final int size = ArrayList.this.size;int i = cursor;if (i >= size) {return;}final Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length) {throw new ConcurrentModificationException();}while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[i++]);}// 在迭代结束时更新一次，以减少堆写入流量cursor = i;lastRet = i - 1;checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}/* AbstractList.ListItr 的优化版本 */private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super();cursor = index;}public boolean hasPrevious() {return cursor != 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();int i = cursor - 1;if (i < 0)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i;return (E) elementData[lastRet = i];}public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void add(E e) {checkForComodification();try {int i = cursor;ArrayList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}/*** 返回此列表中位于指定的｛@code fromIndex｝（包含）和｛@code toIndex}（包含）之间的部分的视图* (If{@code fromIndex} and {@code toIndex} are equal, the returned list is* empty.)  The returned list is backed by this list, so non-structural* changes in the returned list are reflected in this list, and vice-versa.* The returned list supports all of the optional list operations.** <p>This method eliminates the need for explicit range operations (of* the sort that commonly exist for arrays).  Any operation that expects* a list can be used as a range operation by passing a subList view* instead of a whole list.  For example, the following idiom* removes a range of elements from a list:* <pre>*      list.subList(from, to).clear();* </pre>* Similar idioms may be constructed for {@link #indexOf(Object)} and* {@link #lastIndexOf(Object)}, and all of the algorithms in the* {@link Collections} class can be applied to a subList.** <p>The semantics of the list returned by this method become undefined if* the backing list (i.e., this list) is <i>structurally modified</i> in* any way other than via the returned list.  (Structural modifications are* those that change the size of this list, or otherwise perturb it in such* a fashion that iterations in progress may yield incorrect results.)** @throws IndexOutOfBoundsException {@inheritDoc}* @throws IllegalArgumentException {@inheritDoc}*/public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, 0, fromIndex, toIndex);}static void subListRangeCheck(int fromIndex, int toIndex, int size) {if (fromIndex < 0)throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);if (toIndex > size)throw new IndexOutOfBoundsException("toIndex = " + toIndex);if (fromIndex > toIndex)throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")");}private class SubList extends AbstractList<E> implements RandomAccess {private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) {this.parent = parent;this.parentOffset = fromIndex;this.offset = offset + fromIndex;this.size = toIndex - fromIndex;this.modCount = ArrayList.this.modCount;}public E set(int index, E e) {rangeCheck(index);checkForComodification();E oldValue = ArrayList.this.elementData(offset + index);ArrayList.this.elementData[offset + index] = e;return oldValue;}public E get(int index) {rangeCheck(index);checkForComodification();return ArrayList.this.elementData(offset + index);}public int size() {checkForComodification();return this.size;}public void add(int index, E e) {rangeCheckForAdd(index);checkForComodification();parent.add(parentOffset + index, e);this.modCount = parent.modCount;this.size++;}public E remove(int index) {rangeCheck(index);checkForComodification();E result = parent.remove(parentOffset + index);this.modCount = parent.modCount;this.size--;return result;}protected void removeRange(int fromIndex, int toIndex) {checkForComodification();parent.removeRange(parentOffset + fromIndex,parentOffset + toIndex);this.modCount = parent.modCount;this.size -= toIndex - fromIndex;}public boolean addAll(Collection<? extends E> c) {return addAll(this.size, c);}public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);int cSize = c.size();if (cSize==0)return false;checkForComodification();parent.addAll(parentOffset + index, c);this.modCount = parent.modCount;this.size += cSize;return true;}public Iterator<E> iterator() {return listIterator();}public ListIterator<E> listIterator(final int index) {checkForComodification();rangeCheckForAdd(index);final int offset = this.offset;return new ListIterator<E>() {int cursor = index;int lastRet = -1;int expectedModCount = ArrayList.this.modCount;public boolean hasNext() {return cursor != SubList.this.size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= SubList.this.size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[offset + (lastRet = i)];}public boolean hasPrevious() {return cursor != 0;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();int i = cursor - 1;if (i < 0)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length)throw new ConcurrentModificationException();cursor = i;return (E) elementData[offset + (lastRet = i)];}@SuppressWarnings("unchecked")public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);final int size = SubList.this.size;int i = cursor;if (i >= size) {return;}final Object[] elementData = ArrayList.this.elementData;if (offset + i >= elementData.length) {throw new ConcurrentModificationException();}while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[offset + (i++)]);}// 在迭代结束时更新一次，以减少堆写入流量lastRet = cursor = i;checkForComodification();}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {SubList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = ArrayList.this.modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(offset + lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void add(E e) {checkForComodification();try {int i = cursor;SubList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = ArrayList.this.modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (expectedModCount != ArrayList.this.modCount)throw new ConcurrentModificationException();}};}public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, offset, fromIndex, toIndex);}private void rangeCheck(int index) {if (index < 0 || index >= this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private void rangeCheckForAdd(int index) {if (index < 0 || index > this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+this.size;}private void checkForComodification() {if (ArrayList.this.modCount != this.modCount)throw new ConcurrentModificationException();}public Spliterator<E> spliterator() {checkForComodification();return new ArrayListSpliterator<E>(ArrayList.this, offset,offset + this.size, this.modCount);}}@Overridepublic void forEach(Consumer<? super E> action) {Objects.requireNonNull(action);final int expectedModCount = modCount;@SuppressWarnings("unchecked")final E[] elementData = (E[]) this.elementData;final int size = this.size;for (int i=0; modCount == expectedModCount && i < size; i++) {action.accept(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* list.** <p>The {@code Spliterator} reports {@link Spliterator#SIZED},* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.* Overriding implementations should document the reporting of additional* characteristic values.** @return a {@code Spliterator} over the elements in this list* @since 1.8*/@Overridepublic Spliterator<E> spliterator() {return new ArrayListSpliterator<>(this, 0, -1, 0);}/** 基于索引的二次拆分，延迟初始化拆分器 */static final class ArrayListSpliterator<E> implements Spliterator<E> {/** If ArrayLists were immutable, or structurally immutable (no* adds, removes, etc), we could implement their spliterators* with Arrays.spliterator. Instead we detect as much* interference during traversal as practical without* sacrificing much performance. We rely primarily on* modCounts. These are not guaranteed to detect concurrency* violations, and are sometimes overly conservative about* within-thread interference, but detect enough problems to* be worthwhile in practice. To carry this out, we (1) lazily* initialize fence and expectedModCount until the latest* point that we need to commit to the state we are checking* against; thus improving precision.  (This doesn't apply to* SubLists, that create spliterators with current non-lazy* values).  (2) We perform only a single* ConcurrentModificationException check at the end of forEach* (the most performance-sensitive method). When using forEach* (as opposed to iterators), we can normally only detect* interference after actions, not before. Further* CME-triggering checks apply to all other possible* violations of assumptions for example null or too-small* elementData array given its size(), that could only have* occurred due to interference.  This allows the inner loop* of forEach to run without any further checks, and* simplifies lambda-resolution. While this does entail a* number of checks, note that in the common case of* list.stream().forEach(a), no checks or other computation* occur anywhere other than inside forEach itself.  The other* less-often-used methods cannot take advantage of most of* these streamlinings.*/private final ArrayList<E> list;private int index; // 当前索引，在提前/拆分时修改private int fence; // -1直到使用；然后是最后一个指数private int expectedModCount; // 设置围栏时初始化/** 创建覆盖给定范围的新拆分器 */ArrayListSpliterator(ArrayList<E> list, int origin, int fence,int expectedModCount) {this.list = list; // 如果为空，则确定，除非遍历this.index = origin;this.fence = fence;this.expectedModCount = expectedModCount;}private int getFence() { // 第一次使用时将围栏初始化为大小int hi; // (方法forEach中出现了一个专门的变体)ArrayList<E> lst;if ((hi = fence) < 0) {if ((lst = list) == null)hi = fence = 0;else {expectedModCount = lst.modCount;hi = fence = lst.size;}}return hi;}public ArrayListSpliterator<E> trySplit() {int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;return (lo >= mid) ? null : // 将范围一分为二，除非太小new ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);}public boolean tryAdvance(Consumer<? super E> action) {if (action == null)throw new NullPointerException();int hi = getFence(), i = index;if (i < hi) {index = i + 1;@SuppressWarnings("unchecked") E e = (E)list.elementData[i];action.accept(e);if (list.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}return false;}public void forEachRemaining(Consumer<? super E> action) {int i, hi, mc; // 提升机从回路进入并检查ArrayList<E> lst; Object[] a;if (action == null)throw new NullPointerException();if ((lst = list) != null && (a = lst.elementData) != null) {if ((hi = fence) < 0) {mc = lst.modCount;hi = lst.size;}elsemc = expectedModCount;if ((i = index) >= 0 && (index = hi) <= a.length) {for (; i < hi; ++i) {@SuppressWarnings("unchecked") E e = (E) a[i];action.accept(e);}if (lst.modCount == mc)return;}}throw new ConcurrentModificationException();}public long estimateSize() {return (long) (getFence() - index);}public int characteristics() {return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;}}@Overridepublic boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);// 确定要删除哪些元素。在此阶段从筛选器谓词抛出的任何异常都将使集合保持不变int removeCount = 0;final BitSet removeSet = new BitSet(size);final int expectedModCount = modCount;final int size = this.size;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;  // 让gc完成它的工作}this.size = newSize;if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}return anyToRemove;}@Override@SuppressWarnings("unchecked")public void replaceAll(UnaryOperator<E> operator) {Objects.requireNonNull(operator);final int expectedModCount = modCount;final int size = this.size;for (int i=0; modCount == expectedModCount && i < size; i++) {elementData[i] = operator.apply((E) elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}@Override@SuppressWarnings("unchecked")public void sort(Comparator<? super E> c) {final int expectedModCount = modCount;Arrays.sort((E[]) elementData, 0, size, c);if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}
}

3.4.2、LinkedList

存储结构：双向链表
性质：非连续内存，增删快，查询慢

Jdk1.2加入，线程不安全

• 使用方面和ArrayList类似，由于是链表，故多了首尾操作
  • addFirst
  • addLast
  • removeFirst
  • removeLast

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;/*** 指向第一个节点的指针.* 不变：(first == null && last == null) || (first.prev == null && first.item != null)*/transient Node<E> first;/*** 指向最后一个节点的指针.* 不变：(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);}/* 链接e作为第一个元素 */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;elsef.prev = newNode;size++;modCount++;}/* 链接e作为最后一个元素 */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;elsel.next = newNode;size++;modCount++;}/* 在非空节点 succ 前插入元素 e */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;elsepred.next = newNode;size++;modCount++;}/* 取消非空第一节点 f 的链接 */private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}/* 取消非空最后一个节点 l 的链接 */private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}/* 取消与非空节点x的链接 */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;}/* 返回此列表中的第一个元素 */public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/* 返回此列表中的最后一个元素 */public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}/* 从列表中删除并返回第一个元素 */public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}/* 删除并返回此列表中的最后一个元素 */public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}/* 在此列表的开头插入指定的元素 */public void addFirst(E e) {linkFirst(e);}/* 将指定的元素追加到此列表的末尾 */public void addLast(E e) {linkLast(e);}/* 如果此列表包含指定元素，则返回{@code:true} */public boolean contains(Object o) {return indexOf(o) != -1;}/* 返回此列表中的元素数 */public int size() {return size;}/* 将指定的元素追加到此列表的末尾 */public boolean add(E e) {linkLast(e);return true;}/*** 从列表中删除指定元素的第一个匹配项（如果存在）.* 如果该列表不包含该元素，则该元素保持不变.*/public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}/*** 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾.* 如果在操作过程中修改了指定集合，则此操作的行为未定义.* （请注意，如果指定的集合是此列表，并且它是非空的，则会发生这种情况）*/public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}/*** 从指定位置开始，将指定集合中的所有元素插入此列表.* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加其索引）.* 新元素将按指定集合的迭代器返回的顺序显示在列表中.*/public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);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;elsepred.next = newNode;pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}/* 从列表中删除所有元素；此调用返回后，列表将为空 */public void clear() {// Clearing all of the links between nodes is "unnecessary", but:// - helps a generational GC if the discarded nodes inhabit//   more than one generation// - is sure to free memory even if there is a reachable Iteratorfor (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;modCount++;}// 位置访问操作/* 返回此列表中指定位置的元素 */public E get(int index) {checkElementIndex(index);return node(index).item;}/* 返回此列表中指定位置的元素。用指定元素替换此列表中的指定位置处的元素 */public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}/*** 在此列表中的指定位置插入指定元素.* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）*/public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}/*** 删除此列表中指定位置的元素.* 将任何后续元素向左移动（从其索引中减去一）* 返回从列表中删除的元素*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}/* 告诉参数是否是现有元素的索引 */private boolean isElementIndex(int index) {return index >= 0 && index < size;}/* 告诉参数是否是迭代器或添加操作的有效位置的索引 */private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}/*** 构造 IndexOutOfBoundsException 详细信息.* 在许多可能的错误处理代码重构中，这种“概述”在服务器和客户机虚拟机上都表现得最好.*/private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/* 返回指定元素索引处的（非空）节点 */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;}}// 搜索操作/* 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回-1 */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;}/* 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1 */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;}// 队列操作./* 检索但不删除此列表的头（第一个元素）*/public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}/* 检索但不删除此列表的头（第一个元素）*/public E element() {return getFirst();}/* 检索并删除此列表的头（第一个元素）*/public E poll() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}/* 检索并删除此列表的头（第一个元素）*/public E remove() {return removeFirst();}/* 添加指定的元素作为此列表的尾部（最后一个元素）*/public boolean offer(E e) {return add(e);}// Deque 操作/* 在此列表的前面插入指定的元素 */public boolean offerFirst(E e) {addFirst(e);return true;}/* 在此列表末尾插入指定的元素 */public boolean offerLast(E e) {addLast(e);return true;}/* 检索但不删除此列表的第一个元素，如果此列表为空，则返回｛@code null｝*/public E peekFirst() {final Node<E> f = first;return (f == null) ? null : f.item;}/* 检索但不删除此列表的最后一个元素，如果此列表为空，则返回｛@code null｝*/public E peekLast() {final Node<E> l = last;return (l == null) ? null : l.item;}/* 检索并删除此列表的第一个元素，如果此列表为空，则返回｛@code null｝*/public E pollFirst() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}/* 检索并删除此列表的最后一个元素，如果此列表为空，则返回｛@code null｝*/public E pollLast() {final Node<E> l = last;return (l == null) ? null : unlinkLast(l);}/* 插入操作（将元素推送到由该列表表示的堆栈上。换句话说，在列表的前面插入元素）*/public void push(E e) {addFirst(e);}/* 从该列表表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素 */public E pop() {return removeFirst();}/*** 移除才做* 移除此列表中指定元素的第一个匹配项（当从头到尾遍历列表时）* 如果列表不包含元素，则该元素保持不变*/public boolean removeFirstOccurrence(Object o) {return remove(o);}/* 移除此列表中指定元素的最后一次出现（当从头到尾遍历列表时）；如果列表不包含元素，则该元素保持不变 */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;}/* 返回此列表中元素的列表迭代器（按正确顺序），从列表中的指定位置开始 */public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public boolean hasNext() {return nextIndex < size;}public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}public boolean hasPrevious() {return nextIndex > 0;}public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item;}public int nextIndex() {return nextIndex;}public int previousIndex() {return nextIndex - 1;}public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;}public void set(E e) {if (lastReturned == null)throw new IllegalStateException();checkForComodification();lastReturned.item = e;}public void add(E e) {checkForComodification();lastReturned = null;if (next == null)linkLast(e);elselinkBefore(e, next);nextIndex++;expectedModCount++;}public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);lastReturned = next;next = next.next;nextIndex++;}checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}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;}}/* @since 1.6 */public Iterator<E> descendingIterator() {return new DescendingIterator();}/* 通过 ListItr.previous 提供降序迭代器的适配器 */private class DescendingIterator implements Iterator<E> {private final ListItr itr = new ListItr(size());public boolean hasNext() {return itr.hasPrevious();}public E next() {return itr.previous();}public void remove() {itr.remove();}}@SuppressWarnings("unchecked")private LinkedList<E> superClone() {try {return (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}}/* 返回此｛@code LinkedList｝的浅表副本（元素本身不会被克隆）*/public Object clone() {LinkedList<E> clone = superClone();// Put clone into "virgin" stateclone.first = clone.last = null;clone.size = 0;clone.modCount = 0;// Initialize clone with our elementsfor (Node<E> x = first; x != null; x = x.next)clone.add(x.item);return clone;}/* 返回一个数组，该数组包含该列表中的所有元素（从第一个元素到最后一个元素）*/public Object[] toArray() {Object[] result = new Object[size];int i = 0;for (Node<E> x = first; x != null; x = x.next)result[i++] = x.item;return result;}/*** 返回一个数组，该数组包含该列表中的所有元素（从第一个元素到最后一个元素）；* 返回数组的运行时类型是指定数组的运行时间类型。如果列表符合指定的数组，* 则返回该数组。否则，将使用指定数组的运行时类型和此列表的大小分配新数组.*/@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) {if (a.length < size)a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);int i = 0;Object[] result = a;for (Node<E> x = first; x != null; x = x.next)result[i++] = x.item;if (a.length > size)a[size] = null;return a;}/* 将此｛@code LinkedList｝实例的状态保存到流中（即序列化）*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// Write out sizes.writeInt(size);// Write out all elements in the proper order.for (Node<E> x = first; x != null; x = x.next)s.writeObject(x.item);}/* 从流中重构此｛@code LinkedList｝实例（即反序列化）*/@SuppressWarnings("unchecked")private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// Read in sizeint size = s.readInt();// Read in all elements in the proper order.for (int i = 0; i < size; i++)linkLast((E)s.readObject());}/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* list.** <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and* {@link Spliterator#ORDERED}.  Overriding implementations should document* the reporting of additional characteristic values.** @implNote* The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}* and implements {@code trySplit} to permit limited parallelism..** @return a {@code Spliterator} over the elements in this list* @since 1.8*/@Overridepublic Spliterator<E> spliterator() {return new LLSpliterator<E>(this, -1, 0);}/* Spliterators.IteratorSpliterator 的自定义变体 */static final class LLSpliterator<E> implements Spliterator<E> {static final int BATCH_UNIT = 1 << 10;  // batch array size incrementstatic final int MAX_BATCH = 1 << 25;  // max batch array size;final LinkedList<E> list; // null OK unless traversedNode<E> current;      // current node; null until initializedint est;              // size estimate; -1 until first neededint expectedModCount; // initialized when est setint batch;            // batch size for splitsLLSpliterator(LinkedList<E> list, int est, int expectedModCount) {this.list = list;this.est = est;this.expectedModCount = expectedModCount;}final int getEst() {int s; // force initializationfinal LinkedList<E> lst;if ((s = est) < 0) {if ((lst = list) == null)s = est = 0;else {expectedModCount = lst.modCount;current = lst.first;s = est = lst.size;}}return s;}public long estimateSize() { return (long) getEst(); }public Spliterator<E> trySplit() {Node<E> p;int s = getEst();if (s > 1 && (p = current) != null) {int n = batch + BATCH_UNIT;if (n > s)n = s;if (n > MAX_BATCH)n = MAX_BATCH;Object[] a = new Object[n];int j = 0;do { a[j++] = p.item; } while ((p = p.next) != null && j < n);current = p;batch = j;est = s - j;return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);}return null;}public void forEachRemaining(Consumer<? super E> action) {Node<E> p; int n;if (action == null) throw new NullPointerException();if ((n = getEst()) > 0 && (p = current) != null) {current = null;est = 0;do {E e = p.item;p = p.next;action.accept(e);} while (p != null && --n > 0);}if (list.modCount != expectedModCount)throw new ConcurrentModificationException();}public boolean tryAdvance(Consumer<? super E> action) {Node<E> p;if (action == null) throw new NullPointerException();if (getEst() > 0 && (p = current) != null) {--est;E e = p.item;current = p.next;action.accept(e);if (list.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}return false;}public int characteristics() {return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;}}}

3.4.3、Vector (开发使用不多，了解即可)

存储结构：数组
性质：查询快，增删慢

Vector类实现了可扩展的对象数组。 像数组一样，它包含可以使用整数索引访问的组件。 但是， Vector的大小可以根据需要增长或缩小，以适应在创建Vector之后添加和删除项目

Jdk1.0加入，运行效率慢。线程安全（方法由 synchronized 修饰）

用法和 ArrayList 类似

3.4.3.1、枚举器

public interface Enumeration<E> {/* 测试此枚举是否包含更多元素 */boolean hasMoreElements();/* 如果此枚举对象至少还有一个元素要提供，则返回此枚举的下一个元素 */E nextElement();
}

3.4.3.2、枚举器遍历

Enumeration elements = vector.elements();
while(elements.hasMoreElements()){System.out.println(elements.nextElement());
}

3.5、四种初始化方式

1. Arrays.asList

   1. ArrayList<Type> obj = new ArrayList<Type>(Arrays.asList(Object o1, Object o2, Object o3, ...));
      

2. 匿名内部初始化

   1. ArrayList<T> obj = new ArrayList<T>() {{add(Object o1);add(Object o2);...
      }};
      

3. 一个个add

4. Collections.nCopies(通过复制)

   1. ArrayList<T> obj = new ArrayList<T>(Collections.nCopies(count, element));
      

---

4、Collection > Set

特点：无序、有下标、不可重复（重复直接丢弃）

不包含重复元素的集合。 更正式地，集合不包含一对元素e1和e2 ，使得e1.equals(e2) ，并且最多一个空元素。 正如其名称所暗示的那样，这个接口模拟了数学集抽象

Set 接口完全继承自 Collection，并无其他扩展（故此不罗列源码）

4.1、HashSet

基于 hashCode 值计算元素存放位置，其内部就是由一个 HashMap 进行维护

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{private transient HashMap<E,Object> map;// 要与背景映射中的对象关联的虚拟值private static final Object PRESENT = new Object();/* 构造一个新的空集合；支持 HashMap 实例具有默认初始容量（16）和负载因子（0.75）*/public HashSet() {map = new HashMap<>();}/*** 构造包含指定集合中元素的新集合* HashMap 是使用默认加载因子（0.75）创建的，初始容量足以包含指定集合中的元素*/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 实例具有指定的初始容量和默认负载因子（0.75）*/public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}/*** 构造一个新的空链接哈希集（此包私有构造函数仅由LinkedHashSet使用）* 支持HashMap实例是具有指定初始容量和指定负载因子的LinkedHashMap*/HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}/* 返回此集合中元素的迭代器（元素没有特定顺序返回）*/public Iterator<E> iterator() {return map.keySet().iterator();}/* 返回此集合中的元素数（其基数）*/public int size() {return map.size();}/* 如果此集合不包含元素，则返回 true */public boolean isEmpty() {return map.isEmpty();}/* 如果此集合包含指定元素，则返回 true */public boolean contains(Object o) {return map.containsKey(o);}/* 如果指定元素尚未存在，则将其添加到此集合 */public boolean add(E e) {return map.put(e, PRESENT)==null;}/* 从该集合中删除指定的元素（如果存在）*/public boolean remove(Object o) {return map.remove(o)==PRESENT;}/* 从该集合中删除所有元素（此调用返回后，集合将为空）*/public void clear() {map.clear();}/* 返回此 HashSet 实例的浅拷贝：元素本身不被克隆 */@SuppressWarnings("unchecked")public Object clone() {try {HashSet<E> newSet = (HashSet<E>) super.clone();newSet.map = (HashMap<E, Object>) map.clone();return newSet;} catch (CloneNotSupportedException e) {throw new InternalError(e);}}/* 将此 HashSet 实例的状态保存到流（即，序列化）*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// Write out HashMap capacity and load factors.writeInt(map.capacity());s.writeFloat(map.loadFactor());// Write out sizes.writeInt(map.size());// Write out all elements in the proper order.for (E e : map.keySet())s.writeObject(e);}/* 从流中重构 HashSet 实例（即反序列化）*/private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// Read capacity and verify non-negative.int capacity = s.readInt();if (capacity < 0) {throw new InvalidObjectException("Illegal capacity: " +capacity);}// Read load factor and verify positive and non NaN.float loadFactor = s.readFloat();if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new InvalidObjectException("Illegal load factor: " +loadFactor);}// Read size and verify non-negative.int size = s.readInt();if (size < 0) {throw new InvalidObjectException("Illegal size: " +size);}// Set the capacity according to the size and load factor ensuring that// the HashMap is at least 25% full but clamping to maximum capacity.capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),HashMap.MAXIMUM_CAPACITY);// Create backing HashMapmap = (((HashSet<?>)this) instanceof LinkedHashSet ?new LinkedHashMap<E,Object>(capacity, loadFactor) :new HashMap<E,Object>(capacity, loadFactor));// Read in all elements in the proper order.for (int i=0; i<size; i++) {@SuppressWarnings("unchecked")E e = (E) s.readObject();map.put(e, PRESENT);}}/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* set.** <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and* {@link Spliterator#DISTINCT}.  Overriding implementations should document* the reporting of additional characteristic values.** @return a {@code Spliterator} over the elements in this set* @since 1.8*/public Spliterator<E> spliterator() {return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);}
}

4.2、TreeSet

红黑树；基于排列顺序实现元素不重复，TreeSet实现了 SortedSet 接口，集合元素可自动排序

如果TreeSet没有指定元素的比较规则（Comparator），元素类必须实现比较规则（Comparable ）

（因为二叉查找树的基本规则是左<根<右）

4.2.1、Comparable > compareTo

元素类必须实现比较规则

Comparable：可比较的

public class Book implements Comparable<Book>{@Overridepublic int compareTo(Book o) {int n1 = this.price - o1.getPrice();int n2 = this.name.compareTo(o2.getName());return n1 == 0 ? n2 : n1;}
}

4.2.2、Comparator > compare

TreeSet指定元素的比较规则

Comparator ：实现定制比较（比较器）

// 创建集合并指定比较规则
TreeSet<Book> treeSet = new TreeSet<>(new Comparator<Book>(){@Overridepublic int compare(Book o1, Book o2) {int n1 = o1.getPrice() - o2.getPrice();int n2 = o1.getName().compareTo(o2.getName());return n1 == 0 ? n2 : n1;}
});

4.3、HashSet、TreeSet 区别：

1. TreeSet 是红黑树实现的，Treeset中的数据是自动排好序的，不允许放入null值
2. HashSet 是哈希表实现的，HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束
3. HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashCode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

---

5、Map 精简类图

键值对存储（key value）

区别：

• HashMap 键值对存储，键重复就直接覆盖
• TreeMap 可以实现有序：实现 Comparetor 重写 compare方法（要想排序 key不能是null）
• HashTable 实现线程同步

---

6、Map

6.1、Map 接口

package java.util;import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;public interface Map<K,V> {// 查询操作/*** 返回此映射中的键值映射数. * 如果映射包含多于 Integer.MAX_VALUE，返回 Integer.MAX_VALUE*/int size();/* 如果此映射不包含键值映射，则返回 true */boolean isEmpty();/* 如果此映射包含指定键的映射，则返回 true */boolean containsKey(Object key);/* 如果此映射将一个或多个键映射到指定值，则返回 true */boolean containsValue(Object value);/* 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null */V get(Object key);// 修改操作/*** 插入操作（将指定值与此映射中的指定键相关联）.* 如果映射先前包含键的映射，则旧值将替换为指定值.*/V put(K key, V value);/* 删除操作（如果存在键，则从此映射中删除键的映射）*/V remove(Object key);// 批量操作/* 批量插入（将指定映射的所有映射复制到此映射）*/void putAll(Map<? extends K, ? extends V> m);/* 清空映射（从此映射中删除所有映射，此调用返回后，映射将为空）*/void clear();// 视图/* 返回此映射中包含的键的{@link Set}视图 */Set<K> keySet();/* 返回此映射中包含的值的{@link Collection}视图 */Collection<V> values();/* 返回此映射中包含的映射的{@link Set}视图 */Set<Map.Entry<K, V>> entrySet();/* A map entry (key-value pair) */interface Entry<K,V> {/* 返回与此项对应的键 */K getKey();/* 返回与此项对应的值 */V getValue();/* 将与此条目对应的值替换为指定值 */V setValue(V value);/* 将指定的对象与此项进行相等性比较 */boolean equals(Object o);/* 返回此映射项的哈希代码值 */int hashCode();/* 返回一个比较器，该比较器按键的自然顺序比较{@link Map.Entry} */public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {return (Comparator<Map.Entry<K, V>> & Serializable)(c1, c2) -> c1.getKey().compareTo(c2.getKey());}/* 返回一个比较器，该比较器按自然顺序比较{@link Map.Entry}的值 */public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {return (Comparator<Map.Entry<K, V>> & Serializable)(c1, c2) -> c1.getValue().compareTo(c2.getValue());}/* 返回一个比较器，该比较器使用给定的｛@link comparator｝按键比较｛@link Map.Entry｝*/public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {Objects.requireNonNull(cmp);return (Comparator<Map.Entry<K, V>> & Serializable)(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());}/* 返回一个比较器，该比较器使用给定的｛@link比较器｝按值比较｛@link Map.Entry｝*/public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {Objects.requireNonNull(cmp);return (Comparator<Map.Entry<K, V>> & Serializable)(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());}}// 比较和散列/* 将指定的对象与此映射进行相等性比较 */boolean equals(Object o);/* 返回此映射的哈希代码值 */int hashCode();// 默认方法/* 返回指定键映射到的值，如果此映射不包含键的映射，则返回｛@code defaultValue｝*/default V getOrDefault(Object key, V defaultValue) {V v;return (((v = get(key)) != null) || containsKey(key))? v: defaultValue;}/* 对该映射中的每个条目执行给定的操作，直到所有条目都已处理完毕或该操作引发异常 */default void forEach(BiConsumer<? super K, ? super V> action) {Objects.requireNonNull(action);for (Map.Entry<K, V> entry : entrySet()) {K k;V v;try {k = entry.getKey();v = entry.getValue();} catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.throw new ConcurrentModificationException(ise);}action.accept(k, v);}}/*** 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都已处理或函数抛出异常为止* 函数引发的异常会被中继到调用方*/default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {Objects.requireNonNull(function);for (Map.Entry<K, V> entry : entrySet()) {K k;V v;try {k = entry.getKey();v = entry.getValue();} catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.throw new ConcurrentModificationException(ise);}// ise thrown from function is not a cme.v = function.apply(k, v);try {entry.setValue(v);} catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.throw new ConcurrentModificationException(ise);}}}/*** 如果指定的键尚未与值关联（或映射到｛@code null｝），* 则将其与给定值关联并返回｛@code null｝，否则返回当前值*/default V putIfAbsent(K key, V value) {V v = get(key);if (v == null) {v = put(key, value);}return v;}/* 仅当指定键当前映射到指定值时，才删除该项 */default boolean remove(Object key, Object value) {Object curValue = get(key);if (!Objects.equals(curValue, value) ||(curValue == null && !containsKey(key))) {return false;}remove(key);return true;}/* 仅当当前映射到指定值时，才替换指定键的项 */default boolean replace(K key, V oldValue, V newValue) {Object curValue = get(key);if (!Objects.equals(curValue, oldValue) ||(curValue == null && !containsKey(key))) {return false;}put(key, newValue);return true;}/* 仅当指定键当前映射到某个值时，才替换该项 */default V replace(K key, V value) {V curValue;if (((curValue = get(key)) != null) || containsKey(key)) {curValue = put(key, value);}return curValue;}/*** 如果指定的键尚未与值关联（或映射到｛@code null｝），* 则尝试使用给定的映射函数计算其值并将其输入此映射，除非｛@code null｝*/default V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) {Objects.requireNonNull(mappingFunction);V v;if ((v = get(key)) == null) {V newValue;if ((newValue = mappingFunction.apply(key)) != null) {put(key, newValue);return newValue;}}return v;}/* 如果指定键的值存在且不为空，则尝试计算给定键及其当前映射值的新映射 */default V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {Objects.requireNonNull(remappingFunction);V oldValue;if ((oldValue = get(key)) != null) {V newValue = remappingFunction.apply(key, oldValue);if (newValue != null) {put(key, newValue);return newValue;} else {remove(key);return null;}} else {return null;}}/* 尝试计算指定键及其当前映射值的映射（如果没有当前映射，则为{@code null}）*/default V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {Objects.requireNonNull(remappingFunction);V oldValue = get(key);V newValue = remappingFunction.apply(key, oldValue);if (newValue == null) {// delete mappingif (oldValue != null || containsKey(key)) {// something to removeremove(key);return null;} else {// nothing to do. Leave things as they were.return null;}} else {// add or replace old mappingput(key, newValue);return newValue;}}/*** 如果指定的键尚未与值关联或与空关联，则将其与给定的非空值关联.* 否则，将关联值替换为给定重映射函数的结果，如果结果为｛@code null｝，* 则将其删除。当组合键的多个映射值时，此方法可能有用*/default V merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) {Objects.requireNonNull(remappingFunction);Objects.requireNonNull(value);V oldValue = get(key);V newValue = (oldValue == null) ? value :remappingFunction.apply(oldValue, value);if(newValue == null) {remove(key);} else {put(key, newValue);}return newValue;}
}

6.2、遍历

6.2.1、keySet 遍历（效率低）

// Set<T> keySet = map.keySet();
for(T key : map.keySet()){ // 直接简写System.out.println(key + "--" + ,ap.get(key))
}

6.2.2、entrySet 遍历（效率高）

// Set<Entry<K, V>> set = map.entrySet();
for(Entry<K, V> s : map.entrySet()) { // 直接简写System.out.println(s);// 获得 key 和 valueSystem.out.println(s.getKey() + "--" + s.getValue());
}

---

7、Map > HashMap

存储结构：数组 +链表 +红黑树
线程不安全，运行效率快，key和 value可为 null

基于哈希表的实现的Map接口。 此实现提供了所有可选的 Map操作

7.1、总结

1. Hashmap刚创建时，tab1e=nu11，size=0 为了节省空间；当添加第一个元素时，table容量调整为16
2. 当元素个数大于阈值 ( 16 × 0.75 = 12) 时，会进行扩容，扩容后大小为 oldCap << 1 。目的是减少调整元素的个数
3. jdk1.8，当每个链表长度大于8，并且数组元素个数大于等于64时，会调整为红黑树，目的提高执行效率
4. jdk1.8，当红黑树节点小于 6 时，调整成链表
5. jdk1.8以前，链表时头插入，jdk1.8 以后是尾插入

7.2、HashMap 源码

package java.util;import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {/* 默认初始容量16-必须是2的幂 */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 最大容量，如果任何一个带有参数的构造函数隐式指定了更高的值，则使用.* 必须是2的幂 且 <= 1<<30*/static final int MAXIMUM_CAPACITY = 1 << 30;/* 构造函数中未指定时使用的负载因子 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 链表转红黑树阈值（使用树而不是列表的容器计数阈值）* 当将元素添加到至少具有这么多节点的容器时，容器将转换为树。该值必须大于2，* 且应至少为8，以符合树移除中关于收缩后转换回普通箱的假设.*/static final int TREEIFY_THRESHOLD = 8;/*** 红黑树转链表阈值* 用于在调整大小操作期间取消（拆分）存储箱的存储箱计数阈值.* 应小于 TREEIFY_THRESHOLD，且最多为6，以便在移除时进行收缩检测.*/static final int UNTREEIFY_THRESHOLD = 6;/*** 可将存储箱树形化的最小表容量.* （否则，如果bin中的节点太多，则会调整表的大小）* 应至少为 4 × TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突.*/static final int MIN_TREEIFY_CAPACITY = 64;/*** 基本哈希bin节点，用于大多数条目* （参见下面的TreeNode子类，以及LinkedHashMap中的条目子类）*/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;}}/* ---------------- 静态实用程序 -------------- *//* 根据 key 计算 hash 值 */static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}/* 如果x的类的形式为"class C implements Comparable<C>"，则返回x的类，否则为null */static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;if ((c = x.getClass()) == String.class) // bypass checksreturn c;if ((ts = c.getGenericInterfaces()) != null) {for (int i = 0; i < ts.length; ++i) {if (((t = ts[i]) instanceof ParameterizedType) &&((p = (ParameterizedType)t).getRawType() ==Comparable.class) &&(as = p.getActualTypeArguments()) != null &&as.length == 1 && as[0] == c) // type arg is creturn c;}}}return null;}/* 如果x与kc匹配（k在可比类中被筛选），则返回 k.compareTo（x），否则为0 */@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparablestatic int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 :((Comparable)k).compareTo(x));}/*** 返回给定目标容量的二次幂.* [ 不管你给的容量是多少，这里都会处理成大于入参最接近的 2的次幂 ]*/static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}/* ---------------- Fields -------------- *//*** 该表在首次使用时初始化，并根据需要调整大小.* 分配时，长度总是2的幂（在某些操作中，我们还允许长度为零，以允许目前不需要的自举机制）*/transient Node<K,V>[] table;/*** 保存缓存的 entrySet().* 注意，AbstractMap 字段用于 keySet() 和 values()*/transient Set<Map.Entry<K,V>> entrySet;/* 此映射中包含的键值映射数 */transient int size;/*** 此 HashMap在结构上被修改的次数.* 结构修改是指更改 HashMap 中映射的数量或以其他方式修改其内部结构的次数.* 此字段用于使 HashMap 集合视图上的迭代器快速失败.* （参见 ConcurrentModificationException）*/transient int modCount;/* 要调整大小的下一个大小值（容量*负载系数）*/int threshold;/* 哈希表的加载因子 */final float loadFactor;/* ---------------- Public operations -------------- *//* 使用指定的初始容量和负载系数构造一个空的 HashMap */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);}/* 使用指定的初始容量和默认负载因子（0.75）构造一个空的 HashMap */public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}/* 使用默认初始容量（16）和默认负载系数（0.75）构造一个空的 HashMap */public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/*** 构造一个新的 HashMap 并使用与指定 Map 相同的映射.* HashMap 是使用默认负载因子（0.75）创建的，初始容量足以在指定的 Map.*/public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}/* 实现 Map.putAll 和 Map构造器 */final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-sizefloat 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);}}}/* 返回此映射中的键值映射数 */public int size() {return size;}/* 如果此映射不包含键值映射，则返回 true */public boolean isEmpty() {return size == 0;}/* 返回指定键映射到的值，如果此映射不包含键的映射，则返回｛@code null｝*/public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}/* 实现 Map.get 和相关方法 */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 && // 始终检查第一个节点((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;}/* 如果此映射包含指定键的映射，则返回 true */public boolean containsKey(Object key) {return getNode(hash(key), key) != null;}/* 将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧值 */public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/* 实现 Map.put 及相关方法 */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);// 第一次扩容： 7 >= 8 - 1 : 7说明当前链表长度已经是9了！if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // 键的现有映射V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}/*** 初始化表大小或将表大小加倍.* 如果为空，则根据字段阈值中保持的初始容量目标进行分配.* 否则，因为我们使用的是二次幂展开，所以每个bin中的元素必须保持在相同索引，* 或者在新表中以二次幂偏移量移动.*/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 thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = 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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}/* 在给定哈希的索引处替换bin中的所有链接节点，除非表太小，在这种情况下，改为调整大小 */final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}/*** 将指定映射的所有映射复制到此映射.将指定映射的所有映射复制到此映射* 这些映射将替换此映射对于当前指定映射中的任何键所具有的任何映射.*/public void putAll(Map<? extends K, ? extends V> m) {putMapEntries(m, true);}/* 从此映射中删除指定键的映射（如果存在）*/public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}/* 实现 Map.remove 和相关方法 */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;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}/*** 从此映射中删除所有映射.* 此调用返回后，映射将为空.*/public void clear() {Node<K,V>[] tab;modCount++;if ((tab = table) != null && size > 0) {size = 0;for (int i = 0; i < tab.length; ++i)tab[i] = null;}}/* 如果此映射将一个或多个键映射到指定值，则返回 true */public boolean containsValue(Object value) {Node<K,V>[] tab; V v;if ((tab = table) != null && size > 0) {for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next) {if ((v = e.value) == value ||(value != null && value.equals(v)))return true;}}}return false;}/* 返回此映射中包含的键的{@link Set}视图 */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 (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.key);}if (modCount != mc)throw new ConcurrentModificationException();}}}/* 返回此映射中包含的值的{@link Collection}视图 */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 (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.value);}if (modCount != mc)throw new ConcurrentModificationException();}}}/* 返回此映射中包含的映射的{@link 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 (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e);}if (modCount != mc)throw new ConcurrentModificationException();}}}// JDK8 映射扩展方法的重写@Overridepublic V getOrDefault(Object key, V defaultValue) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;}@Overridepublic V putIfAbsent(K key, V value) {return putVal(hash(key), key, value, true, true);}@Overridepublic boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) != null;}@Overridepublic boolean replace(K key, V oldValue, V newValue) {Node<K,V> e; V v;if ((e = getNode(hash(key), key)) != null &&((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {e.value = newValue;afterNodeAccess(e);return true;}return false;}@Overridepublic V replace(K key, V value) {Node<K,V> e;if ((e = getNode(hash(key), key)) != null) {V oldValue = e.value;e.value = value;afterNodeAccess(e);return oldValue;}return null;}@Overridepublic V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) {if (mappingFunction == null)throw new NullPointerException();int hash = hash(key);Node<K,V>[] tab; Node<K,V> first; int n, i;int binCount = 0;TreeNode<K,V> t = null;Node<K,V> old = null;if (size > threshold || (tab = table) == null ||(n = tab.length) == 0)n = (tab = resize()).length;if ((first = tab[i = (n - 1) & hash]) != null) {if (first instanceof TreeNode)old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);else {Node<K,V> e = first; K k;do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {old = e;break;}++binCount;} while ((e = e.next) != null);}V oldValue;if (old != null && (oldValue = old.value) != null) {afterNodeAccess(old);return oldValue;}}V v = mappingFunction.apply(key);if (v == null) {return null;} else if (old != null) {old.value = v;afterNodeAccess(old);return v;}else if (t != null)t.putTreeVal(this, tab, hash, key, v);else {tab[i] = newNode(hash, key, v, first);if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}++modCount;++size;afterNodeInsertion(true);return v;}public V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {if (remappingFunction == null)throw new NullPointerException();Node<K,V> e; V oldValue;int hash = hash(key);if ((e = getNode(hash, key)) != null &&(oldValue = e.value) != null) {V v = remappingFunction.apply(key, oldValue);if (v != null) {e.value = v;afterNodeAccess(e);return v;}elseremoveNode(hash, key, null, false, true);}return null;}@Overridepublic V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {if (remappingFunction == null)throw new NullPointerException();int hash = hash(key);Node<K,V>[] tab; Node<K,V> first; int n, i;int binCount = 0;TreeNode<K,V> t = null;Node<K,V> old = null;if (size > threshold || (tab = table) == null ||(n = tab.length) == 0)n = (tab = resize()).length;if ((first = tab[i = (n - 1) & hash]) != null) {if (first instanceof TreeNode)old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);else {Node<K,V> e = first; K k;do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {old = e;break;}++binCount;} while ((e = e.next) != null);}}V oldValue = (old == null) ? null : old.value;V v = remappingFunction.apply(key, oldValue);if (old != null) {if (v != null) {old.value = v;afterNodeAccess(old);}elseremoveNode(hash, key, null, false, true);}else if (v != null) {if (t != null)t.putTreeVal(this, tab, hash, key, v);else {tab[i] = newNode(hash, key, v, first);if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}++modCount;++size;afterNodeInsertion(true);}return v;}@Overridepublic V merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) {if (value == null)throw new NullPointerException();if (remappingFunction == null)throw new NullPointerException();int hash = hash(key);Node<K,V>[] tab; Node<K,V> first; int n, i;int binCount = 0;TreeNode<K,V> t = null;Node<K,V> old = null;if (size > threshold || (tab = table) == null ||(n = tab.length) == 0)n = (tab = resize()).length;if ((first = tab[i = (n - 1) & hash]) != null) {if (first instanceof TreeNode)old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);else {Node<K,V> e = first; K k;do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {old = e;break;}++binCount;} while ((e = e.next) != null);}}if (old != null) {V v;if (old.value != null)v = remappingFunction.apply(old.value, value);elsev = value;if (v != null) {old.value = v;afterNodeAccess(old);}elseremoveNode(hash, key, null, false, true);return v;}if (value != null) {if (t != null)t.putTreeVal(this, tab, hash, key, value);else {tab[i] = newNode(hash, key, value, first);if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}++modCount;++size;afterNodeInsertion(true);}return value;}@Overridepublic void forEach(BiConsumer<? super K, ? super V> action) {Node<K,V>[] tab;if (action == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.key, e.value);}if (modCount != mc)throw new ConcurrentModificationException();}}@Overridepublic void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {Node<K,V>[] tab;if (function == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next) {e.value = function.apply(e.key, e.value);}}if (modCount != mc)throw new ConcurrentModificationException();}}/* ------------------------------------------------------------ */// 克隆和序列化/* 返回此 HashMap 实例的浅拷贝：键和值本身不被克隆 */@SuppressWarnings("unchecked")@Overridepublic Object clone() {HashMap<K,V> result;try {result = (HashMap<K,V>)super.clone();} catch (CloneNotSupportedException e) {// 这不应该发生，因为我们是可克隆的throw new InternalError(e);}result.reinitialize();result.putMapEntries(this, false);return result;}// 序列化哈希集时也使用这些方法final float loadFactor() { return loadFactor; }final int capacity() {return (table != null) ? table.length :(threshold > 0) ? threshold :DEFAULT_INITIAL_CAPACITY;}/* 将 HashMap 实例的状态保存到流（即序列化）*/private void writeObject(java.io.ObjectOutputStream s)throws IOException {int buckets = capacity();// Write out the threshold, loadfactor, and any hidden stuffs.defaultWriteObject();s.writeInt(buckets);s.writeInt(size);internalWriteEntries(s);}/* 从流中重构{@code HashMap}实例（即反序列化）*/private void readObject(java.io.ObjectInputStream s)throws IOException, ClassNotFoundException {// Read in the threshold (ignored), loadfactor, and any hidden stuffs.defaultReadObject();reinitialize();if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new InvalidObjectException("Illegal load factor: " +loadFactor);s.readInt();                // Read and ignore number of bucketsint mappings = s.readInt(); // Read number of mappings (size)if (mappings < 0)throw new InvalidObjectException("Illegal mappings count: " +mappings);else if (mappings > 0) { // (if zero, use defaults)// Size the table using given load factor only if within// range of 0.25...4.0float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);float fc = (float)mappings / lf + 1.0f;int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?DEFAULT_INITIAL_CAPACITY :(fc >= MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY :tableSizeFor((int)fc));float ft = (float)cap * lf;threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?(int)ft : Integer.MAX_VALUE);@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] tab = (Node<K,V>[])new Node[cap];table = tab;// Read the keys and values, and put the mappings in the HashMapfor (int i = 0; i < mappings; i++) {@SuppressWarnings("unchecked")K key = (K) s.readObject();@SuppressWarnings("unchecked")V value = (V) s.readObject();putVal(hash(key), key, value, false, false);}}}/* ------------------------------------------------------------ */// 迭代器abstract class HashIterator {Node<K,V> next;        // next entry to returnNode<K,V> current;     // current entryint expectedModCount;  // for fast-failint index;             // current slotHashIterator() {expectedModCount = modCount;Node<K,V>[] t = table;current = next = null;index = 0;if (t != null && size > 0) { // advance to first entrydo {} while (index < t.length && (next = t[index++]) == null);}}public final boolean hasNext() {return next != null;}final Node<K,V> nextNode() {Node<K,V>[] t;Node<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();if ((next = (current = e).next) == null && (t = table) != null) {do {} while (index < t.length && (next = t[index++]) == null);}return e;}public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();current = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;}}final class KeyIterator extends HashIteratorimplements Iterator<K> {public final K next() { return nextNode().key; }}final class ValueIterator extends HashIteratorimplements Iterator<V> {public final V next() { return nextNode().value; }}final class EntryIterator extends HashIteratorimplements Iterator<Map.Entry<K,V>> {public final Map.Entry<K,V> next() { return nextNode(); }}/* ------------------------------------------------------------ */// 分离器static class HashMapSpliterator<K,V> {final HashMap<K,V> map;Node<K,V> current;          // current nodeint index;                  // current index, modified on advance/splitint fence;                  // one past last indexint est;                    // size estimateint expectedModCount;       // for comodification checksHashMapSpliterator(HashMap<K,V> m, int origin,int fence, int est,int expectedModCount) {this.map = m;this.index = origin;this.fence = fence;this.est = est;this.expectedModCount = expectedModCount;}final int getFence() { // initialize fence and size on first useint hi;if ((hi = fence) < 0) {HashMap<K,V> m = map;est = m.size;expectedModCount = m.modCount;Node<K,V>[] tab = m.table;hi = fence = (tab == null) ? 0 : tab.length;}return hi;}public final long estimateSize() {getFence(); // force initreturn (long) est;}}static final class KeySpliterator<K,V>extends HashMapSpliterator<K,V>implements Spliterator<K> {KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,int expectedModCount) {super(m, origin, fence, est, expectedModCount);}public KeySpliterator<K,V> trySplit() {int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;return (lo >= mid || current != null) ? null :new KeySpliterator<>(map, lo, index = mid, est >>>= 1,expectedModCount);}public void forEachRemaining(Consumer<? super K> action) {int i, hi, mc;if (action == null)throw new NullPointerException();HashMap<K,V> m = map;Node<K,V>[] tab = m.table;if ((hi = fence) < 0) {mc = expectedModCount = m.modCount;hi = fence = (tab == null) ? 0 : tab.length;}elsemc = expectedModCount;if (tab != null && tab.length >= hi &&(i = index) >= 0 && (i < (index = hi) || current != null)) {Node<K,V> p = current;current = null;do {if (p == null)p = tab[i++];else {action.accept(p.key);p = p.next;}} while (p != null || i < hi);if (m.modCount != mc)throw new ConcurrentModificationException();}}public boolean tryAdvance(Consumer<? super K> action) {int hi;if (action == null)throw new NullPointerException();Node<K,V>[] tab = map.table;if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {while (current != null || index < hi) {if (current == null)current = tab[index++];else {K k = current.key;current = current.next;action.accept(k);if (map.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}}}return false;}public int characteristics() {return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |Spliterator.DISTINCT;}}static final class ValueSpliterator<K,V>extends HashMapSpliterator<K,V>implements Spliterator<V> {ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,int expectedModCount) {super(m, origin, fence, est, expectedModCount);}public ValueSpliterator<K,V> trySplit() {int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;return (lo >= mid || current != null) ? null :new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,expectedModCount);}public void forEachRemaining(Consumer<? super V> action) {int i, hi, mc;if (action == null)throw new NullPointerException();HashMap<K,V> m = map;Node<K,V>[] tab = m.table;if ((hi = fence) < 0) {mc = expectedModCount = m.modCount;hi = fence = (tab == null) ? 0 : tab.length;}elsemc = expectedModCount;if (tab != null && tab.length >= hi &&(i = index) >= 0 && (i < (index = hi) || current != null)) {Node<K,V> p = current;current = null;do {if (p == null)p = tab[i++];else {action.accept(p.value);p = p.next;}} while (p != null || i < hi);if (m.modCount != mc)throw new ConcurrentModificationException();}}public boolean tryAdvance(Consumer<? super V> action) {int hi;if (action == null)throw new NullPointerException();Node<K,V>[] tab = map.table;if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {while (current != null || index < hi) {if (current == null)current = tab[index++];else {V v = current.value;current = current.next;action.accept(v);if (map.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}}}return false;}public int characteristics() {return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);}}static final class EntrySpliterator<K,V>extends HashMapSpliterator<K,V>implements Spliterator<Map.Entry<K,V>> {EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,int expectedModCount) {super(m, origin, fence, est, expectedModCount);}public EntrySpliterator<K,V> trySplit() {int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;return (lo >= mid || current != null) ? null :new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,expectedModCount);}public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {int i, hi, mc;if (action == null)throw new NullPointerException();HashMap<K,V> m = map;Node<K,V>[] tab = m.table;if ((hi = fence) < 0) {mc = expectedModCount = m.modCount;hi = fence = (tab == null) ? 0 : tab.length;}elsemc = expectedModCount;if (tab != null && tab.length >= hi &&(i = index) >= 0 && (i < (index = hi) || current != null)) {Node<K,V> p = current;current = null;do {if (p == null)p = tab[i++];else {action.accept(p);p = p.next;}} while (p != null || i < hi);if (m.modCount != mc)throw new ConcurrentModificationException();}}public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {int hi;if (action == null)throw new NullPointerException();Node<K,V>[] tab = map.table;if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {while (current != null || index < hi) {if (current == null)current = tab[index++];else {Node<K,V> e = current;current = current.next;action.accept(e);if (map.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}}}return false;}public int characteristics() {return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |Spliterator.DISTINCT;}}/* ------------------------------------------------------------ */// LinkedHashMap支持// 创建常规（非树）节点Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}// 用于从树节点到普通节点的转换Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);}// 创建树bin节点TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {return new TreeNode<>(hash, key, value, next);}// For treeifyBinTreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);}/* 重置为初始默认状态。由克隆和readObject调用 */void reinitialize() {table = null;entrySet = null;keySet = null;values = null;modCount = 0;threshold = 0;size = 0;}// 允许LinkedHashMap post操作的回调void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }// 仅从writeObject调用，以确保兼容排序.void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {Node<K,V>[] tab;if (size > 0 && (tab = table) != null) {for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next) {s.writeObject(e.key);s.writeObject(e.value);}}}}/* ------------------------------------------------------------ */// Tree bins/*** 树箱条目（扩展 LinkedHashMap）* 条目（它反过来扩展节点），因此可以用作常规节点或链接节点的扩展*/static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}/* 返回包含此节点的树的根 */final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}}/* 确保给定根是其bin的第一个节点 */static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index];if (root != first) {Node<K,V> rn;tab[index] = root;TreeNode<K,V> rp = root.prev;if ((rn = root.next) != null)((TreeNode<K,V>)rn).prev = rp;if (rp != null)rp.next = rn;if (first != null)first.prev = root;root.next = first;root.prev = null;}assert checkInvariants(root);}}/*** 使用给定的哈希和密钥查找从根p开始的节点.* kc参数在首次使用比较键时缓存 comparableClassForr(key).*/final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this;do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if (pl == null)p = pr;else if (pr == null)p = pl;else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null;}/* 调用根节点的查找 */final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);}/*** 当哈希代码相等且不可比较时，用于排序插入的平局中断实用程序.* 我们不需要一个总的顺序，只需要一个一致的插入规则来保持平衡之间的等价性.*/static int tieBreakOrder(Object a, Object b) {int d;if (a == null || b == null ||(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d;}/* 形成从该节点链接的节点树 */final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;if (root == null) {x.parent = null;x.red = false;root = x;}else {K k = x.key;int h = x.hash;Class<?> kc = null;for (TreeNode<K,V> p = root;;) {int dir, ph;K pk = p.key;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)dir = tieBreakOrder(k, pk);TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;root = balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);}/* 返回替换从该节点链接的非树节点的列表 */final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;}/* putVal 的树版本 */final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;TreeNode<K,V> root = (parent != null) ? root() : this;for (TreeNode<K,V> p = root;;) {int dir, ph; K pk;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {TreeNode<K,V> q, ch;searched = true;if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null))return q;}dir = tieBreakOrder(k, pk);}TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {Node<K,V> xpn = xp.next;TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);if (dir <= 0)xp.left = x;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;moveRootToFront(tab, balanceInsertion(root, x));return null;}}}/* 删除此调用之前必须存在的给定节点 */final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {int n;if (tab == null || (n = tab.length) == 0)return;int index = (n - 1) & hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;if (pred == null)tab[index] = first = succ;elsepred.next = succ;if (succ != null)succ.prev = pred;if (first == null)return;if (root.parent != null)root = root.root();if (root == null || root.right == null ||(rl = root.left) == null || rl.left == null) {tab[index] = first.untreeify(map);  // too smallreturn;}TreeNode<K,V> p = this, pl = left, pr = right, replacement;if (pl != null && pr != null) {TreeNode<K,V> s = pr, sl;while ((sl = s.left) != null) // find successors = sl;boolean c = s.red; s.red = p.red; p.red = c; // swap colorsTreeNode<K,V> sr = s.right;TreeNode<K,V> pp = p.parent;if (s == pr) { // p was s's direct parentp.parent = s;s.right = p;}else {TreeNode<K,V> sp = s.parent;if ((p.parent = sp) != null) {if (s == sp.left)sp.left = p;elsesp.right = p;}if ((s.right = pr) != null)pr.parent = s;}p.left = null;if ((p.right = sr) != null)sr.parent = p;if ((s.left = pl) != null)pl.parent = s;if ((s.parent = pp) == null)root = s;else if (p == pp.left)pp.left = s;elsepp.right = s;if (sr != null)replacement = sr;elsereplacement = p;}else if (pl != null)replacement = pl;else if (pr != null)replacement = pr;elsereplacement = p;if (replacement != p) {TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)root = replacement;else if (p == pp.left)pp.left = replacement;elsepp.right = replacement;p.left = p.right = p.parent = null;}TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);if (replacement == p) {  // detachTreeNode<K,V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null;}}if (movable)moveRootToFront(tab, r);}/* 将树容器中的节点拆分为上树容器和下树容器，如果现在太小，则取消处理 */final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this;// Relink into lo and hi lists, preserving orderTreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;e.next = null;if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;if (hiHead != null) // (else is already treeified)loHead.treeify(tab);}}if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead;if (loHead != null)hiHead.treeify(tab);}}}/* ------------------------------------------------------------ */// 红黑树方法，都是从CLR改编的static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> r, pp, rl;if (p != null && (r = p.right) != null) {if ((rl = p.right = r.left) != null)rl.parent = p;if ((pp = r.parent = p.parent) == null)(root = r).red = false;else if (pp.left == p)pp.left = r;elsepp.right = r;r.left = p;p.parent = r;}return root;}static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> l, pp, lr;if (p != null && (l = p.left) != null) {if ((lr = p.left = l.right) != null)lr.parent = p;if ((pp = l.parent = p.parent) == null)(root = l).red = false;else if (pp.right == p)pp.right = l;elsepp.left = l;l.right = p;p.parent = l;}return root;}static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {x.red = true;for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {if ((xp = x.parent) == null) {x.red = false;return x;}else if (!xp.red || (xpp = xp.parent) == null)return root;if (xp == (xppl = xpp.left)) {if ((xppr = xpp.right) != null && xppr.red) {xppr.red = false;xp.red = false;xpp.red = true;x = xpp;}else {if (x == xp.right) {root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateRight(root, xpp);}}}}else {if (xppl != null && xppl.red) {xppl.red = false;xp.red = false;xpp.red = true;x = xpp;}else {if (x == xp.left) {root = rotateRight(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateLeft(root, xpp);}}}}}}static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {for (TreeNode<K,V> xp, xpl, xpr;;)  {if (x == null || x == root)return root;else if ((xp = x.parent) == null) {x.red = false;return x;}else if (x.red) {x.red = false;return root;}else if ((xpl = xp.left) == x) {if ((xpr = xp.right) != null && xpr.red) {xpr.red = false;xp.red = true;root = rotateLeft(root, xp);xpr = (xp = x.parent) == null ? null : xp.right;}if (xpr == null)x = xp;else {TreeNode<K,V> sl = xpr.left, sr = xpr.right;if ((sr == null || !sr.red) &&(sl == null || !sl.red)) {xpr.red = true;x = xp;}else {if (sr == null || !sr.red) {if (sl != null)sl.red = false;xpr.red = true;root = rotateRight(root, xpr);xpr = (xp = x.parent) == null ?null : xp.right;}if (xpr != null) {xpr.red = (xp == null) ? false : xp.red;if ((sr = xpr.right) != null)sr.red = false;}if (xp != null) {xp.red = false;root = rotateLeft(root, xp);}x = root;}}}else { // symmetricif (xpl != null && xpl.red) {xpl.red = false;xp.red = true;root = rotateRight(root, xp);xpl = (xp = x.parent) == null ? null : xp.left;}if (xpl == null)x = xp;else {TreeNode<K,V> sl = xpl.left, sr = xpl.right;if ((sl == null || !sl.red) &&(sr == null || !sr.red)) {xpl.red = true;x = xp;}else {if (sl == null || !sl.red) {if (sr != null)sr.red = false;xpl.red = true;root = rotateLeft(root, xpl);xpl = (xp = x.parent) == null ?null : xp.left;}if (xpl != null) {xpl.red = (xp == null) ? false : xp.red;if ((sl = xpl.left) != null)sl.red = false;}if (xp != null) {xp.red = false;root = rotateRight(root, xp);}x = root;}}}}}/* 递归不变检验 */static <K,V> boolean checkInvariants(TreeNode<K,V> t) {TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,tb = t.prev, tn = (TreeNode<K,V>)t.next;if (tb != null && tb.next != t)return false;if (tn != null && tn.prev != t)return false;if (tp != null && t != tp.left && t != tp.right)return false;if (tl != null && (tl.parent != t || tl.hash > t.hash))return false;if (tr != null && (tr.parent != t || tr.hash < t.hash))return false;if (t.red && tl != null && tl.red && tr != null && tr.red)return false;if (tl != null && !checkInvariants(tl))return false;if (tr != null && !checkInvariants(tr))return false;return true;}}}

---

8、Map > HashTable

基本不用了，线程安全（操作方法使用 synchronized 修饰），运行效率慢，key和 value不允许 null

---

9、Map > HashTable > Properties

HashTable 的子类

要求 key 和 value 都是 String；通常用于配置文件的读取（ 熟知 Spring 框架的小伙伴一定不陌生）

Properties类表示一组持久的属性。 Properties可以保存到流中或从流中加载。 属性列表中的每个键及其对应的值都是一个字符串。

---

10、Map > TreeSet

存储结构：红黑树

实现了 SortedMap 接口（Map的子接口），可对 key 自动排序

排序类似 TreeSet，可直接看 4.2

---

11、Collections 工具类

集合工具类，定义了除存取以外的集合常用方法

此类仅由静态方法组合或返回集合。 它包含对集合进行操作的多态算法，“包装器”，返回由指定集合支持的新集合，以及其他一些可能的和最终的。

11.1、常用方法

1. public static void reverse(List<?> list) ：反转集合中元素顺序
2. public static void shuffle(List<?> list) ：随机重置集合元素序列
3. public static void sort(List<T> list) ：升序排序（元素必须实现Comparable接口）
4. public static void reverse(List<?> list) ：反转指定列表中元素的顺序