集合类

Java 中重要的集合类有以下这些：集合类：Hashtable、HashMap、ArrayList、LinkedList、TreeMap、WeakHashMap

1、ArrayList

ArrayList 是一个有序数组，内部使用对象数组进行存储，并且有一个单独的 size 字段存储数组中对象的数量。

transient Object[] elementData;
private int size;

提示：虽然 elementData 是用 transient 进行修饰的，但是 ArrayList 提供了 writeObject/readObject 方法用于序列化时候读写用。

1.1 ArrayList.add() 方法流程图

ArrayList 内部的数据数组只有在第一次写入时才会进行初始化，使用 new ArrayList() 时候并没有初始化，是一个懒加载的模式。

可以看出，ArrayList 每次添加对象，基本上都要进行扩容，效率比较低

2、LinkedList

LinkedList 是一个链表类，内部是使用的双指针节点进行的实现，有头指针个尾部指针，还有一个 size 变量存储链表中元素的数量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

3、TreeMap

TreeMap 是一个树形 Map 类，内部使用了红黑树结构进行存储，由指针节点组成

包含，左子树指针，右子树指针，父节点指针

TreeMap（红黑树）的查找、插入、删除操作时间负责度都为：O(logn)

private transient Entry<K,V> root;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

查找、插入、删除操作均为基础的红黑树逻辑操作（需要参考数据结构与算法，然后去阅读）

4、HashMap

HashMap 是一个哈希键值对集合，内部使用了节点数组进行存储。

4.1 核心参数

核心变量如下

• Node<K,V>[] table：节点数组，存储键值对数据
• int size：键值对数量
• int modCount：修改计数器，每次 HashMap 修改操作，计数器都会 +1
• int threshold：扩容临界点，用于触发扩容的阈值，threshold = 容量 * loadFactor，当 size > threshold 时候，将触发 HashMap 的扩容操作
• final float loadFactor：负载因子，只有初始化的时候可以指定，默认值为 0.75，用于计算扩容临界点值

核心常量如下

• int DEFAULT_INITIAL_CAPACITY = 1 << 4：默认 HashMap 容量大小，如果初始化时不指定容量，即为 16
• int MAXIMUM_CAPACITY = 1 << 30：最大容量，2³⁰
• float DEFAULT_LOAD_FACTOR = 0.75f：默认负载因子为 0.75

节点树化使用常量如下：

• int TREEIFY_THRESHOLD = 8：节点树化临界点，当节点长度 > TREEIFY_THRESHOLD，进入节点树化逻辑
• int UNTREEIFY_THRESHOLD = 6：节点取消树化临界点，当扩容时，节点长度 < UNTREEIFY_THRESHOLD，节点取消树化
• int MIN_TREEIFY_CAPACITY = 64：节点树化最小容量临界点，在树化逻辑中，当 size < MIN_TREEIFY_CAPACITY 时候，不进行树化操作，而是直接对 HashMap 进行扩容操作，所以一个节点是否树化有两个核心判断条件

了解以上核心参数的概念后，其实已经可以推断出 HashMap 的操作逻辑了。

使用 new HashMap() 初始化的时候并不会去初始化 table，只有当有写入操作的时候才回去进行初始化。

4.2 基础方法

static final int tableSizeFor(int cap)：对于给定的容量 cap，计算出大于 cap 的最小的 2 的 N 次幂，作为下一次扩容使用的临界点参数值，也就是扩容后的数组的大小，这个方法可以看出，HashMap 数组只能以 2 的倍数进行扩容，每次扩容为原来的 2 倍。

4.3 HashMap.put() 方法流程图

4.4 HashMap 扩容逻辑

5、Hashtable

Hastable 是线程安全的哈希表，负载因子与扩容临界值与 HashMap 用法一致

Hashtabe 是数组 + 链表的结构，没有使用红黑树

插入元素时候，如果发生哈希冲突，则会插入链表的头结点 

6、WeakHashMap

WeakHashMap 是由数组 + 链表构成，表中每个节点都是弱引用节点，当被垃圾回收器扫描到后，元素将会被回收处理。

引用强度：强引用（正常对象）> 软引用 > 弱引用 > 虚引用