Collection
List(有序, 可重复)
ArrayList
数组，线程不安全。
查询：带下标访问数组，O(1)
修改：由于 arraylist 不允许空的空间，当在一个 arraylist 的中间插入或者删除元素，需要遍历移动插入 / 删除位置到数组尾部的所有元素。另外 arraylist 需要扩容时，需要将实际存储的数组元素复制到一个新的数组去，因此一般认为修改的时间复杂度 O(N)
扩容
/*minCapacity 为原 list 长度 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity – elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
默认情况 1.5 倍增长
Vector
数组，线程安全 (条件)
与 ArrayList 不同的是使用了同步（Synchronized），基本实现了线程安全
对象进行操作时，不加锁的话还是有问题，例如下面的例子
public Object deleteLast(Vector v){
int lastIndex = v.size()-1;
v.remove(lastIndex);
}
执行 deleteLast 操作时如果不加锁，可能会出现 remove 时 size 错误
扩容默认 2 倍增长
Stack 堆栈
继承 Vector 通过 push、pop 进行入栈，出栈
LinkedList
双向链表，线程不安全
查询，需要遍历链表，时间复杂度 O(N)
修改，只需要修改 1～2 个节点的指针地址，时间复杂度 O(1)
Set(无序, 唯一)
HashSet
HashMap, 线程不安全
操作元素时间复杂度, O(1)
LinkedHashSet
LinkedHashMap，线程不安全
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
…
public LinkedHashSet() {super(16, .75f, true);}
}
//hashset.java 中的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
操作元素 O(1)
由于底层结构是 LinkedHashMap，可以记录元素之间插入的顺序
TreeSet
TreeMap, 线程不安全
由于是树结构，可以保证数据存储是有序的
操作元素时间复杂度，O(logN)
Queue 队列
queue 使用时要尽量避免 Collection 的 add() 和 remove() 方法，而是要使用 offer() 来加入元素，使用 poll() 来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add() 和 remove() 方法在失败的时候会抛出异常。如果要使用前端而不移出该元素，使用 element() 或者 peek() 方法。
1、没有实现的阻塞接口的 LinkedList：
实现了 java.util.Queue 接口和 java.util.AbstractQueue 接口 内置的不阻塞队列：PriorityQueue 和 ConcurrentLinkedQueue PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。
2) 实现阻塞接口的
java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。五个队列所提供的各有不同：
ArrayBlockingQueue：一个由数组支持的有界队列。
LinkedBlockingQueue：一个由链接节点支持的可选有界队列。
PriorityBlockingQueue：一个由优先级堆支持的无界优先级队列。
DelayQueue：一个由优先级堆支持的、基于时间的调度队列。
SynchronousQueue：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。
Map
HashMap
链表结构，Node 结构
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;
}
JDK 1.8 新特性，当节点数大于 8 时，将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD – 1)
treeifyBin(tab, hash);
过长的链表搜索性能降低，使用红黑树来提高查找性能。
hash 值计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对 key 的 hash 码高 16 位实现异或
a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
如果 a、b 两个值不相同，则异或结果为 1。如果 a、b 两个值相同，异或结果为 0
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);
…
插入 table 时，下标 index = (n – 1) & hash 在 n 较小时，hash 码的低位的 0 和 1 不均匀，容易冲突导致碰撞。而通过上述 XOR 算法调整后，hash 的低 16 位会变大，从而使得 0 和 1 分布更加均匀。
计算表容量
static final int MAXIMUM_CAPACITY = 1 << 30;
public HashMap(int initialCapacity, float loadFactor) {
/** 省略此处代码 **/
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
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;
假设 cap=37，则 n =36，100100
右移 1，010010，或结果 =110110
右移 2，001101，或结果 =111111
右移 4，000011，或结果 =111111
右移 8，000000，或结果 =111111
右移 16，000000，或结果 =111111
结果为 63，二进制或操作只有在两数都为 0 时，才为 0，因此通过循环右移，或操作，实际是为了找到 n 的最高位，并将后面的数字全部全改写为 1，从而实现返回大于等于 initialCapacity 的最小的 2 的幂。
扩容
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 threshold
newCap = oldThr;
else {// zero initial threshold signifies using defaults
newCap = 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 {// 链表
Node<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;
else
loTail.next = e;
loTail = e;
}
else {// 尾部指针 hi
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
这段代码的含义是将 oldTab[j] 中的链表对半拆到 newTab[j] 和 newTab[j + oldCap]
if ((e.hash & oldCap) == 0) 怎么理解
我们知道 oldTab 中的 index = (n – 1) & hash，假设 n =8，则 newTab 中的 index = (16-1) & hash，那么在 newTab 中的 index 为 index 或者 index + 8，那么 e.hash & oldCap == 0 ,hash 必然为 X001000 的形态才有可能，也就是说 if ((e.hash & oldCap) == 0) 代表 newindex == index 的情况
loHead loTail/ hiTail hiHead 这 2 对指针
前面说了 if ((e.hash & oldCap) == 0) 表示 newindex == index，那么 lo 指针指向的就是此类节点，hi 指针指向剩下的节点通过 tail 指针的移动，实现链表拆分以及各节点 next 指针的更新
HashTable
Dictionary, 线程安全
操作元素时间复杂度, O(1)
synchronized 线程安全
写入数据
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings(“unchecked”)
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {// 遍历链表
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings(“unchecked”)
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
扩容
遍历，重新计算 index，并填入 newMap
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity – MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i– > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index]; // 反转链表
newMap[index] = e;
}
}
}
TreeMap
红黑树是平衡二叉树排序树，我们来看下它的特性
红黑树特性
二叉排序树特性
是一棵空树，
或者是具有下列性质的二叉树
左子树也是二叉排序树，且非空左子树上所有结点的值均小于它的根结点的值
右子树也是二叉排序树，且非空右子树上所有结点的值均大于它的根结点的值
平衡二叉树特性
它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1
左右两个子树都是一棵平衡二叉树。
红黑树的特性:
节点是红色或黑色。
根节点是黑色。
每个叶节点（NIL 节点，空节点）是黑色的。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
查找
基于递归的思想处理
/* 查找大于等于 K 的最小节点 */
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {//key < p.key
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {key > p.key
if (p.right != null) {
p = p.right;
} else {// 叔节点
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
/* 查找小于等于 K 的最大节点, 原理类似，省略 */
final Entry<K,V> getFloorEntry(K key) {
…
}
/* 查找大于 K 的最大节点, 原理类似，省略 */
final Entry<K,V> getHigherEntry(K key) {
…
}
/* 查找小于 K 的最大节点, 原理类似，省略 */
final Entry<K,V> getLowerEntry(K key) {
…
}
恢复平衡
插入 / 删除节点会破坏红黑树的平衡，为了恢复平衡，可以进行 2 类操作：旋转和着色
旋转
左旋
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋
插入节点
插入节点总是为红色
场景分析
情形 1: 新节点位于树的根上，没有父节点
将新节点 (根节点设置为黑色）
情形 2: 新节点的父节点是黑色
无处理
情形 3: 新节点的父节点是红色，分 3 类情况
3A: 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
3B: 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
3C: 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
总结
== 为了保证红黑树特性 5，插入的节点需要是红色 ==
== 根节点是红色或者黑色，都不影响红黑树特性 5，也就是说当父节点和叔节点均为红色时，可以通过将互换祖父与父、叔节点的颜色来上朔不平衡，并最终通过将根节点从红色设置为黑色来解决不平衡 ==
== 当叔节点为黑色，父节点为红色时，按照上述思路将父节点与祖父节点颜色互换后，必然会使得当前节点所在的子树黑色节点过多而影响红黑树特性 5，因此需要通过旋转将黑色节点向相反方向转移，以平衡根的两侧 ==
3A
当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
处理思路:
父节点与叔节点变黑色
祖父节点变红色
当前节点转换为祖父节点，迭代处理
graph TD
1[祖父红]–>2[父黑]
1–>3[叔黑]
2–>4{新红}
2–>5[兄]
3B
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
处理思路:
左旋 / 右旋父节点
后续操作见 3C
3C
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
处理思路
父节点设置为黑色
祖父节点设置为红色
右旋 / 左旋祖父节点
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; // 新插入的节点为红色
while (x != null && x != root && x.parent.color == RED) {
// x 的父节点 == x 的父 - 父 - 左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// y 为 x 的叔节点
if (colorOf(y) == RED) {// 叔节点为红色, 3A
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {// 叔节点为黑色
if (x == rightOf(parentOf(x))) {//3B
x = parentOf(x);
rotateLeft(x);
}
//3C
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//3A
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {//3C
x = parentOf(x);
rotateRight(x);
}
//3B
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
删除节点
情况分析
被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给 ” 被删除节点 ” 之后，再将后继节点删除。这样就巧妙的将问题转换为 ” 删除后继节点 ” 的情况了，下面就考虑后继节点。在 ” 被删除节点 ” 有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然 ” 的后继节点 ” 不可能双子都非空，就意味着 ” 该节点的后继节点 ” 要么没有儿子，要么只有一个儿子。若没有儿子，则按 ” 情况①” 进行处理；若只有一个儿子，则按 ” 情况② “ 进行处理。
private void deleteEntry(Entry<K,V> p) {
modCount++;
size–;
// 情况 3 将 p 的值赋予后继节点 s，并转换为删除 s
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 情况 2
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null; // p 是根节点
} else {// 情况 1
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
重新平衡
删除节点 x，根据上文分析，x 有 0 或 1 个子节点
x 是红色节点，那么删除它不会破坏平衡
如果 x 是黑色
4A 兄节点为红色
4B 兄节点的两个子节点均为黑色
4C 兄节点的远端子节点为黑色，另一个为红色或无
4D 兄节点的远端子节点为红色，另一个为红色或无
兄节点及其子树的黑色节点应该比 X 多一个
4A 兄节点为红色
处理方法：
兄节点设置为黑色
父节点设置为红色
左旋 / 右旋父节点，变形为 B /C/ D 情况
4B 兄节点的两个子节点均为黑色
处理方法：
兄节点设置为红色
x 设置为父节点，上溯不平衡
4C 远端侄节点为黑色，另一个为红色或无
处理方法
近端侄节点设置为黑色
兄节点设置为红色
右旋 / 左旋兄节点
转换为 4D 处理
4D 兄节点为黑色，远端侄节点为红色，一个为红色或无
处理方法
将父节点的颜色赋予兄节点
将父节点设置为黑色
将远端侄节点的颜色设置为黑色
左旋父节点