【干货】JAVA 8 中List源码深入解析
前言:如果给List,set,Map放一块的快,源码太多,所以分开搞,更加清楚。
Collection接口子类以及和Collections有什么区别?
Collection的子类只要有List,Set两个接口
Collection:作为List和Set的父类
Collections:集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。
ArrayList集合(底层主要采用的是数组+扩容)
在说其他内容的时候,先来说两个重要的API:
Array.copyOf(T[] original, int newLength)
copyOf参数详解:
* @param original the array to be copied --要复制的数组
* @param newLength the length of the copy to be --复制数组的长度
System.arraycopy(src, srcPos, dest, destPos, length);
arraycopy参数详解:
* @param src the source array. ---源数组。
* @param srcPos starting position in the source array. --源数组中的起始位置。
* @param dest the destination array. ---目标数组
* @param destPos starting position in the destination data.--目标数组中的起始位置。
* @param length the number of array elements to be copied.--表示的是长度
- Arraylist底层基于数组实现,所以下标是从0开始的
transient Object[] elementData;
- Arraylist底层默认数组初始化大小为10个object数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 添加元素后大于当前数组的长度,则进行扩容,将数组的长度增加原来数组的一半。
//这个方法主要是来进行扩容的
//在说扩容之前,先说下位移,比如说2<<3(其实相当于是 2的三次方),打印的结果是16
//2>>>3 (其实就相当于 2/2/2),打印的结果为 0
private void grow(int minCapacity) {
// 定义一个老的扩容相当于elementData的长度
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //在原有的基础上扩容,oldCapacity >> 1 扩容为原来的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //当如果只有一个扩容的时候,会增加一个扩容,所以当定义一个的扩容的,还是最少两个的
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
在这里主要拿其中的啷个方法来大概说下:
Remove方法:
public E remove(int index) {
rangeCheck(index); //每次都会先检验下索引,如果没有的话就会报异常
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; //计算的是需要从哪里替换的开始位置
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //给最后一个位置设置为null
return oldValue;
}
效果图:
每次删除的时候,会给其他的元素前边挪一挪,然后最后的设置为Null。
addAll方法:
//参数说明:index主要是插入的下标,element指的是插入的对象
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); //将原始的扩容+1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
添加的原理:
每次添加的时候,会将后边的数据后边移除。
Vector集合
其实Vecrot和ArrayList底层是一样的,差别就在于Vector中都是Synachized方法修饰的,还有一个就是Vecrot扩容是原来的2倍
众多方法都是被synchronized修饰的
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
public synchronized void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (elementCount < oldCapacity) {
elementData = Arrays.copyOf(elementData, elementCount);
}
}
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
modCount++;
ensureCapacityHelper(minCapacity);
}
}
这个就是双倍的扩容。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//采用的是三目运算符,相当于是oldCapacity+oldCapacity
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);
}
LinkList集合(底层主要采用的是链表)
双链表结构
transient Node<E> first; //定义第一个节点
transient Node<E> last; //定义最后一个节点
增删改查都是根据上一个节点和下一个节点来操作的
List集合总结
List中包括ArrayList,LinkList,Vetor以及其他子类
ArrayList:底层采用的是数组,查询比较快,线程不安全,效率高,扩容为原来的1.5倍。
Vector:线程安全,效率低,扩容为原来的2倍
LinkList:底层采用的是双向链表,增删改比较快
在实战中学习,在快乐中成长