ArrayList 源码分析(未完待续)
首先ArrayList 底层是数组结构的。数组结构意味着 大数量的增加和删除比较慢,查询会比较快。
期次arrayList不是线程安全的。
继承了AbstractList 和 实现了io list randomAccess serializable等接口
jdk7与jdk8对比
jdk8:
ArrayList中维护了Object[] elementData,初始容量为0.
第一次添加时,将初始elementData的容量为10
再次添加时,如果容量足够,则不用扩容直接将新元素赋值到第一个空位上
如果容量不够,会扩容1.5倍
jdk7:
ArrayList中维护了Object[] elementData,初始容量为10.
添加时,如果容量足够,则不用扩容直接将新元素赋值到第一个空位上
如果容量不够,会扩容1.5倍
jdk7和jdk8区别:
jdk7 相当于饿汉式,创建对象时,则初始容量为10
jdk8 相当于懒汉式,创建对象时,并没有初始容量为10,而在添加时才去初始容量为10
/* * 用数组实现的集合,支持随机访问,元素有序且可以重复 * RandomAccess(ArrayList) 支持快速随机访问,使用for循环更加快速 * LinkedList 使用 iterator迭代器更加 快速 * RandomAccess 这是一个标记接口,一般此标记接口用于 List 实现,以表明它们支持快速(通常是恒定时间)的随机访问。 * 该接口的主要目的是允许通用算法改变其行为,以便在应用于随机或顺序访问列表时提供良好的性能 * 包含类中的基础属性和3个构造方法 */ public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { /** * 默认长度 10 */ private static final int DEFAULT_CAPACITY = 10; /** * 默认空的数组 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * ArrayList中的元素 是Object[]类型的数组 */ transient Object[] elementData; // non-private to simplify nested class access /** * 动态数组的实际大小 ,默认为0 * @serial */ private int size; /** * 最大数组容量2147483639 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 集合长度构造函数 */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } /** * 无参构造函数,设置元素数组为空 注意此时初始容量是0,而不是大家以为的 10 */ public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; } /** * 集合参数构造函数 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); // 转化为数组 size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) //是否成功转化为Object类型数组 elementData = Arrays.copyOf(elementData, size, Object[].class); //不为Object数组的话就进行复制 }
1)add(E);//默认直接在末尾添加元素
/** * 新增元素 */ public boolean add(E e) { //赋值初始长度 或者扩容,新增元素,当前实际size+1的长度 ensureCapacityInternal(size + 1); // Increments modCount!! //添加元素 elementData[size++] = e; return true; } /** * 确保elemenData数组有合适的大小 * 如果元素为空,则复制长度默认为10 或者更大*/ private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) {//如果数组为空,则从size+1的值和默认值10中取最大的 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } /** * 确保elemenData数组有合适的大小 * 如果长度大于元素长度则扩容 */ private void ensureExplicitCapacity(int minCapacity) { //记录修改次数,迭代中不一致会触发fail-fast机制,因此在遍历中删除元素的正确做法应该是使用Iterator.remove() modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); //扩容 } /** * 扩容 */ private void grow(int minCapacity) { int oldCapacity = elementData.length; // 旧容量 int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍 if (newCapacity - minCapacity < 0) // 新容量小于参数指定容量,修改新容量 newCapacity = minCapacity; 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); } //如果小于0 就报错,如果大于最大值 则取最大值 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
2)add(int index, E element);//给指定下标,添加元素
/** * 给指定下标,添加元素 */ public void add(int index, E element) { //判断下标是否越界 rangeCheckForAdd(index); //赋值初始长度 或者扩容 ensureCapacityInternal(size + 1); // Increments modCount!! //将源数组中从index位置开始后的size-index个元素统一后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); //赋值 elementData[index] = element; size++; } /** * 判断下标是否越界 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * src:源数组 * srcPos:源数组要复制的起始位置 * dest:目的数组 * destPos:目的数组放置的起始位置 * length:复制的长度 * 注意:src 和 dest都必须是同类型或者可以进行转换类型的数组 */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
正常情况下会扩容1.5倍,特殊情况下(新扩展数组大小已经达到了最大值)则只取最大值。
1)remove(int index); //根据指定下标 删除元素
/** * 根据指定下标 删除元素 */ public E remove(int index) { //判断索引是否越界 rangeCheck(index); modCount++; //获取旧元素 E oldValue = elementData(index); //将数组elementData中index位置之后的所有元素向前移一位 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //将原数组最后一个位置置为null,由GC清理 elementData[--size] = null; // clear to let GC do its work return oldValue; }
ArrayList总结
1)ArrayList可以存放null,本质是Object[]类型的数组。 2)ArrayList区别于数组的地方在于能够自动扩展大小,其中关键的方法就是gorw()方法。 3)ArrayList由于本质是数组,所以它在数据的查询方面会很快,而在插入删除这些方面,性能下降很多, 有移动很多数据才能达到应有的效果,而LinkedList则相反。 4)ArrayList实现了RandomAccess,所以在遍历它的时候推荐使用for循环。 5)初始化数组时推荐给初始长度,反复扩容会增加时耗,影响性能效率。 6) Arrays工具类用来处理数组的工具类,Arrays.asList()方法返回的 ArrayList 数组是一个定长列表, 7) 我们只能对其进行查看或者修改,但是不能进行添加或者删除操作,不能执行影响长度的操作, 8) 因为此ArrayList是Arrays中内部静态类,只实现了部分查看修改方法,添加和删除方法是 9) 继承AbstractList父类的空方法,此ArrayList非彼ArrayList。来源:https://blog.51cto.com/hackerxian/2426030
相关推荐
源码物语 2020-07-18
XGQ 2020-06-21
shayuchaor 2020-04-20
xiaouncle 2020-07-31
fengyun 2020-06-14
OldBowl 2020-06-11
zagnix 2020-06-04
xhao 2020-06-04
付春杰Blog 2020-05-31
ilovewqf 2020-05-30
shenxiuwen 2020-05-29
XGQ 2020-05-26
zhuyonge 2020-05-09
zcpHappy 2020-04-30
luohui 2020-04-29
fraternityjava 2020-04-29
willluckysmile 2020-04-24
fengyun 2020-04-17