https://mp.weixin.qq.com/s/g2wy5orYf2r8qo7lg15_Fg
https://github.com/crossoverJie/Java-Interview/blob/master/MD/HashMap.md
https://www.cnblogs.com/skywang12345/p/3308900.html
LinkedList
LinkedList 是一个双向列表：
我们看一下它的 添加、查找 实现方式：
add：
//添加一个元素，直接添加到列表末尾
public boolean add(E e) {
linkLast(e);
return true;
}
//添加一个元素，并指定添加到的位置：index
public void add(int index, E element) {
linkBefore(element, node(index));
}
//根据 index 查找 node，并返回
Node<E> node(int index) {
//加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//创建一个 Node，把 e 包含进去，并前后结成链
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}
元素添加到 LinkedList 末尾
get：
public E get(int index) {
//直接调用 node() 方法，上面有代码。
return node(index).item;
}
ArrayList
add 和 get 方法：
//确认ArrayList的容量，若容量不够，则增加容量
public boolean add(E e) {
int minCapacity = size + 1; //minCapacity 为 add 之后的长度
//如果需要的长度 大于 数组的长度
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
elementData[size++] = e;
return true;
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//对数组长度扩容一倍，并相加，也就是扩大为原来的3倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
}
public void add(int index, E element) {
grow(size + 1);
//把 size - index 长度的数据 整体往后移一格（通过复制），腾出 index 这个位置给 element
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E get(int index) {
return (E) elementData[index];
}
ArrayList 和 LinkedList 总结：
LinkedList中插入元素快（二分法遍历），ArrayList插入元素慢（需要复制）。
LinkedList中查找元素慢（二分法遍历），ArrayList查找元素块（直接返回数组 索引下的值）
ArrayList 和 Vector 的区别
Vector 和 ArrayList 大体一样，只不过 Vector 的每个方法都加了 synchronized 关键字，下面是区别：
线程安全性不一样
ArrayList是非线程安全；
而Vector是线程安全的，它的函数都是synchronized的，即都是支持同步的。
ArrayList适用于单线程，Vector适用于多线程。对序列化支持不同
ArrayList支持序列化，而Vector不支持；即ArrayList有实现java.io.Serializable接口，而Vector没有实现该接口。构造函数个数不同
ArrayList有3个构造函数，而Vector有4个构造函数。Vector除了包括和ArrayList类似的3个构造函数之外，另外的一个构造函数可以指定容量增加系数。
public Vector(int initialCapacity, int capacityIncrement) {
super();
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
//看一下 Vector 中对 capacityIncrement 的使用
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//此处和 ArrayList 处理的不一致，ArrayList 是对 oldCapacity 扩大一倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
