带数字 网站 域名,杭州做网站建设公司,商业空间设计文案,外贸网站建设智能建站ArrayList集合底层原理ArrayList集合底层原理1.介绍2.底层实现3.构造方法3.1集合的属性4.扩容机制5.其他方法6.总结ArrayList集合底层原理
1.介绍
ArrayList是List接口的可变数组的实现。实现了所有可选列表操作#xff0c;并允许包括 null 在 内的所有元素。 每个 Array…
ArrayList集合底层原理ArrayList集合底层原理1.介绍2.底层实现3.构造方法3.1集合的属性4.扩容机制5.其他方法6.总结ArrayList集合底层原理
1.介绍
ArrayList是List接口的可变数组的实现。实现了所有可选列表操作并允许包括 null 在 内的所有元素。 每个 ArrayList 实例都有一个容量该容量是指用来存储列表元素的数组的大小。它是至少等于列表的大小。随着向 ArrayList 中不断添加元素其容量也自动增长。自动增长会带来数据向新数组的重新拷贝因此如果可预知数据量的多少可在构造 ArrayList 时 指定其容量。
ArrayList集合特点为什么是增删慢、查询快
2.底层实现
底层使用数组实现
transient Object[] elementData;3.构造方法
ArrayList 提供了三种方式的构造器可以构造一个默认初始容量为 10 的空列表、构造 一个指定初始容量的空列表以及构造一个包含指定 collection 的元素的列表这些元素按照 该 collection 的迭代器返回它们的顺序排列的。
// 空参构造
ArrayListString list1 new ArrayList();
// 源码
public ArrayList() {/*DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 指向private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};空数组.注意:默认长度是在第一次添加元素时赋值的数组*/this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}// 指定初始长度
ArrayListString list2 new ArrayList(100);
// 源码
public ArrayList(int initialCapacity) {// 判断传入的长度大小if (initialCapacity 0) {// 根据长度创建数组this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {// 如果等于0,返回默认长度数组// EMPTY_ELEMENTDATAprivate: 指向static final Object[] EMPTY_ELEMENTDATA {};this.elementData EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}
}
// 包含指定 collection 的元素的列表
ListString list new ArrayList();
ArrayListString list3 new ArrayList(list);
// 源码
public ArrayList(Collection? extends E c) {// 先把传入的集合转成数组elementData c.toArray();// 判断集合的长度是否等于0if ((size elementData.length) ! 0) {// 判断数组字节码类型 为什么要判断,因为c.toArray()有可能转变的不是Object数组if (elementData.getClass() ! Object[].class)// copyOf把参数集合的元素拷贝到定义数组// elementData:要复制的数组// size:长度// Object[].class:要返回的新数组elementData Arrays.copyOf(elementData, size, Object[].class);} else {//EMPTY_ELEMENTDATA:指向:private static final Object[] EMPTY_ELEMENTDATA {};this.elementData EMPTY_ELEMENTDATA;}
}
3.1集合的属性
//默认容量的大小
private static final int DEFAULT_CAPACITY 10;//空数组常量
private static final Object[] EMPTY_ELEMENTDATA {};//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//存放元素的数组从这可以发现 ArrayList 的底层实现就是一个 Object数组
transient Object[] elementData;//数组中包含的元素个数
private int size;//数组的最大上限
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;4.扩容机制
图解:
扩容源码:
public boolean add(E e) {// 计数器,返回实时增加的元素个数,比如调用size()方法返回的集合元素个数modCount;/*1.e:表示现在要添加的元素2.elementData集合底层数组名3.size本次要添加的索引位置,第一次添加size的值为0*/add(e, elementData, size);return true;
}private void add(E e, Object[] elementData, int s) {// 判断存入的位置索引if (s elementData.length)// 调用grow方法进行扩容elementData grow();// 索引位置小于数组长度正常存入elementData[s] e;size s 1;
}private Object[] grow() {// 第一次存入元素size默认为0,进行长度加1return grow(size 1);
}private Object[] grow(int minCapacity) {/*创建一个新的数组长度为10把原来数组元素拷贝进去minCapacity:传入的容量*/return elementData Arrays.copyOf(elementData,newCapacity(minCapacity));
}private int newCapacity(int minCapacity) {// overflow-conscious code// 旧容量int oldCapacity elementData.length;// 新容量 旧容量 * 1.5int newCapacity oldCapacity (oldCapacity 1);// 拿新的容量 - 传入的大小 如果结果小于0,if (newCapacity - minCapacity 0) {// 第一次扩容// 判断数组是否是同一个数组if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// DEFAULT_CAPACITY默认容量10// 比较默认容量与传入容量大小,把最大返回return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity 0) // overflow 内存溢出throw new OutOfMemoryError();return minCapacity;}// 返回新的长度return (newCapacity - MAX_ARRAY_SIZE 0)? newCapacity: hugeCapacity(minCapacity);
}ArrayList的add方法在插入元素之前它会先检查是否需要扩容然后再把元素添加到数组中最后一个元素的后面。
在 newCapacity 方法中我们可以看见如果当 elementData 为空数组时它会使用默认的大小去扩容。所以说
通过无参构造方法来创建 ArrayList 时它的大小其实是为 0 的只有在使用到的时候才会通过 grow 方法去创建
一个大小为 10 的数组。第一个 add 方法的复杂度为 O(1)虽然有时候会涉及到扩容的操作但是扩容的次数是非常
少的所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法则复杂度为 O(n)因为涉及到
对数组中元素的移动这一操作是非常耗时的。5.其他方法
// 修改方法
public E set(int index, E element) {// 判断是否会发生异常Objects.checkIndex(index, size);// 根据索引获取元素E oldValue elementData(index);// 把传入的元素替换原来的元素elementData[index] element;// 返回原来的元素return oldValue;
}// 指定索引处添加,如果当前有元素,则向右移动当前位与该位置的元素以及所有后续元素
public void add(int index, E element) {// 判断是否发生异常rangeCheckForAdd(index);// 记录修改次数, 一般研究线程安全性问题,关注这个变量modCount;final int s;Object[] elementData;/*(s size):数组长度,下面拷贝使用了(elementData this.elementData):当前数组,下面有用到判断元素个数是否与数组长度相同*/if ((s size) (elementData this.elementData).length)// 数组扩容前面已经讲解elementData grow();// 将elementData中从index位置开始,长度为s-index的元素// 拷贝到从下标为index1位置开始的新的elementData数组中// 也就是当前位于该位置的元素以及后面的元素向后移动一位System.arraycopy(elementData, index,elementData, index 1,s - index);// 把元素赋值到指定索引处elementData[index] element;// 长度加一size s 1;
}// 返回此列表中指定位置上的元素。
public E get(int index) {// 判断异常Objects.checkIndex(index, size);// 返回元素return elementData(index);
}// 移除指定索引处元素
public E remove(int index) {// 判断异常Objects.checkIndex(index, size);// 临时变量数组赋值final Object[] es elementData;// 拿到指定索引处的元素SuppressWarnings(unchecked) E oldValue (E) es[index];fastRemove(es, index);return oldValue;
}
private void fastRemove(Object[] es, int i) {// 记录修改次数, 一般研究线程安全性问题,关注这个变量modCount;// 定义临时变量final int newSize;// 判断数组长度-1,是否大于变量索引if ((newSize size - 1) i)/*将es中从索引i1位置开始,长度为newSize - i的元素拷贝到从下表i 1位置开始的新的es数组中也就是当前位于该位置的元素以及后面的元素向前一定一位*/System.arraycopy(es, i 1, es, i, newSize - i);// 临时变量在赋值为nulles[size newSize] null;
}
// 移除指定元素
public boolean remove(Object o) {// 定义临时数组,并赋值final Object[] es elementData;// 定义临时长度变量,并赋值final int size this.size;int i 0;// found标识,发现指定元素found: {if (o null) {for (; i size; i)if (es[i] null)break found;} else {for (; i size; i)if (o.equals(es[i]))break found;}return false;}// 移除元素并移动fastRemove(es, i);return true;
}
6.总结 从上述代码中可以看出数组进行扩容时会将老数组中的元素重新拷贝一份到新的数组中每次数组容量的增长大约是其原容量的 1.5 倍。这种操作的代价是很高的因此在实际使用时我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时要在构造 ArrayList 实例时就指定其容量以避免数组扩容的发生。或者根据实际需求通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。
