基于 jdk8 🔗 https://docs.oracle.com/javase/8/docs/api/index.html
Collection概览
Collection
集合层次结构中的根接口。集合表示一组对象，称为其元素。一些集合允许重复的元素，而另一些则不允许。一些是有序的，而其他则是无序的。 JDK不提供此接口的任何直接实现：它提供更具体的子接口（例如 Set和 List）的实现。所有通用的 Collection 实现类都应提供两个“标准”构造函数：一个void（无参数）构造函数（用于创建一个空集合）和一个带有单个参数类型的构造函数 Collection，它将创建一个新集合，其元素与其参数相同。不同的集合实现类对包含的元素有不同的限制。线程安全由实现者自己保证。对于集合直接或间接包含自身的自引用实例，某些执行集合的递归遍历的集合操作可能会失败。这包括 clone()，equals()，hashCode()和 toString() 方法。实现可以有选择地处理自引用场景，但是大多数当前实现不这样做。
AbstractCollection
此类提供了 Collection 接口的基本实现，以最大程度地减少实现新的集合所需的工作。
如要要实现一个不可变集合，只需要实现类重写iterator和size方法。iterator必须要实现hasNext和next方法。如果要实现一个可变集合，实现类必须要重写add方法。iterator必须要实现remove方法。
集合实现类应该提供一个无参构造器和一个接受Collection的初始化构造器。
AbstractCollection中提供的所有实现都是基于iterator实现。
List
有序集合（也称为序列）。该接口可以精确控制列表中每个元素的插入位置。用户可以通过其整数索引（列表中的位置）访问元素，并在列表中搜索元素。
与集合不同，列表通常允许重复的元素，不限制具体的实现类允许多个null元素。
该接口提供了一个特殊的迭代器，称为 ListIterator，它允许元素插入和替换及双向访问，提供了一种方法来获取从列表中指定位置开始的列表迭代器。
List接口提供了两种方法来有效地在列表中的任意点插入和删除多个元素。
注意：如果列表允许添加自身，hashCode方法会由于循环嵌套抛出StackOverflowError。因此所有依赖equals的方法都会受到影响
RandomAccess
此接口表示其实现类可以很快的恒定时间通过坐标访问元素，比如 ArrayList实现了此接口而 LinkedList没有实现。
AbstractList
此类提供 List 接口的基本实现，以最大程度地减少实现由“随机访问”数据存储（例如数组）支持的该接口所需的工作。对于顺序访问数据（例如链表），应优先使用 AbstractSequentialList 。
要实现一个不可修改的列表，只需要重写get/set方法的实现。
要实现一个可修改的列表，须另外重写 set方法（否则会抛出 UnsupportedOperationException）。如果列表是可变大小的，则必须另外重写 add 和 remove 方法。
ArrayList
List接口的数组实现。允许null。除了实现 List接口之外，应用程序可以通过使用 esureCapacity 操作在添加大量元素之前增加ArrayList实例的容量。这可以减少增量重新分配的数量。
此实现未同步。 如果多个线程同时访问 ArrayList实例，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。（结构修改是添加或删除一个或多个元素或显式调整后备数组大小的任何操作；仅设置元素的值不是结构修改。）如果要同步需要使用 ` Collections.synchronizedList 进行包装。List list = Collections.synchronizedList(new ArrayList(…));`。此类在创建迭代器后任何操作都会判断modCount值是否改变来快速失败。在进行add、remove等操作时会递增modCount。
ArrayList由于使用的是数组，需要有一套扩容机制。其实现方式为：默认创建时使用一个哨兵对象，长度为0的数组。第一次扩容的默认大小为10。之后默认扩容大小为当前长度除2，但是不会超过 Integer.MAX_VALUE - 8。但是当一次扩容所需的大小超过默认大小时，比如addAll添加很多元素，就会直接扩到所需的大小，这时允许超过 Integer.MAX_VALUE - 8，所以在一些JVM上会有OOM风险。ArrayList的扩容代码在JDK8之前逻辑混乱，表述不清，虽然在JDK11中重构了一次，但是描述也很冗余。直到JDK17中的实现才真正清晰明确。
ArrayList中的元素插入、删除、扩容等所有需要移动元素的方法，都是使用 Arrays.copyOf方法实现。
ArrayList中有两个内部类 Itr和 ListItr用于实现迭代器，但其还是基于ArrayList内部数据实现，只是缓存了一些迭代指针等数据。
ArrayList的subList方法返回的并不是一个新的ArrayList，还是其内部类 SubList。SubList也是基于ArrayList的原始内部数据实现，只作为一个视图，只是缓存了当前subList的边界等数据。因此在使用SubList的时候需要谨慎。
SubList
AbstractList 的内部类、实现类。内部保存了子List的长度和父List的长度子列表与父列表的数据修改会互相影响，子列表的长度变化会影响父列表，但是父列表的长度变化会导致子列表执行方法抛异常。
RandomAccessSubList
AbstractList 的内部类、实现类。继承 SubList，由于 SubList没有直接实现 RandomAccess接口，所以其作用只是标识一个实现了 RandomAccess接口的 SubList。
AbstractSequentialList
此类提供了 List 接口的基本实现，以最大程度地减少实现由“顺序访问”数据存储（例如链表）支持的该接口所需的工作。对于随机访问数据（例如数组），应优先使用 AbstractList。
LinkedList
List和 Deque 接口的双链表实现。允许null元素。支持peek、pop、push、offer、poll等操作。
其根据索引查找数据的操作会判断当前索引落在中间之前，还是中间之后，然后选择从前或从后遍历重找元素。
其根据数据查找索引的操作，需要从前往后遍历。
此实现未同步，如果需要同步应使用 Collections.synchronizedList来进行包装。List list = Collections.synchronizedList(new LinkedList(...));
Vector
与ArrayList的不同是，所有修改的方法上都有 synchronized 修饰。每次扩容默认扩容一倍。
Stack
所述Stack类表示对象的后进先出（LIFO）堆栈。它继承了 Vector类，并通过Vector提供的方法扩展了push、pop、peek方法，这些操作允许将Vector视为堆栈。首次创建堆栈时，它不包含任何项目。在需要堆栈时应优先使用 Deque类。 Deque<Integer> stack = new ArrayDeque<Integer>();。
Set
不包含重复元素的集合。最多包含一个空元素。❗特别注意集合元素中不能有可变对象。
AbstractSet
此类提供Set 接口的基本实现，以最大程度地减少实现此接口所需的工作。通过扩展此类来实现集合的过程与通过扩展 AbstractCollection 来实现 Collection 的过程相同，不同之处在于，此类的子类中的所有方法和构造函数都必须服从 Set 接口施加的附加约束（例如， add方法不得允许将一个对象的多个实例添加到集合中）。
HashSet
依赖HashMap实现的HashSet。内部有一个全局静态哨兵对象来当做HashMap的value。其中的一个构造函数提供初始化容量 (Math.max((int) (param.size()/.75f) + 1, 16))。
LinkedHashSet
继承了HashSet，HashSet中为LinkedHashSet专门提供了一个构造方法，使用 LinkedHashMap作为内部存储来实现LinkedHashSet ：
// dummy参数没有使用，只是个构造函数多态辅助标识
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
EnumSet
不允许空元素。用于枚举类型的 Set实现，枚举集中的所有元素都必须来自创建集时显式或隐式指定的单个枚举类型。枚举集在内部表示为位向量。这种表示非常紧凑和高效。此类的时空性能应足够好，以使其可以用作传统的基于int的“位标志”的高质量，类型安全的替代方法。如果批量操作（例如containsAll和keepAll）的参数也是一个枚举集，它们也应该非常快速地以恒定时间运行。EnumSet不同步。
使用以下方法创建新的空集合：
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = SharedSecrets.getJavaLangAccess()
.getEnumConstantsShared(elementType);
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);
}
JumboEnumSet
用于EnumSet的私有实现类，用于“巨大”枚举类型(即元素多于64个的元素)
private long elements[];
private int size = 0;
RegularEnumSet
枚举集的私有实现类，用于“常规大小”枚举类型(即枚举常数为64或更少的枚举)
private long elements = 0L;
SortedSet
定义有序Set的接口。subSet的操作是前闭后开，如果需要前开或者后闭请参考 https://stackoverflow.com/questions/17380051/adding-0-to-a-subset-range-end。
NavigableSet
提供一种可以在Set内部进行搜索查询的接口。提供了lower、floor、ceiling和higher方法返回小于、小于或等于、大于或等于和大于给定元素的元素，如果没有这样的元素则返回null。可以按升序或降序访问遍历NavigableSet。正序的视图性能可以比降序的快。
该接口还定义了pollFirst和pollLast方法，它们返回和删除最低和最高元素，如果存在，则返回null。方法subSet、headSet和tailSet与类似命名的SortedSet方法的不同之处在于接受描述下限和上限是包含还是排除的附加参数。任何NavigableSet的子集都必须实现NavigableSet接口。
在允许null元素的实现中，导航方法的返回值可能不明确。但是，即使在这种情况下，也可以通过检查 contains(null)来消除歧义。为避免此类问题，鼓励此接口的实现不允许插入null元素。（请注意， Comparable元素的排序集本质上不允许null 。）
方法 subSet(E, E)、headSet(E)和 tailSet(E)被指定返回SortedSet以允许对SortedSet的现有实现进行兼容改造以实现NavigableSet，但鼓励此接口的扩展和实现覆盖这些方法返回NavigableSet。
Queue
设计用于在处理之前容纳元素的集合。除了基本的收集操作外，队列还提供其他插入，提取和检查操作。这些方法中的每一种都以两种形式存在：一种在操作失败时引发异常，另一种返回一个特殊值（根据操作而为null或false）。插入操作的后一种形式是专为与容量受限的 Queue实现一起使用而设计的；在大多数实现中，插入操作不会失败。该接口未定义阻塞队列的方法。不允许插入空值，因为poll方法空值认为不包含任何元素。
| Throws exception | Returns special value | |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
AbstractQueue
此类提供某些 Queue 操作的基本实现。不允许空值。
PriorityQueue
基于优先级堆的无边界优先级队列。里面的元素自然排序，或者创建时提供的 Comparator。不允许插入空值，即使基于自然排序依然需要元素实现比较。队列的头是最小元素，如果有多个最小元素将是其中之一。poll, remove, peek, element方法从队列头操作。队列虽然是无界的，但内部有容量来记录数组大小，会自动增长。其提供的 iterator()方法不提供有序遍历，请使用 Arrays.sort(pq.toArray())。此类线程不安全，可以使用 PriorityBlockingQueue代替。此类 ` (offer, poll, remove() and add)方法有 O(log(n))时间复杂度，remove(Object) and contains(Object) `有线性复杂度，(peek, element, and size)有常数复杂度。
Deque
支持在两端插入和删除元素的线性集合。”double ended queue”的缩写。不支持索引访问。不应该向其插入空值，一般空值意味着队列为空。
| Throws exception | Special value | Throws exception | Special value | |
|---|---|---|---|---|
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
该接口扩展了 Queue接口。当双端队列用作队列时，将导致FIFO（先进先出）行为。元素在双端队列的末尾添加，并从开头删除。
| Queue 方法 | 等效Deque方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
双端队列也可以用作LIFO（后进先出）堆栈。此接口应优先于旧 Stack类使用。当双端队列用作堆栈时，元素从双端队列的开头被压入并弹出。
| 堆叠方式 | 等效Deque方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
ArrayDeque
Deque接口的可调整大小的数组实现。阵列双端队列没有容量限制。它们会根据需要增长以支持使用。它们不是线程安全的。在没有外部同步的情况下，它们不支持多个线程的并发访问。空元素是禁止的。此类可能比 Stack用作堆栈时要快 ，并且比 LinkedList 用作队列时要快。
Map概览
Map
将键映射到值的对象。映射不能包含重复的键；每个键最多可以映射到一个值。 该接口代替了 Dictionary类，后者是一个完全抽象的类，而不是一个接口。 Map接口提供了三个集合视图，这些视图允许将Map的内容视为一组键，一组值或一组键-值映射。映射的顺序定义为映射的集合视图上的迭代器返回其元素的顺序。一些Map实现（例如TreeMap类）对其顺序做出特定的保证。其他的（例如HashMap类）则没有。 注意：如果将可变对象用作Map键，则必须格外小心。如果在对象是映射中的键的情况下以影响等值比较的方式更改对象的值，则不会指定映射的行为。
AbstractMap
Map接口的一些骨架实现。几乎需要全部重写。
HashMap
基于哈希表的Map实现类。允许null作为键或者值。不保证顺序，且不保证顺序不会发生变化。
get和put操作有恒定的时间性能，集合视图的操作（keySet、values、entrySet）迭代需要的时间与容量加上大小成正比。因此如果迭代性能很重要，初始容量不要太高或负载因子不要太低。
HashMap的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子触发扩容的阈值。当哈希表中的条目数❗超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），扩容至大约两倍（极限是1«30）的桶数。
默认负载因子 (0.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put ）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。
如果要在一个HashMap实例中存储许多映射，则创建具有足够大容量的映射将比让它根据需要执行自动重新散列以增加表来更有效地存储映射。当遇到具有相同hashcode的键时，如果键是Comparable的，会使用compare来处理。
此实现是不同步的，需要在外部进行同步。或使用 Collections.synchronizedMap。HashMap返回的视图迭代器都是快速失败的，在并发修改后，会抛出 ConcurrentModificationException。只能使用这个异常来检查错误，不能用于逻辑判断。
计算键的hash值
位运算与取余计算
为什么高位参与计算：Float的hash值问题
扩容
16的3/4=12 16的6/8=12
开放地址法和链地址法 高位参与运算 阈值可以大于1
SortedMap
进一步提供其键的总体排序的Map。通常在排序的Map创建时提供的Comparator来对地图进行排序。遍历排序后的地图的集合视图（由entrySet，keySet和values方法返回）时，将反映此顺序。