一、Arrays工具类
来自java.util.Arrays，用来处理数组的各种方法。
1.1 List asList(T… a)
用来返回由自定数组支持的固定大小列表，虽然这里返回了一个List，但是这个是Arrays中的一个内部类，这里边主要的方法有：
并没有add和remove方法，因此它是不支持add和remove方法的，是一个定长列表，不支持添加和删除，但是可以修改
注：因为参数是泛型的，所以是不能使用基础数据类型作为参数的，但是基本数据类型的数组是可以的。
1.2 void sort(int[] a)
它有一系列重载方法，包括各种基本数据类型和Object类型（实现了Comparable接口）的重载方法
1.3 int binarySearch(int[] a, int key)
binarySearch只可以在有序数组中进行查找，找到元素返回数组下标，没有则返回负数。
1.4 int[] copyOf(int[] original, int newLength)
调用System._arraycopy_实现数组copy，将原数组copy成新数组，数组长度为设置长度。
1.5 boolean equals(int[] a, int[] a2)
对比两个数组中对应位置的每个元素是否相等。
1.6 boolean deepEquals(Object[] a1, Object[] a2)
用来对比两个数组元素是否相等，主要是对比多维数组，而且任意层次嵌套数组。
1.7 void fill(int[] a, int val)
用来给数组赋值，有多种类型的重载方法
二、ArrayList类
ArrayList就是动态数组，由数组实现，支持随机访问，元素有序并且可以重复。
RandomAccess接口是一个标记接口，此接口一般用于List实现，以表示他们支持快速（O(1))的随机访问。
重要属性：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
用于第一次添加元素时是否扩展成DEFAULT_CAPACITY
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
提供快速失败方式
*/
protected transient int modCount = 0;
ArrayList默认初始容量是0，而不是10，10是第一次添加元素时，如果是默认集合，也就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么第一次会增加到10。如果是EMPTY_ELEMENTDATA，那么每次在原基础上扩大1.5倍。
2.1 boolean add(E e)
重载方法还有void add(int index, E element)
通过Arrays.cooy()进行动态数组的扩容，首先会通过ensureCapacityInternal判断确定集合大小。其中逻辑中就有上面提到的DEFAULTCAPACITY_EMPTY_ELEMENTDATA对于它的特殊判断。每次修改都会使modCount加1，这个是为了确保ArrayList迭代器使用，在并发操作中如果被修改，那么可以快速失败（类似乐观锁）
只有数组元素超过了当前长度时才会进行扩容，扩容最大可以扩容0x7fffffff，int的最大值。
可以添加null值。
修改modCount
2.2 E remove(int index)
重载方法有：boolean remove(Object o)移除**第一个查询**到的元素、boolean removeAll(Collection<?> c)移除所有集合中相关的元素（并非第一个）、boolean removeIf(Predicate<? super E> filter)移除符合条件的元素。
在remove方法中主要是应用System._arraycopy_进行元素的移除。
修改modCount
2.3 E set(int index, E element)
设置某个元素的元素。不会修改modCount。
2.4 E get(int index)
返回该位置的元素
2.5 int indexOf(Object o)
返回第一次出现该元素的下标位置，不存在返回_-1_int lastIndexOf(Object o)从后至前，第一次出现的下标位置。
2.6 Iterator iterator()
返回一个Itr内部类，属于Iterator接口的实现类，在内部通过checkForComodification()方法对expectedModCount和modCount进行检查，实现乐观锁机制。
ArrayList内部还提供了一种方式，就是ListIterator<E> listIterator()，用来生成ListItr内部类，它是Itr的子类，它相较于Itr内部类，提供了向前遍历的previous方法以及add方法。
2.7 遍历方式
除了上面Iterator以外，还有三种遍历方式，分别是for (int i = 0; i < a.size(); i++) { a.get(i); }这种直接for的，不会检验modCountvoid forEach(Consumer<? super E> action)通过lamda表达式进行，这种也会检验modCountfor (Integer s : a) { System._out_.println(s); }这种属于JDK的一种语法糖，如果通过反编译的话，依然是使用Iterator进行的遍历。
2.8 List subList(int fromIndex, int toIndex)
用来生成一个SubList类，它是一个内部类，可以看成是原集合的视图，如果对subList类进行修改和新增操作的话，那么原数组也会进行相应的操作。
2.9 int size()
返回集合的数量，并不是数组的数量。
2.10 void trimToSize()
该方法用来回收多余的内存，即一旦确定集合不再添加多余的元素后，调用该方法将数组大小刚好调整成集合元素大小。
三、LinkedList类
通过双链表实现的集合类。因为LinkedList实现Deque的原因，所以可以直接使用LinkedList作为Deque和Queue的一种声明方式，而ArrayList就不可以，只能使用ArrayDeque。
重要属性：
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
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;
}
}
链表无需预先初始化集合的长度。
3.1 boolean add(E e)
重载方法有：void addLast(E e)和add一致、void addFirst(E e)、void add(int index, E element)、boolean addAll(Collection<? extends E> c)、boolean addAll(int index, Collection<? extends E> c)在指定位置插入该集合
插入元素
3.2 E remove()
重载方法有：E removeFirst()与默认一致、E remove(int index)、boolean remove(Object o)、boolean removeFirstOccurrence(Object o)与前面remove(Object o)一致、E removeLast()、boolean removeLastOccurrence(Object o)、boolean removeAll(Collection<?> c)、boolean removeIf(Predicate<? super E> filter)
移除元素
3.3 E set(int index, E element)
替换指定位置的元素
3.4 E get(int index)
重载方法：E getFirst()、E getLast()
获取元素
3.5 遍历方式
ArrayList具备的遍历方式，Linked也同样具备，但是因为它的内部数据结果所决定的，如果使用普通for循环，那么将会导致更多时间消耗，因为它的get时间复杂度是O(N)。
可以使用迭代器，它记录的是上一个Node节点，这样访问下一个节点时，无需从头遍历。
其他和ArrayList差不多。
·
四、HashMap类
HashMap是采用链地址法来解决hash冲突，在JDK1.7中，HashMap是由数组+链表构成的，但是在JDK1.8中，HashMap是由数组+链表+红黑树构成。
// 默认最小容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
默认最大的容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
当桶bucket上节点大于这个值时转换成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
当桶Bucket节点数小于这个值时转换成链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
当集合中元素小于该值时，即使上面桶中数量超过了阈值，也不会转换成树，而是进行扩容。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
保存实际的数据
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
// 扩容的阈值，一般值为capacity * load factor，每次扩容总是之前的两倍，即2的幂数
int threshold;
/**
* The load factor for the hash table.
* 负载因子，默认值0.75，该值可以大于1，这是因为链接表的原因
* @serial
*/
final float loadFactor;
hash：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4.1 V put(K key, V value)
类似方法：void putAll(Map<? extends K, ? extends V> m)、V putIfAbsent(K key, V value)
在该方法中，如果size大于threshold，则进行扩容，调用resize()方法，其他的逻辑是根据hash值所在的桶是否有值，如果没有，则直接添加到该节点；如果有，则判断该位置应该为链表还是红黑树，进行对应的添加操作。
注意：如果是链表，当数量大于等于阈值_TREEIFY_THRESHOLD_，则转换成为红黑树；红黑树中也有相应的转为链表操作。
对于方法afterNodeAccess(Node<K,V> p)、afterNodeInsertion(boolean evict)，在HashMap中并没有具体实现，在LinkedHashMap中有相应的处理。
4.2 Node<K,V>[] resize()
在该方法中进行扩容，扩容指的是对于属性table数组的大小调整，类似于ArrayList的动态扩容，但是多了一些对于链表和红黑树的操作，这里扩容时的阈值属性是threshold。
在Map中最大可扩容的数量依然是0x7fffffff，当然这个不是指size最大是该值，而是值桶最多只有这么多。
在JDK1.8中，每次扩容都是直接扩容2倍，所以原来的元素要么在原位置，要么在原位置+原数组长度。
4.3 V remove(Object key)
类似方法：boolean remove(Object key, Object value) key-value同时相等时，移除
Map移除元素，一般先找到桶的位置（通过hash），然后判断。如果是链表，则进行链表的遍历，找到需要删除的元素后删除，如果是红黑树，遍历树，找到元素后删除调整平衡，并且当红黑树小于阈值UNTREEIFY_THRESHOLD时，则转化成链表。
对于afterNodeRemoval(Node<K,V> p)，同样是LinkedHashMap进行处理
4.4 V get(Object key)
类似方法：V getOrDefault(Object key, V defaultValue)、boolean containsKey(Object key)、boolean containsValue(Object value)通过遍历查找每一个value，O(N)的时间复杂度
根据key查找元素，查看桶的第一个节点，如果是则返回，如果不是，则遍历链表或者红黑树。不存在返回null。
4.5 遍历方法
可以通过Set<K> keySet()、Collection<V> values()分别获取到key或者value的集合。
不推荐使用keySet获取到key的集合后，get每一个value。
可以使用Set<Map.Entry<K,V>> entrySet()来直接获取到key和value 的集合。
上面三种获取集合的方式，都是可以使用迭代器的。
注意：modCount的变化
五、LinkedHashMap类
LinkedHashMap是基于HashMap实现的一种集合，具有HashMap集合的所有特性，除了HashMap是无序的，LinkedHashMap是有序的，这个是因为LinkedHashMap在HashMap基础上单独维护一个具有所有数据的双向链表，该链表保存了元素迭代的顺序。
Entry节点：
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
它是一个双向链表。
属性：
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
除继承自HashMap的属性外，单独维护一个双向链表，这些都是双向链表必要的属性和数据结构。
5.1 添加函数
LinkedHashMap中没有put方法，而是直接调用HashMap的put方法，只是重写了afterNodeAccess(Node<K,V> p)、afterNodeInsertion(boolean evict)方法。
当然在添加新元素时，也将新元素添加到了链表的末尾。通过方法linkNodeLast()afterNodeAccess主要是在accessOrder为true时（并且当前节点不为尾结点）生效，也就是根据访问顺序排序。在具体实现中，将该节点从其他位置移动到尾部。afterNodeInsertion主要是处理添加后是否要移除首节点的元素，可以利用这个特性来实现LRU算法，其中需要重写boolean removeEldestEntry(Map.Entry<K,V> eldest)方法。
5.2 删除元素
LinkedHashMap直接调用HashMap的remove方法。只是在其中重写了afterNodeRemoval方法，
在该方法中增加了移除双链表中某个元素的功能。比较简单
5.3 遍历元素
LinkedHashMap是根据双链表进行遍历的，这样就是有序的，其中方法entrySet返回的是LinkedEntrySet内部类。
六、TreeMap类
TreeMap是有Tree和Map集合有关的，由红黑树作为底层实现的有序k-v集合
它不但继承了AbstractMap，而且实现了接口NavigableMap，表示它支持一系列获取指定集合的导航方法，比如获取小于指定key的集合。
因为是有序集合，所以在可以在构造方法中直接传入构造器，如public TreeMap(Comparator<? super K> comparator)，当然也可以在key的类中实现比较器Comparable
这里的有序是根据key对元素进行排序，上面LinkedHashMap只是保证了一个插入/访问的顺序，并不是根据key有序的。
6.1 V put(K key, V value)
类似方法：void putAll(Map<? extends K, ? extends V> map)、V putIfAbsent(K key, V value)
如果没有实现comparator方法，则key不允许为null值
6.2 V remove(Object key)
类似方法：boolean remove(Object key, Object value)
移除元素
注：本文为《Java修炼指南：高频源码解析》阅读笔记