联博统计:ArrayList详解-源码剖析

admin 4个月前 (05-21) 科技 41 0

ArrayList详解-源码剖析

1. 概述

在平时的开发中,用到最多的聚集应该就是ArrayList了,本篇文章将连系源代码来学习ArrayList。

  • ArrayList是基于数组实现的聚集列表
  • 支持随便性的接见(可凭据索引直接获得你想要的元素)
  • 线程不安全
  • 支持动态扩容
  • 查询快,增删慢
  • ...

这些人人应该都很清晰,下面凭据源代码来深入剖析一下ArrayList。

2. ArrayList类声明

源代码如下所示:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

开端剖析:

  1. ArrayList类继续于AbstractList抽象类
  2. ArrayList类实现了List、RandomAccess、Cloneable、Serializable接口

继续剖析一下:

  • AbstractList抽象类实在已经实现了Collection接口中大部门方式
  • 实现了RandomAccess接口,以是支持随便性接见(随机接见)
  • 实现了Cloneable接口,说明重写了 clone()方式,支持拷贝(Cloneable 接口只是个正当挪用 clone() 的标识(marker-interface),一个工具想挪用clone()方式,则该类必须实现Cloneable 接口,否则会报错 CloneNotSupportedException
  • 实现了Serializable接口,支持序列化操作

3. 成员变量

源代码如下所示:

    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    
    private int size;

开端思索:

  1. 一共有6个变量,各自的作用?

  2. 有两个空数组,只是命名不一样,为什么?

继续剖析:

  1. 各个变量的作用:
    • serialVersionUID: 序列化版本号
    • DEFAULT_CAPACITY:默认容量巨细
    • EMPTY_ELEMENTDATA:空数组时的引用
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA:初始化时默认的空数组
    • elementData:现实存储聚集元素的数组
    • size:现实元素的数目(int类型默认值为0
  2. 两个空数组:
    • 划分用于默认初始化和传入容量时的初始化

4. 组织方式

源代码如下所示:

    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);
        }
    }

   
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    
    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;
        }
    }

开端思索:

  1. 提供了三个组织方式
  2. 划分对应无参组织、指定聚集容量的组织以及通过Collection的子类来组织一个ArrayList工具

继续剖析:

  1. 无参组织:

    • 直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组赋值给elementData(注重:此时ArrayList的数组长度照样0
  2. 指定容量组织:

    • 参数大于0: 建立一个该参数巨细的数组,赋值给elementData
    • 参数即是0: 将成员变量EMPTY_ELEMENTDATA数组赋值给elementData
    • 参数小于0: 抛出异常
  3. 传入Collection子类工具组织:

        public ArrayList(Collection<? extends E> c) {
            /**
            *将传入的聚集转换为一个Object类型的数组,并将此数组的引用赋给elementData
            */
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {// 转换后的数组不为空时
                /**
                * 判断转换后的数组是不是Object[]数组
                * 若是不是的话,就把它复制为一个Object[]数组,举行赋值
                */
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // 转换后的数组为空,用成员变量EMPTY_ELEMENTDATA来辅助
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    

    toArray()方式源代码如下:

    public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }
    

    Arrays类的copyOf()方式源代码如下:

     @SuppressWarnings("unchecked")
        public static <T> T[] copyOf(T[] original, int newLength) {
            // 此处的copyOf()挪用了本类的重载方式
            return (T[]) copyOf(original, newLength, original.getClass());
        }
    

    重载方式源代码如下所示:

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }
    

    代码剖析:

    • 使用三元运算符举行判断传入数组的类型

    • 若是传入的数组类型强转为Object[]数组为true,则建立一个Object[newLength]数组赋值给copy

    • 若是为false,则行使反射获取到传入数组的类型,建立一个该类型的指定长度的数组赋值给copy

  • 挪用native方式举行赋值

  • 最后返回copy

    挪用链最后挪用到了native方式上:

    public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,
                                            int length);
    /**
    * 参数说明:
    * src:源工具 
    * srcPos:源数组中的起始位置 
    * dest:目的数组工具 
    * destPos:目的数据中的起始位置 
    * length:要拷贝的数组元素的数目
    */
    

源代码中最后都挪用到了native方式,只能看到方式名和参数,看不到详细的实现,对native方式做个简朴的先容吧。

native声明的接口方式: Java代码和内陆C代码举行互操作的API,称为Java Native Interface (Java内陆接口)。也就是说,带有native符号的方式,都是使用C语言来实现的,读者领会到这里即可,感兴趣的可以去查阅下相关资料,这里就不多论述了。

5. 常用方式剖析

  • add(E e)

源代码如下所示:

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

开端剖析:

  1. 挪用一个ensureCapacityInternal()方式,ensure Capacity Internal 直接谷歌翻译,意思是确保内部容量,此方式内应该就隐藏着ArrayList动态扩容的方式了!
  2. 将传入参数e,赋值给elementData[]数组中下标为size++的元素
  3. 返回true

继续跟踪ensureCapacityInternal()方式,该方式相关源代码如下所示:

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

剖析:

  1. 先对elementData数组举行空数组判断,注重:这里是直接使用 ==运算符来举行判断的,回首下前面讲到的ArrayList的无参组织方式
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

发现了没?若是使用默认的组织方式,挪用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,执行add()方式之前,ArrayList数组的长度都是,添加第一个元素后,数组的长度就变为10了。

  1. 下一个方式是ensureExplicitCapacity(),我们继续跟踪。

该方式源代码如下所示:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

开端剖析:

  • 泛起了一个前面没看到的变量modCount
  • 内里另有一个grow()方式,ArrayList能够动态扩容的缘故原由就在这个方式内里了,八九不离十了!grow这个单词我照样熟悉的,哈哈哈~~~

继续剖析:

  1. 经由追踪,发现modCount是ArrayList 的父类AbstractList的一个成员变量,作用是纪录ArrayList的size转变,添加元素时,该变量会自增一次。
  2. minCapacity变量是要添加元素在elementData数组里的索引,当该变量值跨越elementData数组长度的时刻,elementData数组就要举行动态扩容了!

接下来,看下grow()方式的源代码,马上就要揭开ArrayList能够动态扩容的根本缘故原由了,想想另有些激动,哈哈~

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }

剖析:

  1. 将当前未添加新元素的elementData的数组长度赋值给oldCapacity变量,示意旧数组的容量

  2. 界说一个变量newCapacity,示意新数组的容量,新数组的容量巨细为旧数组容量的1.5倍

    • 此处用到了移位操作,>>是移位运算符,示意带符号数右移
    • 向右移动n位,等同于除以2的n次方
  3. 此处需要注重一个地方,若是oldCapacity + (oldCapacity >> 1)执行的效果跨越了int的最大值,即2的31次方减1,那么新数组的长度将变为负数

  4. 下面就是对照新数组容量和旧数组的容量,将较大的容量赋值给新数组

  5. 若是新数组的容量巨细跨越了界说的MAX_ARRAY_SIZE巨细,那么将挪用hugeCapacity()方式

代码如下:

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  • 传入的容量是负数,思量到了数值溢出,抛出异常

  • 传入的容量跨越了MAX_ARRAY_SIZE巨细,则将Integer.MAX_VALUE的值举行返回,否则返回MAX_ARRAY_SIZE

  1. 最后挪用Arrays.copyOf()方式,将旧数组复制到新数组中,至此便完成了数组的动态扩容
  • add(int index, E element)

源代码如下所示:

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

基于add()方式的剖析,剖析如下:

  1. 判断索引是否越界
  2. 复制数组,举行移动
  3. 将传入参数赋值给指定下标的数组元素
  4. 聚集长度加1

rangeCheckForAdd()方式源代码如下所示:

private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

剖析如下:

  • 索引的上限是现实元素的长度,下限是0
  • 跨越这两个界限值就会抛出异常

注重:由于此处判断局限上限取的现实元素的个数,那么就会造成一个情形,我们使用指定容量的组织方式,建立了一个ArrayList工具,然后使用add(int index, E element)方式时,当添加的index不是0时,就会报错

举例如下:

public static void main(String[] args) {
		
		List<String> a = new ArrayList<>(12);// 初始化指定了数组的容量为12
		a.add(5, "element");
		
	}
//效果如下:
//  Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 5, Size: 0
//	 at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:661)
//	 at java.util.ArrayList.add(ArrayList.java:473)
//	 at test.TestAddArrayList.main(TestAddArrayList.java:11)
  • get(int index)

源代码如下所示:

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

E elementData(int index) {
        return (E) elementData[index];
    }

简要剖析:

  1. 首先判断索引是否在准确的局限之内,此处仅仅只是判断了上限为现实元素个数
    • 跨越上限时的报错提醒信息为 "Index: "+index+", Size: "+size
    • 当index为负数时的报错提醒信息则是:index,仅仅只是显示你接见的index值
  2. 挪用elementData()方式,直接返回对应索引位置的元素
  • remove(int index)

源代码如下所示:

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        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

        return oldValue;
    }

剖析:

  1. 首先对index举行判断是否在准确的局限内
  2. 移除元素使得数组长度发生了转变,以是modCount++
  3. 盘算需要移动的元素个数
  4. 挪用arraycopy()方式举行数组元素的复制和移动
  5. 将数组现实长度的最后一位元素赋值为null,利便GC举行接纳
  6. 最后返回索引位置的元素

不难看出,移除元素现实上也是数组的复制和移动

  • indexOf(Object o)

源码如下所示:

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

indexOf方式是返回某元素在ArrayList工具里的下标(索引)。

剖析:

  1. 区分两种情形

  2. 查询元素为null时,使用==运算符举行判断,返回索引

  3. 非null元素时,使用equals()方式来判断(ps:由此处挪用的equals()方式,可以看出为什么不支持基本类型的元素

  4. 当查询的元素不存在列表中,返回-1

ArrayList中另有许多方式,篇幅有限,在此不再赘述。

6. 总结

ArrayList是开发中用的最多了一个聚集类了,许多时刻我们只是停留在使用上面,没有深入的去学习,剖析,为什么是这样?为什么会这样?有时刻遇到问题了,也只能两眼一抹黑,不知道详细缘故原由是什么,多看源码,多学习,提高解决问题的能力,一点点的提高,就好。

,

申慱手机下载版

欢迎进入申慱手机下载版!Sunbet 申博提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet客户端下载、Sunbet代理合作等业务。

皇冠APP声明:该文看法仅代表作者自己,与本平台无关。转载请注明:联博统计:ArrayList详解-源码剖析

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:544
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1015
  • 评论总数:168
  • 浏览总数:3181