集合类深入
先上一张继承关系图
ArrayList
对象数组结构。
public ArrayList() {
//调用ArrayList(int initialCapacity)
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//创建存储数据对象
this.elementData = new Object[initialCapacity];
}
元素添加：
public boolean add(E e) {
//校验数组容量
ensureCapacity(size + 1); // Increments modCount!!
//将数据对象插入到数组的size末端
elementData[size++] = e;
return true;
}
//插入指定位置的元素
public void add(int index, E element) {
//索引>size或索引小于0直接抛出异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
ensureCapacity(size + 1); // Increments modCount!!
//将index后面的数据后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将数据插入到指定index位置
elementData[index] = element;
//size加一
size++;
}
public void ensureCapacity(int minCapacity) {
modCount++;
//原有数组容量大小
int oldCapacity = elementData.length;
//插入的索引位置大于数组容量，增大数组容量
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//数组容量增大，按照原数组容量大小0.5增加
int newCapacity = (oldCapacity * 3) / 2 + 1;
//增大的容量如果还是小于插入的索引位置，将索引直接赋值给新的数组容量
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//将数组按照新的数组容量进行扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
先校验底层的对象数组是否能再添加元素，如果没法添加，先将对象数组进行扩容，进行一次数组拷贝，扩容因子为0.5，再进行插入；如果能添加元素，直接将数据插入到size对应的索引位置。如果插入到指定位置将会涉及到数组元素的后移，进行一次数组拷贝。
元素获取：
public E get(int index) {
RangeCheck(index);//校验index大小
return (E) elementData[index];//获取index位置的数据
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
}
元素删除：
public E remove(int index) {
RangeCheck(index);//检查index大小
modCount++;
E oldValue = (E) elementData[index];//标记删除位置的值
int numMoved = size - index - 1;//计算删除索引到size剩入数据
if (numMoved > 0)//如果剩入数据大于0，则将index后的数据进行前移。
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; //将size大小-1，并将elementData的原来索引位置为size-1的数据清空。
return oldValue;
}
删除涉及到数组的前移，前移的数据范围为删除索引的值+1到size-1的元素，删除时并未缩小数组大小。
（1）：ArrayList的实际存储对象为一个数组对象，没有容量大小，可以无限增加【扩展因子为0.5】。
（2）：ArrayList中可以包含重复的元素，并可以存储NULL值。
（3）：ArrayList的所有方法都是非线程安全的。
（4）：ArrayList的索引访问和元素更新方面有着非常优秀的性能，因为不需要花费精力做范围检查，所以从ArrayList的末端添加元素，删除元素也有着非常优秀的性能，除非ArrayList的存储容量不足而需要扩展内部数组的长度。插入和删除数据需要一个数组的拷贝，需要拷贝的元素数量是ArrayList的元素长度（size-1）减去索引号。对插入来讲，插入元素到ArrayList的第一个元素位置的性能最差，插入到最后一个位子的性能最好，数组拷贝所需的时间会根据元素的数量增加而显著增加。
（5）：ArrayList查找指定位置的数据时间为O(1)，插入到指定位置的数据时间为O(size-index-1)。
（6）：ArrayList插入大量的元素，提前指定ArrayList的大小，防止在插入过程ArrayList进行扩容。
Vector
实现与ArrayList基本一致，但所有的关键方法均加入了synchronized关键字，是线程安全的，适用于多线程共享数据存储的情况。
LinkedList
双向链表结构。
双向链表的每个节点用内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。
元素添加：
public boolean add(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;//原来链表为空，这是插入的第一个元素
else
l.next = newNode;
size++;
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);//index >= 0 && index <= size;
if (index == size)//插入位置是末尾，包括列表为空的情况
add(element);
else{
Node<E> succ = node(index);//1.先根据index找到要插入的位置
//2.修改引用，完成插入操作。
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//插入位置为0
first = newNode;
else
pred.next = newNode;
size++;
}
}
直接在队尾的链表节点上增加一个元素节点，时间复杂度为O(1)；先根据index找到要插入的位置，再修改链表节点关系，将新数据加入。注意这里查找index的时候，判断了index的位置与size的关系，如果靠后则从后向前遍历查找。
元素获取：
public E get(int index) {
//检查index是否合法
checkElementIndex(index);
//如果合法就返回该节点位置的值
return node(index).item;
}
//获取index位置上的节点
Node<E> node(int index) {
//断言index在链表中
// assert isElementIndex(index);
//从第一个节点开始寻找直到index位置，然后返回index//位置的节点
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;
}
}
//检查index值的合法性
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//判断index是否存在于链表中
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
获取index节点时需要从头到尾遍历链表，当链表数据量比较大时，耗时比较严重。
元素删除：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
//保存x节点的值
final E element = x.item;
//保存x节点的后继
final Node<E> next = x.next;
//保存x节点的前驱
final Node<E> prev = x.prev;
//如果前驱为null，说明要移除的是第一个节点，把First指向下一个节点就行
if (prev == null) {
first = next;
} else {//否则，把x节点前驱的后继指向x的后继，并把x的前驱设置为null
prev.next = next;
x.prev = null;
}
//如果后继为null则要移除的是最后一个节点，则把last的引用指向x节点的前驱就ok
if (next == null) {
last = prev;
} else {//否则，把x节点的后继的前驱设置为x节点的前驱，并x节点的后继设为null
next.prev = prev;
x.next = null;
}
//把x节点的值设为null，这样x就没有任何引用了，gc处理
x.item = null;
//把链表的size减少1
size--;
//结构性修改的次数增加1
modCount++;
//返回x节点的值，在移除之前已经保存在element中了
return element;
}
HashMap
链表数组结构。
在HashMap内部，有一个transient Entry[] table这样的结构数组，它保存所有Entry的一个列表，而Entry的定义是一个典型的链表结构，它是单独为HashMap服务的一个内部单链表结构的类。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//...
}
元素添加
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
hash(int h)方法根据key的hashCode重新计算一次散列。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
接下来看一下indexFor方法。
static int indexFor(int h, int length) {
return h & (length-1);
}
首先，HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方，h& (length-1)运算等价于对length取模，当数组长度为2的n次幂的时候，不同的key算得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
HashMap的resize：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为 2 * 16 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
元素获取
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
// table[indexFor(hash, table.length)] 就是将indexFor运算得到的值直接映射到数组的索引
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
//找到hash值相同的情况下可能出现hash碰撞，所以需要调用equals方法来比较是否相等
return e.value;
}
return null;
}
先通过indexFor找到index位置，拿到首节点Entry，再循环遍历链表，通过比较key值是否相同，找到对应的Entry值。
HashSet
基于HashMap实现的，HashSet底层使用HashMap来保存所有元素。
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
它里面放置的元素都对应到map里面的key部分，而在map中与key对应的value用一个Object()对象保存。
TreeMap
基于红黑树实现，首先需要了解二叉树、平衡二叉树和红黑树。
- 没有子节点的节点称为树叶或叶子节点。
- 有相同父亲的节点称为兄弟节点。
- 对任意节点的深度是从根到该节点的唯一路径的长度。
- 树的高指的是从根节点到所有节点的路径中最长的一个。
二叉树是一棵树，其中每个节点都不能有多余两个儿子。对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有的项的值大于X中的项。
平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近
对二叉树进行插入操作可能会使其失去平衡的条件，但这可以通过对树进行简单的修正来保持其平衡的属性，这种操作称之为旋转，实现平衡二叉树，保持树的深度必须是O(log N)。
- 对a的左儿子的左子树进行一次插入 （右旋）
- 对a的左儿子的右子树进行一次插入 （左右旋）
- 对a的右儿子的左子树进行一次插入 （右左旋）
- 对a的右儿子的右子树进行一次插入 （左旋）
历史上平衡二叉树最流行的另一变种是红黑树。红黑树具有下列着色性质的二叉查找树：
- 每一个节点或者着成红色，或者着成黑色。
- 根是黑色的。
- 如果一个节点是红色的，那么它的子节点必须是黑色的。
- 一个节点到一个null引用的每一条路径必须包含相同数量的黑色节点。
元素添加：
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
//如果根节点为null，将传入的键值对构造成根节点（根节点没有父节点，所以传入的父节点为null）
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
// 记录比较结果
int cmp;
Entry<K,V> parent;
// 分割比较器和可比较接口的处理
Comparator<? super K> cpr = comparator;
// 有比较器的处理
if (cpr != null) {
// do while实现在root为根节点移动寻找传入键值对需要插入的位置
do {
// 记录将要被掺入新的键值对将要节点(即新节点的父节点)
parent = t;
// 使用比较器比较父节点和插入键值对的key值的大小
cmp = cpr.compare(key, t.key);
// 插入的key较大
if (cmp < 0)
t = t.left;
// 插入的key较小
else if (cmp > 0)
t = t.right;
// key值相等，替换并返回t节点的value(put方法结束)
else
return t.setValue(value);
} while (t != null);
}
// 没有比较器的处理
else {
// key为null抛出NullPointerException异常
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 与if中的do while类似，只是比较的方式不同
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 没有找到key相同的节点才会有下面的操作
// 根据传入的键值对和找到的“父节点”创建新节点
Entry<K,V> e = new Entry<K,V>(key, value, parent);
// 根据最后一次的判断结果确认新节点是“父节点”的左孩子还是又孩子
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 对加入新节点的树进行调整
fixAfterInsertion(e);
// 记录size和modCount
size++;
modCount++;
// 因为是插入新节点，所以返回的是null
return null;
}
1、以根节点为初始节点进行检索。
2、与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
3、循环递归2步骤知道检索出合适的叶子节点为止。
4、将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。
5、平衡二叉树操作fixAfterInsertion，调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。
TreeSet
底层基于TreeMap实现
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
value部分使用PRESENT替代。
LinkedHashMap
LinkedHashMap是HashMap的子类，核心实现是基于HashMap实现，但HashMap是无序的，而LinkedHashMap是有序的，我们来看看它是如何实现的。
在LinkedHashMap中，并没有实现put方法，重写了addEntry和createEntry方法，如下：
/**
* 创建节点，插入到LinkedHashMap中，该方法覆盖HashMap的addEntry方法
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// 注意头结点的下个节点即header.after，存放于链表头部，是最不经常访问或第一个插入的节点，
//有必要的情况下(如容量不够,具体看removeEldestEntry方法的实现，这里默认为false，不删除)，可以先删除
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* 创建节点，并将该节点插入到链表尾部
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//将该节点插入到链表尾部
e.addBefore(header);
size++;
}
在HashMap的addEntry方法中会调用createEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
所以可以知道，LinkedHashMap除了将Entry放到对应的桶之外，还将该节点放到了一个双向链表的尾部，用一张图来表达就是这样的。
每次插入的数据除了按照HashMap固有hashcode命中的存放方式外，还会形成一个以header结点为头结点的双向链表，每次将新加入的节点放在双向链表的尾部，用另一个示意图表示就是这样的。
所以HashMap用来存放和获取对象，而双向链表用来实现有序。
LinkedHashSet
在父类HashSet的构造器中，有专门为LinkedHashSet留的包构造器，实现即LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
总结
总结一下：
ArrayList基于数组实现，扩容因子为0.5，当索引位置超过数组容量时，按照原数组的0.5倍进行扩容，扩容涉及到数组拷贝，开销较大，同样在某个位置插入也需要拷贝数组，时间开销较大，但访问速度较快。
Vector就是线程安全的ArrayList。
LinkedList基于双向链表实现，在数据量较大的情况下，遍历成本较高，访问某个元素的时间成本也较高，但插入和删除的时间成本较低。
HashMap基于数组加链表的数据结构，初始化大小为16，负载因子为0.75，即当数组占位超过0.75当前长度时，就要对数组进行扩容，而且扩容倍数为当前的2倍。保持两倍的扩容比例是在桶这个层面实现最小哈希冲突的方法。当出现哈希冲突时，通过添加链表的方式解决，但一个HashMap的链表越少，性能才越好。
TreeMap的核心就是红黑树，红黑树是最典型的平衡二叉树实现，任何一次值的添加，都会导致树的失衡，以及左旋右旋的计算。
LinkedHashMap就是在HashMap的基础上，增加了双向链表，用来维护顺序，访问还是基于HashMap来完成，而遍历时则会基于双线链表，实现有序的访问。
