1. ArrayList
基于动态数组实现，可以插入空数据，支持随机访问。
ArrayList在调用 add() 方法的时候
- 首先进行扩容校验。如果容量不够时，需要使用 grow() 方法进行扩容，每次扩容大小是原数组的 1.5 倍。
- 将插入的值放到尾部。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
如果是在指定位置添加数据的话
- 也是首先扩容校验。
- 接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//复制，向后移动
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
那么删除数据也是一样的思路
将 index+1 后面的元素都复制到 index 位置上，然后将数组大小减一，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。
扩容
添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
Vector
Vector 底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据,开销比较大
与 ArrayList 的比较
Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。
Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。
CopyOnWriteArrayList
特点是：读写分离
写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。
但是 CopyOnWriteArrayList 有其缺陷：
内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
LinkedList
基于双向链表实现，使用 Node 存储链表节点信息
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
每个节点存储了 prev 和 next 指针：
image.png
新增
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(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++;
modCount++;
}
从以上可以看出插入数据都是移动指针，改变前驱指针和后继指针的指向，当然删除数据也是一样的。
查找
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(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离链表头比较近，就从节点头部遍历。否则就从节点尾部开始遍历。
也就是索引值大于链表大小的一半，那么将从尾结点开始遍历
这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。
总结：
- LinkedList 插入，删除都是移动指针效率很高。
- 查找需要进行遍历查询，效率较低。
HashMap
HashMap 底层是基于数组和链表实现的。其中有两个重要的参数：
- 容量
- 负载因子
容量的默认大小是 16，负载因子是 0.75，当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。
put 方法
首先会将传入的 Key 做 hash 运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。
网友评论