河北建设厅官方网站电话,推广app渠道,芒果国际影城星沙店,网站属性设置前言#xff1a;ArrayList作为我们常用的一个集合数据类型#xff0c;我们在代码中经常用它来装载数据#xff0c;可谓是和HashMap一样常用的集合类型了。我们经常用它#xff0c;那么就有必须知道它的内部工作原理#xff0c;比如它是如何添加进去数据的#xff0c;它内… 前言ArrayList作为我们常用的一个集合数据类型我们在代码中经常用它来装载数据可谓是和HashMap一样常用的集合类型了。我们经常用它那么就有必须知道它的内部工作原理比如它是如何添加进去数据的它内部的数据结构是怎样的当我们做一个remove操作它又做了哪些工作。了解这些内部工作的原理能够帮助我们更好的理解Arraylist什么时候使用它和不使用它如何提升它的效率等等。那么本篇博文就来聚焦Arraylist走进它的内部源码来一探究竟吧。 本篇博客的目录 一Arraylist简介 二Arrsylist的构造方法 三Arraylist的add和remove方法分析 四Arraylist的常用方法源码分析 五Arrraylist与linkedlist的区别 六总结 一Arraylist简介 首先是Arraylist一种java的数据容器作为数据容器我们在程序中经常使用它比如Map、Collection、HashMap、TreeSet等等。如它的名字一样它的内部结构是数组而这个数组是可以动态扩容的就犹如hashMap一样。它的所有操作都是基于其内部的动态数组来进行操作list接口的大小可变数组的实现、如果1-1所示其中index表示的是数组的元素的位置,但注意其数组下标实际是从0开始的而不是1源码中多次涉及到index这个变量在这里可以先理解一下。其次它本质上一个类实现了list接口继承了AbstractList和Cloneable接口、Serializable表明其继承于抽象的list并且可以进行浅复制和序列化写入到数据文件中。同时它在构建的时候就说明了其类型泛型E所以Arraylist是一种在新建时就声明其包含类型的集合并且可支持复制、序列化、克隆等特性。 public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable 二Arrsylist的成员变量和构造方法 我们先来看一看Arraylist的成员变量从中可以看到Arraylist维护着的数组和一些基本的数值表示出它的大小和数据类型之所以声明为Object类型的是因为要定义一个适用于所有java数据类型的这样它就可以向下转型为所有基本类型了。至于元素容量为什么是10而不是11或者12这个可能是jdk的作者经过计算、根据使用习惯计算出来的有一定的科学依据。这些都是全局变量也就是说下面的方法都可以访问这些变量并修改它的值。 private static final long serialVersionUID 8683452581122892189L; //序列版本号private static final int DEFAULT_CAPACITY 10;//默认数组元素的初始容量为10private static final Object[] EMPTY_ELEMENTDATA {};//空元素对象数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//默认容量的空数据数组transient Object[] elementData; // 数组元素对象list中的元素就存在这里private int size;//添加的元素的数量 看完了成员变量我们来看一下Arraylist的3个构造函数其中我们用到的最多的也就是第二个无参的构造函数平时代码里我们经常这样写ListString list new Arraylist()String;这就是调用了其第二个构造函数在构造函数里面我们可以看到它对空数组进行了赋值将维护着的数组的大小设为10个容量然后我们就可以使用这个list了。接下来我们就讲一讲如何往这个list里面增添元素和移除元素这是我们使用list最常用的两个方法。 public ArrayList(int initialCapacity) { //初始化容量 if (initialCapacity 0) { //判断传入的参数值this.elementData new Object[initialCapacity];//把传入的容量作为数组的初始容量} else if (initialCapacity 0) {//如果传入的是0this.elementData EMPTY_ELEMENTDATA;//初始化为空数组} else {throw new IllegalArgumentException(Illegal Capacity: //传入的如果小于0就抛出参数违规异常initialCapacity);}}public ArrayList() { //空构造方法this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//空对象数组初始化其容量为10}public ArrayList(Collection? extends E c) {//传入一个泛型的集合elementData c.toArray();//默认空数组if ((size elementData.length) ! 0) { //// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() ! Object[].class)elementData Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData EMPTY_ELEMENTDATA;}} 三Arraylist的add和remove方法分析 1.add方法的解析 我们先来看一下add方法这其中又涉及到了rangeCheckForAdd方法和ensureCapacityInternal、System.arraycopy方法我们来依次分析一下其中的源码看看究竟在我们add一个元素的时候Arraylist做了什么 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;//数组大小增加} private void rangeCheckForAdd(int index) { //专为add方法增加的返回检查if (index 0 || index this.size)//如果传入的参数小于0或者大于数组已添加元素的个数throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//抛出异常} private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;//定义数组最大的值为Integer最大值-8private void ensureCapacityInternal(int minCapacity) {//确保容量if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果数组元素等于默认的空数组容量minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);//取默认的容量和指定的容量的较大值}ensureExplicitCapacity(minCapacity);//传入 ensureExplicitCapacity方法确保扩展的容量} private void ensureExplicitCapacity(int minCapacity) {/确保扩展容量modCount;//修改次数1// overflow-conscious codeif (minCapacity - elementData.length 0)//如果指定的容量大于数组容量grow(minCapacity);//调用gorw方法} private void grow(int minCapacity) { //传入指定的容量// overflow-conscious codeint oldCapacity elementData.length;//取旧的数组元素的长度int newCapacity oldCapacity (oldCapacity 1);//旧长度除以2长度赋予新长度相当于扩容1.5倍if (newCapacity - minCapacity 0)//如果新长度小于指定的容量newCapacity minCapacity;//把新计算的长度赋予指定的容量if (newCapacity - MAX_ARRAY_SIZE 0)//如果新容量最大数组大小newCapacity hugeCapacity(minCapacity);//调用bugeCapcaity方法elementData Arrays.copyOf(elementData, newCapacity);//复制数组} private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // 如果指定容量小于0throw new OutOfMemoryError();//抛出异常内存错误return (minCapacity MAX_ARRAY_SIZE) ?//如果指定容量大于最大数组大小返回int的最大值Integer.MAX_VALUE :MAX_ARRAY_SIZE;//否则返回最小数组大小} 通过源码我们可以看出Arraylist在添加元素的时候首先进行的是范围检查防止其传入的参数小于0或者超过数组的size大小再是和默认分配的大小值进行比较如果大于默认大小就要进行扩容。扩容的时候首先把旧数组的大小提升1.5倍成为新数组的大小值。同时也可以看到Arrylist的大小边界是Interger的最大值这个数字是很大的2147483647也就是它的最大值是这么多这个值足以我们程序员平常进行使用在检查完毕和扩容完毕之后就是要进行数组的拷贝了我们开看一下System.arrayCopy()方法的源码 public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length); 其中可以看出它是native修饰的也就是说它是一个引用本地其他语言的代码库windows就是.dll库的方法具体的源码我们不深究了这里解释一下它的参数src你要从哪个数组复制srcpos:要复制的位置起点 dest要复制要哪个数组destPos要复制到的数组起始位置 lengh:复制的长度 System.arraycopy(elementData, index, elementData, index 1, size - index); 代入add方法里也就是说把elementData的从index开始的元素复制size-index长度到elementData中从index1开始。这是一个自我复制的过程为了保证数据的完整。然后把指定的元素值放入到指定的位置中。我们来用图解释一下这个复制的过程首先是图1-1表示的是一共有5个元素那么这个数组的size就是5.我们现在要在index2的位置上插入元素六。我们来看看通过arraycopy方法之后的数组是什么样的如图1-2。然后调用lementData[index] element方法之后数组就会变成图1-3可见我们要插入的元素六就这样插入到指定位置上了从中也可以看出自我复制也就是数组的元素从指定的位置向后移动这也间接说明了Arraylist插入数据的效率比较低因为它要移动数据。 图 1-3 2remove方法 我们看romove方法首先还是进行范围检查然后用elementData()方法去找到指定数组元素中的值再用size-index-1转为numMoved接着进行再次自我复制。然后把size-1甚至设置为null。这样这个数组中元素就是null了。 public E remove(int index) {//根据指定位置移除元素rangeCheck(index);//范围检查
modCount;//修改次数1E oldValue elementData(index);//根据数组元素的位置找到旧值int numMoved size - index - 1;if (numMoved 0)//判断是否大于0System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null; // return oldValue;//返回旧值} 为了更好的理解remove方法我们来用画图的方式理解一下其中一二三到十使我们存放的值如图2-1.那么这个数组的size10假如我们移除remove(3),则index3,我们可以看到index2对应的值是四然后numMoved的值是7大于0。然后进行自我复制。从elementData的index3开始复制之后的结果如图2-2可以看出从index开始的位置所有的元素往前移动了一位这就是arraycopy方法的根本目的然后再把 elementData[--size] null; 也就是最后一个元素十置为null这样数组的大小就自然减-1并且顺利的移出了指定位置的元素。这就是remove方法原理 图 2-1 图 2-2 四Arraylist的常用方法源码分析 我们再来看一下Arraylist中一些常见方法的源码其中包括返回其大小的方法判断是否为空的方法。是否包含某个元素的方法等等这些方法比较简单我只列出了基本的注释。 public int size() {//取其大小return size;//返回size的数组}public boolean isEmpty() {//判断list是否为空return size 0;//用其size和0去比较}public boolean contains(Object o) {//判断指定元素是否包含return indexOf(o) 0;//返回indexof方法的返回结果是否大于0。大于0表示含有如果小于0表示没有}public int indexOf(Object o) {//检索指定元素是否存在if (o null) {//如果元素为nullfor (int i 0; i size; i)//遍历循环整个数组if (elementData[i]null)//如果找到元素为nullreturn i;//返回元素中的位置} else {//如果不为nullfor (int i 0; i size; i)//遍历循环数组if (o.equals(elementData[i]))//如果指定元素和数组中的元素相同return i;//返回数组中的位置}return -1;//否则返回-1}public int lastIndexOf(Object o) {//从末尾检索指定元素if (o null) {//如果元素为nullfor (int i size-1; i 0; i--)//按照元素从大到小if (elementData[i]null)//如果元素为nullreturn i;//返回数组中的位置} else {//如果元素不为nullfor (int i size-1; i 0; i--)//按照元素从大到小if (o.equals(elementData[i]))//如果元素等于数组中的元素return i;//返回数组中的位置}return -1;//否则返回-1} public boolean remove(Object o) {//判断元素是否能够移除if (o null) {//如果元素为nullfor (int index 0; index size; index)//if (elementData[index] null) {//如果元素值为nullfastRemove(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;//修改次数1int numMoved size - index - 1;//从指定元素的下一个开始if (numMoved 0)//如果元素的下一个大于0System.arraycopy(elementData, index1, elementData, index,numMoved);//拷贝数组elementData[--size] null; //数组对象的最后一个值赋值为null }public void clear() { //清除元素modCount;//修改次数1for (int i 0; i size; i)//遍历循环整个数组elementData[i] null;//将其值设为null便于GC回收
size 0;//size等于0} 五Arraylist与linkedlist的区别 1.从本篇博文中可以看出ArrayList基于动态数组的数据结构但是LinkedList基于链表的数据结构。 2Arraylist是有序的元素它是按照固定的顺序排列每次都往后移动一位并且很容易可以看出它是允许值为null。而linkedlist是无序的。 3.对于随机访问get和setArrayList觉得优于LinkedList因为LinkedList要移动指针。 我们在这里看一下get方法的源码其中可以看出其只需要做个范围检查然后就可以通过数组的位置计算 处其位置上的值这也是数组的特点获取数组很快。但是linkedlist是链表结构的所谓结构决定功能链表的获取元素时候需要一层层去节点里面遍历这无疑增加了工作量所以linked的随机 访 问要落后与Arraylist public E get(int index) {//根据指定位置返回对应的值rangeCheck(index);//调用范围检查的方法防止其越界return elementData(index);//把参数传入调用elementData()方法} 4.对于新增和删除操作add和removeLinkedList有很大的优势因为ArrayList要移动数据 我们通过比对发现add和remove方法它们都要经过System.arrayCopy()方法进行数据的移动比较麻烦而基于链表的结构的LinkedList则只需要进行值和位置的封装然后放入链表即 可。 5:Arraylist是非线程安全的其中我们可以看出它并没有同步机制的实现也没有synchronize等关键字的修饰。所以在多线程的环境下慎用Arraylist。同时linkedList也并非线程安全的 六总结 本篇博文介绍了Arraylist的源码从其中可以看出jdk设计者的巧妙包括其add方法的校验防止校验还有动态扩容的特性它作为一个我们在实际开发中常用的数据容器按照从全局变量到构造方法再到其add、remove方法的学习我们对arraylist也有了进一步的认知同时与linkedlist进行了对比以便于我们更好的掌握Arraylist!好了本次博客就到这里结束了。 转载于:https://www.cnblogs.com/wyq178/p/6986363.html
