集合源码-List
1.Collection分类：
ArrayList源码：
新增：
//1.ArrayList是数组结构，查询快增删慢。
//2.看源码：先看继承实现了什么（知源头），再看构造方法、定义的变量（识轮廓），在看对应调用的方法（会应用）
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 判断是否扩容
elementData[size++] = e;//赋值后size+1
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//elementData当前的数组 minCapacity：当前数组size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//若当前数组是一个空数组（还未新增过），取到默认容量10，否则返回size+1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//记录改变次数
//1.新增到第10次之前elementData.length是10，后面会1.5*10扩容
//2.新增到第10次时进入到grow方法 进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//>>右移：除以2的n次方
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//最大值是Integer的MAX
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
指定索引的新增
//指定索引去新增
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//多了这一步骤：用于将index之后的元素都往后移一位步：
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
删除：
public E remove(int index) {
rangeCheck(index);//校验索引值
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;//要移动的长度
if (numMoved > 0)
//将elementData从index+1开始长度为numMoved的部分移动到index位置处，即：index+1后面的元素前进一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 赋值 size-1
return oldValue;
}
查询：
//因为它本身就是个数组 速度快
//arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
LinkedList源码：
LinkedList是一个双向链表，查询慢、增删快
LinkedList属性：
transient int size = 0; //链表大小 transient Node<E> first;//头结点信息 transient Node<E> last;//尾节点信息 //节点信息：数据+前/后指针 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; } }
新增：
//从尾部新增： 其它类似！
public boolean add(E e) {
linkLast(e);
return true;
}
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 boolean remove(Object o) {
//这个就说明LinedList可以存放null元素
//遍历该链表，找到一致的元素删掉
if (o == null) {
//从头结点first开始一直next到尾节点null
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//解链操作
E unlink(Node<E> x) {
//首先先获取要删除元素的数据+前后一个数据信息
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//判断是不是头结点
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;//去掉该元素指针
}
//判断是不是为节点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//数据置空
x.item = null;
size--;
modCount++;
return element;
}
查询：
//可以根据索引、查询头尾
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//采用了二分法进行查询
Node<E> node(int index) {
//如果当前索引小于size的一半，从头结点开始查询
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;
}
}
ArrayList和LinekList的区别：
- LinkedList在删除和增加等操作上性能好（它只需要改变当前结点和前后结点即可，而ArrayList使用System.copy（…）方法操作的是一段长度的元素），而ArrayList在查询的性能上好。
- ArrayList：必须开辟连续空间进行存储数据而LinkedList不需要。
- 两者在遍历时可以使用for-each循环、Iterator、listIterator遍历器。
Vector源码：
Vector是数组结构（和ArrayList类似），线程安全的。在分析源码之前先了解下锁机制(也是Vector为啥是线程安全的)：对象锁、方法锁、类锁:
- 对象锁就是方法锁：就是在一个类中的方法上加上synchronized关键字，这就是给这个方法加锁了。Vector就是在方法上添加了synchronized关键字。
- 类锁：锁的是整个类，当有多个线程来声明这个类的对象的时候将会被阻塞，直到拥有这个类锁的对象被销毁或者主动释放了类锁。这个时候在被阻塞住的线程被挑选出一个占有该类锁，声明该类的对象。其他线程继续被阻塞住。例如：在类A上有关键字synchronized，那么就是给类A加了类锁，线程1第一个声明此类的实例，则线程1拿到了该类锁，线程2在想声明类A的对象，就会被阻塞。
Vector属性：
protected Object[] elementData; //数组容器 protected int elementCount; //元素个数 protected int capacityIncrement;//增长系数 在扩容的时候用到（若它大于0每次扩容是原数组容量+增长系数 若小于等于0 原数组容量*2） //Vector提供了构造方法 可以指定初始化容量和增长系数 public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } //默认初始化容量是10 public Vector() { this(10); }
增加：
//synchronized关键字 //和ArrayList原理类似 都是先判断是否扩容 在去赋值，不同的是扩容方式 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } private void ensureCapacityHelper(int minCapacity) { //若新增之后的长度>原长度扩容 //这里和ArrayList有点区别：应为无参构造的Vector默认长度为10，而ArrayList是0，在新增后初始化长度10然后再1.5*原长度 if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容 原长度+扩容系数/原长度*2 private void grow(int minCapacity) { int oldCapacity = elementData.length; //原长度+扩容系数（指定扩容系数>0）/原长度*2（ int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
删除：
//根据索引 public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; //将index后面的元素整体前移一位 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; } //根据元素值：根据元素值找到其索引，在根据索引删除 public boolean remove(Object o) { return removeElement(o); } public synchronized boolean removeElement(Object obj) { modCount++; int i = indexOf(obj); if (i >= 0) { removeElementAt(i); return true; } return false; } public synchronized void removeElementAt(int index) { modCount++; if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } int j = elementCount - index - 1; if (j > 0) { System.arraycopy(elementData, index + 1, elementData, index, j); } elementCount--; elementData[elementCount] = null; /* to let gc do its work */ }
总结：
1、arrayList和LinkedList区别？
- ArrayList底层是用数组实现的顺序表，是随机存取类型，可自动扩增，并且在初始化时，数组的长度是0，只有在增加元素时，长度才会增加。默认是10，不能无限扩增，有上限，在查询操作的时候性能更好
- LinkedList底层是用链表来实现的，是一个双向链表，注意这里不是双向循环链表,顺序存取类型。在源码中，似乎没有元素个数的限制。应该能无限增加下去，直到内存满了在进行删除，增加操作时性能更好。
- 两个都市线程不安全的，在iterator时，会发生fail-fast。
2、ArrayList和Vector的区别？
- ArrayList线程不安全，在用iterator，会发生fail-fast
- Vector线程安全，因为在方法前加了Synchronized关键字。也会发生fail-fast
3、fail-fast和fail-safe区别是什么?什么情况下会发生？
一句话，在在java.util下的集合都是发生fail-fast，而在java.util.concurrent下的发生的都是fail-safe 。fail-fast：快速失败，例如在arrayList中使用迭代器遍历时，有另外的线程对arrayList的存储数组进行了改变，比如add、delete、等使之发生了结构上的改变，所以Iterator就会快速报一个java.util.ConcurrentModificationException 异常，这就是快速失败。fail-safe:安全失败，在java.util.concurrent下的类，都是线程安全的类，他们在迭代的过程中，如果有线程进行结构的改变，不会报异常，而是正常遍历，这就是安全失败。
- 1、为什么在java.util.concurrent包下对集合有结构的改变，却不会报异常？
这里稍微解释一下，在concurrent下的集合类增加元素的时候使用Arrays.copyOf()来拷贝副本，在副本上增加元素，如果有其他线程在此改变了集合的结构，那也是在副本上的改变，而不是影响到原集合，迭代器还是照常遍历，遍历完之后，改变原引用指向副本，所以总的一句话就是如果在次包下的类进行增加删除，就会出现一个副本。所以能防止fail-fast，这种机制并不会出错，所以我们叫这种现象为fail-safe。
- 2、vector也是线程安全的，为什么是fail-fast呢？
这里搞清楚一个问题，并不是说线程安全的集合就不会报fail-fast，而是报fail-safe，你得搞清楚上面这个问题答案的原理，出现fail-safe是因为他们在实现增删的底层机制不一样，就像上面说的，会有一个副本，而像arrayList、linekdList、verctor等，他们底层就是对着真正的引用进行操作，所以才会发生异常。
- 3、既然是线程安全的，为什么在迭代的时候，还会有别的线程来改变其集合的结构呢(也就是对其删除和增加等操作)？
首先，我们迭代的时候，根本就没用到集合中的删除、增加，查询的操作，就拿vector来说，我们都没有用那些加锁的方法所以其他线程是可以拿到该集合的。
- fail-fast
- fail-safe
4、为什么现在都不提倡使用vector了？
- 1、vector实现线程安全的方法是在每个操作方法上加锁，这些锁并不是必须要的，在实际开发中，一般都市通过锁一系列的操作来实现线程安全，也就是说将需要同步的资源放一起加锁来保证线程安全，
- 2、如果多个Thread并发执行一个已经加锁的方法，但是在该方法中，又有vector的存在，vector本身实现中已经加锁了，那么相当于锁上又加锁，会造成额外的开销，
- 3、就如上面第三个问题所说的，vector还有fail-fast的问题，也就是说它也无法保证遍历安全，在遍历时又得额外加锁，又是额外的开销，还不如直接用arrayList，然后再加锁呢。
总结：Vector在你不需要进行线程安全的时候，也会给你加锁，也就导致了额外开销，所以在jdk1.5之后就被弃用了，现在如果要用到线程安全的集合，都是从java.util.concurrent包下去拿相应的类。
版权声明：本文为Jiedeman原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。