养老院网站建设的费用,网站群建设方案,门户网站建设方案模板,火锅自助餐网站建设ArrayList类简介类层次结构构造无参构造有参构造添加元素add#xff1a;添加/插入一个元素addAll:添加集合中的元素扩容mount与迭代器其他常见方法不常见方法不常见方法的源码和小介绍常见方法的源码和小介绍积累面试题ArrayList是什么#xff1f;可以用来干嘛#xff1f;Ar…
ArrayList类简介类层次结构构造无参构造有参构造添加元素add添加/插入一个元素addAll:添加集合中的元素扩容mount与迭代器其他常见方法不常见方法不常见方法的源码和小介绍常见方法的源码和小介绍积累面试题ArrayList是什么可以用来干嘛ArrayList 的默认长度ArrayList如何扩容ArrayList频繁扩容导致性能下降该怎么办什么情况下你会使用ArrayList什么时候你会选择LinkedListArrayList的插入或删除一定比LinkedList慢吗写在前面: 第一次写源码分析感觉写起来不知道从何下手不过慢慢的也就写完了也不知道条理怎么样内容应该还是都说了。希望能对ArrayList的理解有所帮助. 本文通过ArrayList对动态数组的实现/生命周期来进行源码的解析。会列举源码并注释代码的作用。但不会讲述动态数组的实现过程实现过程在数组–java–动态数组已经写过了明天在继续写 本文内容包括源码分析 扩容机制 迭代器 面试题 简介
此类是 Java 集合框架的成员。 ArrayList 是一个数组队列相当于动态数组。与Java中的数组相比它的容量能动态增长。使用量很大所以作为第一个进行源码分析的类。
类层次结构
继承于AbstractList抽象类 实现了
List 有序集合也称为 序列的接口RandomAccess 标记性接口使得随机访问比迭代器快Cloneable 标记性接口克隆 所以重写clone方法完成浅克隆java.io.Serializable 标记性接口序列化
构造
ArrayList的构造方法一共有3个
无参构造 elementData代表着的就是存储元素的数组了。 transient关键字代表着其不能被序列化
注释上写着构造一共初始容量为10的空列表。但是我们打开DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个类查看。很明显这就是一个空数组所以最开始的数组大小就是0。 这个也算是慢初始因为可能构造了不用所以设置为空就会减少空间的浪费。 但为什么要这么写呢 我们可以看到这样一个属性我们在扩容的时候用到这个会导致无参构造扩容后就会是10.而在调用add后动态的初始化。 有参构造
根据你传入的参数来构建大小如果为0则会赋值一个空数组(但是这个和无参的不一样)
这个构造先判断传入集合的大小如果为空则设置为空数组。 如果不为空则判断是否的ArrayList类是则直接赋值了不是则进行拷贝。
添加元素
add添加/插入一个元素
这里和jdk8会不一样 modCount继承于AbstractList记录着集合的修改次数 然后调用了add(E e, Object[] elementData, int s)方法(jdk8直接实现出来了而不是抽取方法) 返回一个true代表添加成功 这段代码是很平常的添加代码有意思的是这个注释。 查阅资料发现当方法字节码大小小于35的时候会进行方法内联 而这个操作由c1编译器进行。c1编译器(适用于执行时间较短或对启动性能有要求的程序)会比c2要快所以可以让这个add成为热点而被优化。 这个部分应该属于JIT优化。
public void add(int index, E element)
/**
在此列表中的指定位置插入指定的元素。将当前位于该位置的元素如果有和任何后续元素向右移动将一个元素添加到其索引中。
形参:
index – 要插入指定元素的索引 element – 要插入的元素
抛出:
IndexOutOfBoundsException – 如果索引超出范围 index 0 || index size()
**/public void add(int index, E element) {rangeCheckForAdd(index); // 进行index范围的检查超出范围会抛出异常modCount;final int s;Object[] elementData;if ((s size) (elementData this.elementData).length)elementData grow();//赋值并且检查是否需要扩容System.arraycopy(elementData, index,elementData, index 1,s - index);// 拷贝插入点前后的元素elementData[index] element; // 插入点赋值size s 1;}addAll:添加集合中的元素
扩容
扩容判断
if (s elementData.length)则扩容这个是扩容的通用代码。 记录了旧容量后如果不是默认空数组或者容量大于0则if成立。 这里就是默认空数组和其他构造的空数组的区别了 如果是默认空数组则走初始容量为10的路线否则则按照1.5倍扩容走 /*** 增加容量以确保它至少可以容纳最小容量参数指定的元素数。** param minCapacity 所需的最小容量* throws OutOfMemoryError 如果最小容量小于零*/private Object[] grow(int minCapacity) {int oldCapacity elementData.length;//获取旧容量if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* 最小增长 */oldCapacity 1 /* 首选增长*/);//这个方法会从old的基础上选取后面2个值的大的来增长。// 也就是需要的容量和1.5倍比较return elementData Arrays.copyOf(elementData, newCapacity);//拷贝旧的} else {return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}而一般性的,就是长度加一调用上面的方法。 private Object[] grow() {return grow(size 1);}mount与迭代器
其他常见方法
//返回此列表中的元素数。
public int size()//如果此列表不包含任何元素则返回 true 。
public boolean isEmpty()//如果此列表包含指定的元素则返回true。更正式地说当且仅当此列表包含至少一个元素eObjects.equals(o, e)时返回 true .
public boolean contains(Object o)//返回此列表中指定元素第一次出现的索引如果此列表中不包含该元素则返回 -1。更正式地说返回最低索引例如 Objects.equals(o, get(i))如果没有这样的索引i则返回 -1。
public int indexOf(Object o)//返回此列表中指定元素最后一次出现的索引如果此列表中不包含该元素则返回 -1。更正式地说返回最高索引如果没有这样的索引iObjects.equals(o, get(i))则返回 -1。public int lastIndexOf(Object o)
不常见方法
//将此实例的容量修剪为列表的 ArrayList 当前大小。
public void trimToSize() //如有必要增加此 ArrayList 实例的容量以确保它至少可以容纳最小容量参数指定的元素数。
//形参:minCapacity – 所需的最小容量
public void ensureCapacity(int minCapacity) //浅克隆
public Object clone();
不常见方法的源码和小介绍
这是一个缩小空间的方法把未使用的数组删掉。 这个方法在ArrayList里面没有调用但是在其他地方优化的时候还挺多的。 /*** 将此实例的容量修剪为列表的 ArrayList 当前大小。* 应用程序可以使用此操作来最小化实例的 ArrayList 存储*/public void trimToSize() {modCount;if (size elementData.length) {elementData (size 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}没有调用的
public void ensureCapacity(int minCapacity) {if (minCapacity elementData.length !(elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA minCapacity DEFAULT_CAPACITY)) {modCount;grow(minCapacity);}}public Object clone() {try {ArrayList? v (ArrayList?) super.clone();v.elementData Arrays.copyOf(elementData, size);v.modCount 0;return v;} catch (CloneNotSupportedException e) {// this shouldnt happen, since we are Cloneablethrow new InternalError(e);}}常见方法的源码和小介绍
把这个放后面呢是因为简单应该看的人少。
public int size() {return size;} public boolean isEmpty() {return size 0;}public boolean contains(Object o) {return indexOf(o) 0;}public int indexOf(Object o) {return indexOfRange(o, 0, size);}int indexOfRange(Object o, int start, int end) {Object[] es elementData;if (o null) {for (int i start; i end; i) {if (es[i] null) {return i;}}} else {for (int i start; i end; i) {if (o.equals(es[i])) {return i;}}}return -1;}public int lastIndexOf(Object o) {return lastIndexOfRange(o, 0, size);}int lastIndexOfRange(Object o, int start, int end) {Object[] es elementData;if (o null) {for (int i end - 1; i start; i--) {if (es[i] null) {return i;}}} else {for (int i end - 1; i start; i--) {if (o.equals(es[i])) {return i;}}}return -1;}积累面试题
ArrayList是什么可以用来干嘛
ArrayList是个动态数组实现List接口主要用来存储数据只存储包装类。它的特点是
增删慢每次删除元素都需要更改数组长度、拷贝以及移动元素位置。
查询快由于数组在内存中是一块连续空间因此可以根据地址索引的方式快速获取对应位置上的元素。ArrayList 的默认长度
在jdk8以前和jdk8以后稍有不同
jdk8以前创建就会初始数组长度长度为10
jdk8及以后是懒加载初始的时候为空数组在第一次添加元素的时候扩容为10ArrayList如何扩容
定好容量后定好会把原来的数组元素拷贝到新数组中再把指向原数的地址换到新数组。
这个有2种扩容机制
对于无参构造的集合在第一次添加元素的时候会扩容到10存满后按照1.5倍的进行扩容。如果一次添加了多个元素1.5倍放不下则会按照实际需要的大小进行扩容。
对于其他的构造就没有扩容10的步骤了按照max(1.5倍实际大小)ArrayList频繁扩容导致性能下降该怎么办
这时候我们可以估算需要的容量使用
ArrayList(int capacity)的有参构造来指定容量的空列表在测试中甚至有几个下图这样这样的比例运行了
什么情况下你会使用ArrayList什么时候你会选择LinkedList
多数情况下当你遇到访问元素比插入或者是删除元素更加频繁的时候你应该使用ArrayList。
另外一方面当你在某个特别的索引中插入或者是删除元素更加频繁或者你压根就不需要访问元素的时候你会选择LinkedList。
这里的主要原因是在ArrayList中访问元素的最糟糕的时间复杂度是”1″
而在LinkedList中可能就是”n”了。
在ArrayList中增加或者删除某个元素通常会调用System.arraycopy方法这是一种极为消耗资源的操作因此在频繁的插入或者是删除元素的情况下LinkedList的性能会更加好一点。ArrayList的插入或删除一定比LinkedList慢吗
大多数是的但是不一定.
如果删除靠前的元素arraylist需要拷贝后面的元素
如果靠中间或者靠后linkedlist找元素需要消耗很多的时间而arraylist拷贝的元素会少一些
arraylist取数真的太快了linkedlist就算能从后面找就算是取最后一个数也慢了很多数组长度n10000 a100 bn-a cn/2 可以看到
随机向中间添加arraylist快
add方法添加到最后linkedlist完胜
随机删除Arraylist快
删除靠前元素linkedlist快
删除中间的arralist快
删除后面的arralist快TestArrayList.testArrayListRandonAdd thrpt 2 12289.462 ops/s
TestArrayList.testLinkedListRandonAdd thrpt 2 11362.013 ops/s
TestArrayList.testArrayListRandonAddLast thrpt 2 12820.688 ops/s
TestArrayList.testLinkedListRandonAddLast thrpt 2 2482660.154 ops/s
TestArrayList.testArrayListRandonRemove thrpt 2 207213.498 ops/s
TestArrayList.testLinkedListRandonRemove thrpt 2 11402.369 ops/s
TestArrayList.testArrayListRemove100 thrpt 2 110029.496 ops/s
TestArrayList.testLinkedListRemove100 thrpt 2 1036584.680 ops/s
TestArrayList.testArrayListRemoveNDividing2 thrpt 2 205019.017 ops/s
TestArrayList.testLinkedListRemoveNDividing2 thrpt 2 6156.114 ops/s
TestArrayList.testArrayListRemoveN_100 thrpt 2 2064240.192 ops/s
TestArrayList.testLinkedListRemoveN_100 thrpt 2 1072619.806 ops/s接下来下调参数 n1000 a10 bn-a cn/2
随机向中间添加linkedlist快
add方法添加到最后linkedlist完胜
随机删除Arraylist快
删除靠前元素linkedlist快
删除中间的arralist快
删除后面的linkedlist快Benchmark Mode Cnt Score Error Units
TestArrayList.testArrayListRandonAdd avgt 0.912 us/op
TestArrayList.testLinkedListRandonAdd avgt 0.423 us/op
TestArrayList.testArrayListRandonAddLast avgt 0.788 us/op
TestArrayList.testLinkedListRandonAddLast avgt 0.042 us/op
TestArrayList.testArrayListRandonRemove avgt 0.194 us/op
TestArrayList.testLinkedListRandonRemove avgt 0.418 us/op
TestArrayList.testArrayListRemove100 avgt 0.211 us/op
TestArrayList.testLinkedListRemove100 avgt 0.043 us/op
TestArrayList.testArrayListRemoveNDividing2 avgt 0.189 us/op
TestArrayList.testLinkedListRemoveNDividing2 avgt 0.722 us/op
TestArrayList.testArrayListRemoveN_100 avgt 0.151 us/op
TestArrayList.testLinkedListRemoveN_100 avgt 0.039 us/op
