JavaSE开发中使用的ArrayList源码解析
面试过程中常见问题ArrayList和LinkList有什么区别?
通常答:两者数据结构不同,ArrayList是基于数组,LinkList是基于链表,ArrayList查询比较快,LinkList插入比较快。
那么插入过程中LinkList真的比ArrayList快吗?那为什么coding过程无论插入还是查询都是使用ArrayList的情况多呢?你真的了解日常使用的ArrayList和LinkList的吗?
public static void main(String[] args) {
int length = 100000;
List arrList = new ArrayList(length);
List linkList = new LinkedList();
long startTime=System.nanoTime();
for (int i = 0; i < length; i++) {
arrList.add(i);
}
long endTime = System.nanoTime();
System.out.println("arrayList插入耗时:" + (endTime - startTime));
System.out.println("=================");
long startTime1 = System.nanoTime();
for (int i = 0; i < length; i++) {
linkList.add(i);
}
long endTime1 = System.nanoTime();
System.out.println("linkList插入耗时:" + (endTime1 - startTime1));
}
结果和我们日常所熟知的并不太一样,带着这个疑问,开始这篇文章的内容。本文主要从数组开始讲解,到ArrayList相关源码实现,希望可以帮助朋友彻底掌握ArrayList。
前提
ArrayList中有几个属性
//存储arrayList的真正容器,就是数组
transient Object[] elementData;
//默认容量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数组真实的容量
private int size;
1.ArrayList构造函数
先看ArrayList中的属性,为什么定义两个{}?
//无初始化容量
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//设置初始化容量
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);
}
}
关键点
默认构造函数
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
有参构造函数
this.elementData = EMPTY_ELEMENTDATA;
利用两个不同的属性值,就将ArrayList是通过哪种方式创建的进行了区分,这个区分为了之后的扩容。下边添加元素的时候咱在看。
那么问题又来了为什么给默认构造函数一个默认值?
数组属于引用类型,如果没有默认值,那么创建n个默认无参集合,就需要占用n个内存地址。而此时都指向了同一个地址,减少内存的占用。
2.查找
之前在博客中已经介绍过【算法&数据结构篇】——数组和链表,关于数组基础概念请移步。这里只强调几个重点概念,数组支持下标查询,而且是连续内存,存储相同类型的元素,所以每个元素占用的内存空间是相同的。也就是这里为数组支持随机访问元素提供了基础。
先说通常大家提到数组的普遍认知,支持随机访问,但是本质上这种表述不准确,数组是适合查找操作,但是查找的时间复杂度并不是O(1)。即使排好顺序的数组,使用二分查找,时间复杂度也是O(logn)。正确的描述应该是,根据下标随机访问的时间复杂度为O(1),即get(i) 数组的起始位置+i*元素占用的内存。在ArrayList中get方法就是通过下标进行的随机访问
public E get(int index) {
//检查下标是否越界
rangeCheck(index);
//获取数组的第i个元素
return elementData(index);
}
3.插入和删除
数组是有固定容量的,所以使用ArrayList进行add,需要考虑容量大小,并实现自动扩容。ArrayList中add有两种方式,默认是尾部添加,另一种指定下标添加元素。
1) 、默认尾部添加元素
public boolean add(E e) {
//确定ArrayList容量,不够则进行扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果elementData为默认无参构造函数创建,则初始化容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//todo 操作数,咱们将迭代器的在处理
modCount++;
//如果数组容量已满,则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//默认扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后还不够,则已入参设置的容量为主
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断数组是否超过限定的最大值Integer.MAX_VALUE - 8,如果超过则扩容为Integer.MAX
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
在添加元素的时候,开头讲的两个值一样,但是属性名称不同的操作,在此处有了答案,这个判断决定通过默认构造函数创建的ArrayList默认容量为10。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
这此处纠正一个误区,ArrayList的最小容量并不是10,利用有参构造函数创建的时候,ArrayList的最小容量可以为0.
2)、指定下标添加元素
public void add(int index, E element) {
//下标越界检查
rangeCheckForAdd(index);
//同上判断扩容,记录操作树
ensureCapacityInternal(size + 1);
//依次复制插入位置及后面的数组元素,到后面一格,不是移动,因此复制完后,添加的下标位置和下一个位置指向对同一个对象
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//再将元素赋值给该下标
elementData[index] = element;
size++;
}
利用这种方式进行插入,时间复杂度为O(n),与移动元素个数正相关,所以如果利用add(E e)能解决问题,优先使用尾部元素添加。
3)、指定下标删除元素
public E remove(int index) {
//检查数组元素下标是否合法
rangeCheck(index);
// todo 操作树,之后将迭代器再说有何用
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
//判断要删除的元素是否是最后一个位,如果 index 不是最后一个,
//就从 index + 1 开始往后所有的元素都向前拷贝一份。
//然后将数组的最后一个位置空,如果 index 是最后一个元素那么就直接将数组的最后一个位置空
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//让指针最后指向空,进行垃圾回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
4)、删除指定元素
//当我们调用 remove(Object o) 时,会把 o 分为是否为空来分别处理。
//然后对数组做遍历,找到第一个与 o 对应的下标 index,
//然后调用 fastRemove 方法,删除下标为 index 的元素。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
删除指定元素,从代码可以看出来,如果集合中有重复的值,只能默认删除一个值
从时间复杂度角度来分析,无论是哪种情况的时间的复杂度至少为O(n),利用删除指定元素删除的时候时间复杂度为O(n^2)。
4.灵魂拷问容器能否完全替代数组?
每天都在用ArrayList,与数组相比,到底有什么优势呢?
ArrayList最大的优势可以将很多数组操作细节进行封装,例如数组的插入,删除是需要搬移数据,而且还支持动态扩容。
那么数组是不是就无用武之地了呢?答案:不是的!
1)、ArrayList无法存储基本类型,例如int,long需要封装成Integer,Long类,而拆装箱则有一定性能损耗,如果特别关注性能,或希望使用基本类型,则可以选用数组。
2)、如果数组大小已知,并且对数据操作非常简单,用不到ArrayList提供的大部分方法,也可以直接使用数组。
3)、表示多维数组时,利用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<ArrayList<object>> array,但是这点依据个人的使用喜好。
对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。
5.ArrayList的父类关系
ArrayList有三个特性,实现了三个标记接口:RandomAccess, Cloneable, java.io.Serializable
1)、RandomAccess
支持随机访问(基于下标),为了能够更好地判断集合是ArrayList还是LinkedList,从而能够更好选择更优的遍历方式,提高性能
List arrayList = new ArrayList();
long startTime2=System.nanoTime();
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long endTime2 = System.nanoTime();
System.out.println("arrayList插入耗时:" + (endTime2 - startTime2));
Collections.binarySearch(arrayList,Integer.class);
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
//利用Random区分查询是哪种list,采用不同的查询方式
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
2)、Cloneable
支持拷贝:实现Cloneable接口,重写clone方法、方法内容默认调用父类的clone方法。
2.1)、浅拷贝
基础类型的变量拷贝之后是独立的,不会随着源变量变动而
String类型拷贝之后也是独立的
引用类型拷贝的是引用地址,拷贝前后的变量引用同一个堆中的对象
public Object clone() throws CloneNotSupportedException {
Study s = (Study) super.clone();
return s;
}
2.2)、深拷贝
变量的所有引用类型变量(除了String)都需要实现Cloneable(数组可以直接调用clone方法),clone方法中,引用类型需要各自调用clone,重新赋值
public Object clone() throws CloneNotSupportedException {
Study s = (Study) super.clone();
s.setScore(this.score.clone());
return s;
}
java的传参,基本类型和引用类型传参
java在方法传递参数时,是将变量复制一份,然后传入方法体去执行。复制的是栈中的内容
所以基本类型是复制的变量名和值,值变了不影响源变量
引用类型复制的是变量名和值(引用地址),对象变了,会影响源变量(引用地址是一样的)
String:是不可变对象,重新赋值时,会在常量表新生成字符串(如果已有,直接取他的引用地址),将新字符串的引用地址赋值给栈中的新变量,因此源变量不会受影响
3)、Serializable
序列化:将对象状态转换为可保持或传输的格式的过程。与序列化相对的是反序列化,它将流转换为对象。这两个过程结合起来,可以轻松地存储和传输数据,在Java中的这个Serializable接口其实是给jvm看的,通知jvm,我不对这个类做序列化了,你(jvm)帮我序列化就好了。如果我们没有自己声明一个serialVersionUID变量,接口会默认生成一个serialVersionUID,默认的serialVersinUID对于class的细节非常敏感,反序列化时可能会导致InvalidClassException这个异常(每次序列化都会重新计算该值)
4)、AbstractList
继承了AbstractList ,说明它是一个列表,拥有相应的增,删,查,改等功能。
5)、List
为什么继承了 AbstractList 还需要 实现List 接口?
6.插入LinkList不一定比ArrayList快
ArrayList不适合插入的原因是因为在插入过程中涉及到数组的扩容拷贝,如果预先设定后ArrayList的容量,采用尾部添加时间复杂仅为O(1)。
那么不预先设定ArrayList为容量,那么LinkList插入一定比ArrayList快吗?
long startTime1 = System.nanoTime();
for (int i = 0; i < length; i++) {
linkList.add(i);
}
long endTime1 = System.nanoTime();
System.out.println("linkList插入耗时:" + (endTime1 - startTime1));
System.out.println("=================");
List arrayList = new ArrayList();
long startTime2=System.nanoTime();
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long endTime2 = System.nanoTime();
System.out.println("arrayList插入耗时:" + (endTime2 - startTime2));
LinkList在插入过程中需要创建新的节点,而ArrayList在扩容的时候直接创建好了数组,两者在插入过程中到底谁更快?还需要根据创建的数据量来判断。所以在coding过程无论插入还是查询都是使用ArrayList的情况多。
总结
ArrayList以数组作为底层数据结构,针对数组的插入和删除进行二次封装,隐藏了直接数组涉及到的数据搬移,扩容等复杂内容。ArrayList的使用给业务开发带来了极大的便利性,但是如果对性能要求极高,而且涉及到基本类型的操作,推荐优先使用数组。同时纠正误区在做插入操作的时候LinkList不一定比ArrayList快,这个具体需要比较是LinkList创建新节点更耗时,还是扩容更耗时。
通过看ArrayList源码,收获最大的一点是构造函数的巧妙,利用常量,让所有通过无参创建的ArrayList,指向内存中同一位置,节省了大量内存的消耗。而且为了区分扩容,利用两个不同的常量,将ArrayList的创建方式分开,也便利利用无参构造函数的初识容量的设定。
本文地址:https://blog.csdn.net/jiadajing267/article/details/108700091
推荐阅读
-
Java中的容器(集合)之ArrayList源码解析
-
.Net Core中ObjectPool的使用与源码解析
-
在iOS开发中关于NSUserDefaults的使用解析
-
WordPress开发中的get_post_custom()函数使用解析
-
golang中cache组件的使用及groupcache源码解析
-
JavaSE开发中使用的ArrayList源码解析
-
解析iOS应用的UI开发中懒加载和xib的简单使用方法
-
Java中的容器(集合)之ArrayList源码解析
-
JavaSE面试题——基于JDK1.8中ArrayList的实现原理(源码剖析)
-
WordPress开发中的get_post_custom函数使用解析