Collection接口

List

ArrayList

基本内容

1. 可以允许null值
2. 内存是连续的，节省内存空间。
3. 插入时间复杂度：插在队头O(n)因为要把后面的元素都往后移动一位；插在队尾，如果不需要扩容，则是 O（1），如果需要扩容则先需要 O(n)把原来的 ArryList复制一遍，再执行O（1）的插入操作。 插在队中间，O(n).
4. 删除时间复杂度：与插入的时间复杂度相对应。
5. 并非线程安全。

底层实现

1. 由动态数组实现，随机访问某个节点，只需要计算它的地址值，因此随机访问O(1). 实现了RandomAccess这一个标识借口。
2. 如果没有指定初始容量，那么默认初始容量为0，第一次添加元素时，容量变成10. 每次动态扩容，容量变成原来的1.5倍。

ArrayList与 Array 的区别

1. ArrayList可以动态扩容；Array则不行，它的长度是固定的，并且需要在初始化数组的时候就指定长度
2. ArrayList支持泛型
3. ArrayList只支持对象，对于基本数据类型则需要使用它们的包装类如Integer, Double。Array支持基本数据类型和对象。

LinkedList

底层实现

1. 双向链表实现。在头部/尾部进行插入/删除的时间复杂度均为O(1)
2. 不支持随机访问。每次访问指定元素的时间复杂度为O(n)
3. 性能不如ArrayList, 在实际开发中基本不会用到。
4. 线程不安全。
5. 允许null值
6. 除了数据之外还要存指针，所以占用空间比LinkedList大。

HashMap

实现原理

1. 哈希表+链表/红黑树实现。解决哈希冲突的方法有 chaining/probing，一般使用chaining.
2. 哈希值如何计算？拿到key的hashcode()。将原 hashcode和hashcode右移16位的值进行异或运算。

1

int hash = (key == null) ? 0 : (key.hashCode()) ^ ((key.hashCode()) >>> 16);

3. 计算数组下标。hash&(length-1)，相当于hash%length. 二进制运算比取模运算更快。
4. 如果遇到碰撞，就在链表或红黑树中找是否存在该key，如果存在则直接替换值，如果不存在，就加到里面去。链表长度为 8，并且哈希表长度大于64时，升级成红黑树。
5. 红黑树节点数少于6时，变回链表。
6. 初始容量16，负载因子0.75，扩容至原来的两倍。
7. 并非线程安全。扩容的时候可能会造成链表成环。

时间复杂度

理想情况下，HashMap 的插入、删除和查找操作平均时间复杂度都是 O (1)。
如果转成红黑树，操作的时间复杂度会稳定在 O (log n)

扩容

1. 桶里只有一个节点：直接重新rehash搬到新的哈希表里面去。
2. 链表。遍历链表，对于每个元素 rehash，他们新的位置要么是原来的 index，要么是原来的 index+原来容量。所以相当于是拆成两条链表
3. 红黑树。当成链表来处理。节点为 6 ，退化为链表。

线程不安全

put操作并非原子。如果两个线程为两个元素计算出相同的桶 index，他们并发往哈希表里插入值，那么一个插入操作可能会被另一个插入操作覆盖。

hashMap正在扩容的时候另外一个线程要执行put操作，是插入到新的table还是旧的table?

若扩容还未完成：新线程的 put 操作会尝试在旧的 table 上进行。这是因为在扩容过程中，旧的 table 仍然是可以访问的，并且新线程在执行 put 时会先检查旧 table 的状态。如果发现正在扩容，它会尝试协助进行扩容操作（协助迁移元素），在协助完成一部分扩容工作后，再继续执行 put 操作，不过最终还是基于旧 table 来计算插入位置。
若扩容已经完成：新线程的 put 操作会在新的 table 上进行。因为扩容完成后，HashMap 内部的 table 引用已经指向了新的数组，后续的操作都会基于新数组来执行。

ConcurrentHashMap

1. 处理单个键值对一般用 CAS
2. 处理链表或者红黑树的时候，对它们的头节点加 synchronized。但此时其它线程可以自由更改其它桶。
3. HashMap 的 key 和 value 都可以为 null。但 ConcurrentHashMap 的 key 和 value 都不允许为 null。
4. ConcurrentHashMap 不允许 null 值，主要是因为它的设计理念是在高并发场景下提供强一致性。如果允许 null 值，在处理并发读写时会变得很复杂，难以判断某个键不存在到底是真没有还是值为 null，容易引发数据不一致问题，所以干脆就不允许了。

用红黑树，不用AVL Tree

AVL Tree 任意一颗子树的左右高度差最多为 1.
每次插入、删除节点可能需要旋转操作，会影响性能。

红黑树：根节点为黑色。红色代表该节点的父节点为黑色。
根到任意一个叶子节点的路径上，黑色节点的数量都是相等的。
黑色节点的子节点为红色或者为空。