ArrayList
基于数组实现
构造函数：
ArrayList()初始化空数组ArrayList(int initialCapacity)使用指定容量初始化数组ArrayList(Collection<? extends E> c)使用集合初始化数组，如果传入的集合为ArrayList则是直接赋值，否则使用数组拷贝。
trimToSize：将数组大小修剪为当前实际存放的数据大小，使用数组拷贝。
add:先调用ensureCapacityInternal(size+1)确保当前数组容量可以新增元素，然后再设置元素。
get:直接通过数组索引获取元素。
remove(int index)：删除index元素，后面元素向前移动一位（拷贝），返回值为删除的元素，remove(Object o)返回值为boolean。
ensureCapacityInternal(int minCapacity)：确保数组容量不小于传入值，会先通过calculateCapacity计算得到要设置的实际最小值，如果使用空参构造且传入最小值小于默认值10（DEFAULT_CAPACITY）,则会使用默认值，否则使用传入值。
然后通过ensureExplicitCapacity进行扩容，内部调用grow(int minCapacity)函数，grow函数每次扩容为原始大小的1.5倍（newCapacity = oldCapacity + (oldCapacity >> 1)），当原始容量1.5仍然小于传入值时，才会使用传入值作为数组容量。
grow扩容函数还对数组最大容量进行了控制，如果传入值大于ArrayList默认的最大容量MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,则会使用Integer.MAX_VALUE作为数组容量。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return 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);
}
toArray(T[] a):传入数组a的长度小于当前ArrayList大小时效果与toArray()一致，直接返回一个大小与ArrayList一致的数组拷贝。否则会将ArrayList中的元素拷贝到数组a并返回。
LinkedList
基于链表实现（双向链表）,还实现了Deque接口，可以当队列或者双端队列使用。
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;
}
}
HashMap
jdk 1.7 使用数组+链表实现。
jdk 1.8 使用数组+链表+红黑树实现，当某个索引上的链表长度大于8(TREEIFY_THRESHOLD)时，会调用treeifyBin(Node<K,V>[] tab, int hash)转换红黑树，treeifyBin函数会先判断当前数组长度是否大于64(MIN_TREEIFY_CAPACITY),当大于64了才会进行转换，否则会先调用resize()进行数组扩容，因为造成链表过长不一定是hash值相同（冲突），还可能是由于hash取模之后相同，所以优先进行数组扩容。
扰动函数：计算hash值并不是直接使用hash值（32位，int值范围），而是将hash值的高16位与低16位进行异或运算，以增大随机性、降低hash冲突概率。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
初始化容量（initialCapacity）：默认16（1<<4）,可通过构造函数HashMap(int initialCapacity, float loadFactor)传入，会通过函数tableSizeFor(int cap)设置为大于传入值的最小的2幂次方数（7->8,15->16,32->32,48->64）。
HashMap为什么保证容量始终为2的幂次方数？
负载因子(loadFactor)：默认值0.75f，可通过构造函数传入，数据量达到当前容量*负载因子会发生扩容。
插入：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
- 数组为空时先调用
resize()初始化数组。 - 根据hash计算数组索引位置
– 如果为空则直接插入节点
– 如果不为空（产生hash冲突）
---- 如果key与当前索引第一个节点对应，则更新值。
---- 如果是红黑树，则调用红黑树方法插入。
---- 否者遍历链表，找到插入位置进行插入。然后会进行长度判断是否需要扩容或转红黑树。 - 判断当前总元素是否超过阈值
(threshold),超过即调用resize()扩容。
扩容机制：
jdk 1.7 中扩容会重新计算hash获取新的位置索引。
jdk 1.8 中扩容不用重新计算hash也能获取新的位置索引。
查找：
删除：
遍历：