资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/ArrayList源码解析

ArrayList源码解析

khlbat / 2350人阅读

摘要：说明是对中数组的扩展，其底层还是使用数据实现，支持自动扩容，不是线程安全的类。其继承，实现了各个接口，其中为支持随机读写的标记接口，在后续类的讲解中会用到。加上主要是为了不能直接序列化，而是必须使用自带的和方法，主要是为了节省空间。

1.说明

ArrayList是对java中数组的扩展，其底层还是使用数据实现，支持自动扩容，不是线程安全的类。其继承AbstractList，实现了List, RandomAccess, Cloneable,Serializable各个接口，其中RandomAccess为支持随机读写的标记接口，在后续Collections类的讲解中会用到。

2.优缺点

ArrayList是一个支持自动扩容的线性表，所以其与普通线性表的特点一样，如下：

顺序存储，所以按照下标读取元素的时间复杂度为O(1)

在删除元素时其后面的所有元素都得前移，新增元素时后面的所有元素都得后移

在存储时就需要开辟一块固定的存储空间

3.重要变量 
</>复制代码 
  1. //默认的容量，当构造函数没有传入此参数时，会在加入第一个元素时将数组扩容为此值
  2. private static final int DEFAULT_CAPACITY = 10;
  3.     
  4. //当数组中元素为空时，会将数组初始化为此数组，代表空数组，这个空数组是在传入
  5. 初始容量并且初始容量为0的情况下令数组等于这个
  6. private static final Object[] EMPTY_ELEMENTDATA = {};
  7. //与上一个变量的区别在于其是在于这个空数组是在使用无参构造函数时创建
  8. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  9. //这个数组用于ArrayList存储元素,ArrayList的容量就是数组的长度。加上transient主要是为了
  10. 不能直接序列化，而是必须使用自带的writeObject和readObject方法，主要是为了节省空间。不私有
  11. 化主要是为了以后扩展，防止以后嵌套等操作
  12. transient Object[] elementData; // non-private to simplify nested class access
  13. //ArrayList的实际大小，即元素所占个数
  14. private int size;
4.构造方法 
</>复制代码 
  1. //传入初始参数的构造方法
  2. public ArrayList(int initialCapacity) {
  3.         //如果初始容量大于0，那么直接按照初始容量初始化数组，
  4.           如果初始容量等于0，等于EMPTY_ELEMENTDATA，上文
  5.           的常量，不过不会在添加第一个元素的时候令容量等于DEFAULT_CAPACITY
  6.           如果初始容量小于0，直接抛出异常
  7.         if (initialCapacity > 0) {
  8.             this.elementData = new Object[initialCapacity];
  9.         } else if (initialCapacity == 0) {
  10.             this.elementData = EMPTY_ELEMENTDATA;
  11.         } else {
  12.             throw new IllegalArgumentException("Illegal Capacity: "+
  13.                                                initialCapacity);
  14.         }
  15. }
  16. //无参构造函数，直接令存储数组等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
  17.   在添加第一个元素的时候令容量等于DEFAULT_CAPACITY
  18. public ArrayList() {
  19.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  20. }
  21. //通过一个集合类来构造一个ArrayList
  22. public ArrayList(Collection c) {
  23.     //获取集合类的底层数组
  24.     elementData = c.toArray();
  25.     //判断集合类的元素个数是否为0
  26.     if ((size = elementData.length) != 0) {
  27.         //ps:c.toArray()可能返回的数组类型不为Object[]类型，
  28.           通过ArrayList的toArray一定是Object[]类型，但是Arrays.asList（）
  29.           里转化成其内部自身的ArrayList，其内部的ArrayList的toArray方法会
  30.           返回E[]这种泛型的对象，导致出现问题
  31.         //如果集合类的toArray方法返回的不为Object[]类型，使用Arrays.copyOf
  32.           将其迁移到一个新的Object[]数组中
  33.         if (elementData.getClass() != Object[].class)
  34.             elementData = Arrays.copyOf(elementData, size, Object[].class);
  35.         } else {
  36.             // 如果元素个数为0，那么直接将元素数组置为EMPTY_ELEMENTDATA空数组
  37.             this.elementData = EMPTY_ELEMENTDATA;
  38.         }
  39. }
5.基本方法 
</>复制代码 
  1. //增加一个新元素
  2. public void add(int index, E element) {
  3.         //检验index是否超出范围
  4.         rangeCheckForAdd(index);
  5.         //检验当前容量是否足够，如果不够，进行扩容
  6.         ensureCapacityInternal(size + 1);  
  7.         //将index之后的元素都后移一个
  8.         System.arraycopy(elementData, index, elementData, index + 1,
  9.                          size - index);
  10.         //将新增的元素填入
  11.         elementData[index] = element;
  12.         //添加数组元素个数
  13.         size++;
  14. }
  15. //检验index是否超出范围
  16. private void rangeCheckForAdd(int index) {
  17.         //判断index是否大于当前长度或者小于0，如果不在数组范围，
  18.           那么直接跑出数组超出范围异常
  19.         if (index > size || index < 0)
  20.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  21. }
  22. //确保内部元素的容量足够
  23. private void ensureCapacityInternal(int minCapacity) {
  24.         //对数组进行扩容
  25.         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  26.     }
  27. //用于判断数组是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此处用==号进行比较，是因为
  28.   只用于判断是构造函数时未传初始容量，延迟到第一次添加新元素时进行默认初始容量的设置，然后
  29.   返回比较默认容量与需要的最小容量的最大值，这里返回最大值是因为有可能一次添加多个元素，  AddAll也会复用这个函数
  30. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  31.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  32.             return Math.max(DEFAULT_CAPACITY, minCapacity);
  33.         }
  34.         return minCapacity;
  35.     }
  36. //对数组进行扩容
  37. private void ensureExplicitCapacity(int minCapacity) {
  38.         //修改次数+1
  39.         modCount++;
  40.         // 如果需要的容量数大于当前容量，进行扩容，否则，不在继续，
  41.           并且防止溢出，如果溢出，不进行下列操作，直接会在后续数组
  42.           赋值中直接抛出越界异常，因为这个时候代表size已经很大了
  43.         if (minCapacity - elementData.length > 0)
  44.             grow(minCapacity);
  45.     }
  46.     
  47.  //对数组进行扩容
  48.  private void grow(int minCapacity) {
  49.         int oldCapacity = elementData.length;
  50.         //令新的容量等于原容量的1.5倍
  51.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  52.         //如果新的容量小于当前需要的的最小容量，那么新容量等于当前需要的的最小容量
  53.           防止newCapacity溢出或者增加1.5倍还是小于minCapacity的情况
  54.         if (newCapacity - minCapacity < 0)
  55.             newCapacity = minCapacity;
  56.         //如果新的容量比MAX_ARRAY_SIZE还大，MAX_ARRAY_SIZE为
  57.           Integer.MAX_VALUE - 8，那么对当前需要的最小容量进行扩容
  58.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  59.             newCapacity = hugeCapacity(minCapacity);
  60.         //为数组开辟更大的空间
  61.         elementData = Arrays.copyOf(elementData, newCapacity);
  62.     }
  63.     //根据需要的容量进行扩容
  64.     private static int hugeCapacity(int minCapacity) {
  65.         //如果minCapacity此时小于0，代表已经溢出，其实此时已经不大可能，因为在
  66.           ensureExplicitCapacity已经有一层判断了
  67.         if (minCapacity < 0) 
  68.             throw new OutOfMemoryError();
  69.         //如果minCapacity小于MAX_ARRAY_SIZE，那么直接等于MAX_ARRAY_SIZE，
  70.           否则直接等于Integer的最大值
  71.         return (minCapacity > MAX_ARRAY_SIZE) ?
  72.             Integer.MAX_VALUE :
  73.             MAX_ARRAY_SIZE;
  74.     }
  75.     
  76.

下面，来看看Api中的add，addAll等方法，其他类似方法不在赘述，get和set也不赘述，比较简单

</>复制代码 
  1. //与add方法不同的是，他是在这个索引处新增了一个集合的元素
  2. public boolean addAll(int index, Collection c) {
  3.         //检验index是否合法
  4.         rangeCheckForAdd(index);
  5.         Object[] a = c.toArray();
  6.         int numNew = a.length;
  7.         //size + numNew代表需要的最小容量
  8.         ensureCapacityInternal(size + numNew);  
  9.         //numMoved代表需要向后移动的元素个数
  10.         int numMoved = size - index;
  11.         if (numMoved > 0)
  12.             System.arraycopy(elementData, index, elementData, index + numNew,
  13.                              numMoved);
  14.         //将集合c中的所有元素移动到elementData的index之后
  15.         System.arraycopy(a, 0, elementData, index, numNew);
  16.         size += numNew;
  17.         //如果集合c的长度不为0，返回true，否则返回false
  18.         return numNew != 0;
  19.     }
  20.     //将elementData中的空元素去除，节省空间(去除不了中间的等于null这样类型的元素)
  21.     public void trimToSize() {
  22.         modCount++;
  23.         //如果当前元素个数小于elementData的容量，当size == 0时
  24.           将elementData赋值为EMPTY_ELEMENTDATA，否则，将elementData
  25.           容量减小到size大小
  26.         if (size < elementData.length) {
  27.             elementData = (size == 0)
  28.               ? EMPTY_ELEMENTDATA
  29.               : Arrays.copyOf(elementData, size);
  30.         }
  31.     }
  32.     
  33.     //根据对应元素计算出元素位置（遍历为从前到后）
  34.     public int indexOf(Object o) {
  35.         //如果传入元素为null，找到等于null的元素，否则，使用
  36.           equals遍历
  37.         if (o == null) {
  38.             for (int i = 0; i < size; i++)
  39.                 if (elementData[i]==null)
  40.                     return i;
  41.         } else {
  42.             for (int i = 0; i < size; i++)
  43.                 if (o.equals(elementData[i]))
  44.                     return i;
  45.         }
  46.         return -1;
  47.     }
  48.     
  49.     //移除当前元素
  50.     public E remove(int index) {
  51.         rangeCheck(index);
  52.         modCount++;
  53.         //获取当前index在数组对应元素
  54.         E oldValue = elementData(index);
  55.         //获取需要移动的元素个数，即index之后的元素都需要向前移动，不包括index
  56.         int numMoved = size - index - 1;
  57.         if (numMoved > 0)
  58.             System.arraycopy(elementData, index+1, elementData, index,
  59.                              numMoved);
  60.         //将最后一个元素置为空，其中的元素有gc自动回收
  61.         elementData[--size] = null; 
  62.         //返回被删除的元素值
  63.         return oldValue;
  64.     }
  65.     
  66.     //对对应元素进行移除，先遍历查找，在进行移除，值得一提的是，
  67.       此处的remove方法，使用的是fastRemove，与remove方法具体
  68.       少了rangeCheck方法和获取oldValue，从而减少时间复杂度
  69.     public boolean remove(Object o) {
  70.         if (o == null) {
  71.             for (int index = 0; index < size; index++)
  72.                 if (elementData[index] == null) {
  73.                     fastRemove(index);
  74.                     return true;
  75.                 }
  76.         } else {
  77.             for (int index = 0; index < size; index++)
  78.                 if (o.equals(elementData[index])) {
  79.                     fastRemove(index);
  80.                     return true;
  81.                 }
  82.         }
  83.         return false;
  84.     }
  85.     
  86.
云服务器 GPU云服务器 ArrayList源码 源码解析 webrtc源码解析 webrtc 源码解析

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77240.html

相关文章

  • Java集合之ArrayList源码解析

    摘要：数组的大小会根据容量的增长而动态的增长，具体的增长方式请看这里构造函数提供了三种方式的构造器。这些元素按照该的迭代器返回的顺序排列的。 原文地址 ArrayList ArrayList是List接口的 可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。ArrayList继承自 A...

    W4n9Hu1 评论0 收藏0

  • java源码

    摘要：集合源码解析回归基础，集合源码解析系列，持续更新和源码分析与是两个常用的操作字符串的类。这里我们从源码看下不同状态都是怎么处理的。 Java 集合深入理解：ArrayList 回归基础，Java 集合深入理解系列，持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMi...

    Freeman 评论0 收藏0

  • ArrayList源码解析之fail-fast机制深入理解

    摘要：当多个线程对同一个集合的内容进行操作时，就可能会产生事件。当某一个线程遍历的过程中，的内容被另外一个线程所改变了就会抛出异常，产生事件。在线程在遍历过程中的某一时刻，线程执行了，并且线程删除了中的节点。 概要 前面，我们已经学习了ArrayList。接下来，我们以ArrayList为例，对Iterator的fail-fast机制进行了解。 1 fail-fast简介 fail-fast...

    NikoManiac 评论0 收藏0

  • List集合就这么简单【源码剖析】

    摘要：线程不安全底层数据结构是链表。的默认初始化容量是，每次扩容时候增加原先容量的一半，也就是变为原来的倍删除元素时不会减少容量，若希望减少容量则调用它不是线程安全的。 前言 声明，本文用得是jdk1.8 前一篇已经讲了Collection的总览：Collection总览，介绍了一些基础知识。 现在这篇主要讲List集合的三个子类： ArrayList 底层数据结构是数组。线程不安全 ...

    cpupro 评论0 收藏0

  • LinkedList源码解析

    摘要：我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针，能指向下一个节点，无需做额外的遍历，速度非常快。不同的遍历性能差距极大，推荐使用迭代器进行遍历。LinkedList类介绍 上一篇文章我们介绍了JDK中ArrayList的实现，ArrayList底层结构是一个Object[]数组，通过拷贝，复制等一系列封装的操作，将数组封装为一个几乎是无限的容器。今天我们来介绍JD...

    roundstones 评论0 收藏0

发表评论

登陆后可评论

0条评论

khlbat

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<