JDK源码阅读（三）：ArrayList源码解析

2020-05-28 00:00:00 索引 删除 元素 数组 方法


今天来看一下 ArrayList 的源码

  • 目录

    • 介绍

    • 继承结构

    • 属性

    • 构造方法

    • add 方法

    • remove 方法

    • 修改方法

    • 获取元素

    • size() 方法

    • isEmpty 方法

    • clear 方法

    • 循环数组

1. 介绍

一般来讲文章开始应该先介绍一下说下简介。这里就不介绍了 如果你不知道 ArrayList 是什么的话就没必要在看了。大致讲一下一些常用的方法

2. 继承结构

ArrayList 源码定义：

ArrayList 继承结构如下：

  • Serializable 序列化接口

  • Cloneable 前面我们在看 Object 源码中有提到这个类，主要表示可以进行克隆

  • List 主要定义了一些方法实现

  • RandomAccess 也是一个标记类，实现 RandomAccess 表示该类支持快速随机访问。

3. 属性

ArrayList 中的主要属性方法有：

初始化容量，默认为 10

  1. private static final int DEFAULT_CAPACITY = 10;

空数组

  1. private static final Object[] EMPTY_ELEMENTDATA = {};

也是一个空数组，和上面的数组相比主要的作用是在添加元素的时候知道数组膨胀了多少。

  1. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 的大小

  1. private int size;

注意 ArrrayList 中有一个 modCount 成员变量，来记录修改次数，主要是在使用迭代器遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素数量发生改变）了，主要在多线程环境下需要使用，防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构。好好认识下这个异常：ConcurrentModificationException。对了，ArrayList 是非线程安全的。

4. 构造方法

我们来看一下 ArrayList 的构造方法
无参构造方法：

可以看出无参构造会直接创建一个指定 DEFAULTCAPACITYEMPTYELEMENTDATA 的数组，而 DEFAULTCAPACITYEMPTYELEMENTDATA 数组默认是空的。

所以在执行一下代码的时候 ArrayList 默认创建的是一个初始化容量为 0 的数组。

  1. ArrayList list = new ArrayList();

有参构造方法：

传入创建数组的大小，如果大于 0 就创建一个传入参数大小的数组，如果等于 0 就就指定为空数组。如果小于 0 就会抛异常。

看源码我们可以看到传入 Collection 的构造方法做的事情就是复制数组，将已有的集合复制到新的集合中。

5.add 方法

ArrayList 底层是用数组来实现的，那我们就一起来看以下 Add 方法是如何实现的

以下是 Add 方法的实现源码。

可以看到 ArrayList 在添加元素之前先检查一下集合的大小

在 ensureExplicitCapacity 方法中，首先对修改次数 modCount 加一，这里的 modCount 给 ArrayList 的迭代器使用的，在并发操作被修改时，提供快速失败行为（保证 modCount 在迭代期间不变，否则抛出 ConcurrentModificationException 异常，可以查看源码 865 行），接着判断 minCapacity 是否大于当前 ArrayList 内部数组长度，大于的话调用 grow 方法对内部数组 elementData 扩容，grow 方法代码如下：

上面的代码可以看出 ArrayList 的扩容。首先获得老数组的容量，然后 oldCapacity + (oldCapacity>> 1); 计算出老数组大小的 1.5 倍，判断 新容量小于参数指定容量，修改新容量，如果新容量大于大容量的话就指定容量。

6.remove 方法

ArrayList 的删除操作一共有两种一种是根据索引删除，一种是根据内容删除。

根据索引删除元素


remove 方法表示删除索引 index 处的元素，首先通过 rangeCheck 方法判断给定索引的范围，超过集合大小则抛出异常；接着通过 System.arraycopy 方法对数组进行自身拷贝。
根据元素删除

我们可以看到首先判断一下是否为空。不为空的话就开始循环查找元素，用 equals 来判断元素是否相同，如果一致就调用 fastRemove 来删除元素。然后通过 System.arraycopy 进行自身复制。

7. 修改方法


　通过调用 set(int index, E element) 方法在指定索引 index 处的元素替换为 element。并返回原数组的元素。先通过 rangCheck 来检查索引的合法性，如果不合法（负数，或者其他值）会抛出异常。

8. 获取元素

因为本身 ArrayList 就是用数组来实现的，所以获取元素就相对的来说简单一点。


首先也是调用 rangeCheck 方法来判断索引是否合法，然后在直接根据索引回去元素


根据元素查找索引


直接返回次出现的元素。否则返回 - 1

9.size() 方法


直接返回的 size 大小。

9.isEmpty 方法

直接返回 size==0 的结果，是不是非常简单。

10.clear 方法


循环把元素赋值为空，便于 GC 回收

11. 循环数组

for 循环

for 循环可能在 java 中是常用的遍历方法主要实现：


因为我们前面说过 get 方法可以通过索引来获取元素。同理。

迭代器 iterator

先看实现：


我们来看一下源码怎么实现的：


返回一个 Itr 对象，这个类是 属于 ArrayList 的内部类。

    

  1.  /**
    2. 

  2.      * An optimized version of AbstractList.Itr
    3. 

  3.      */
    4. 

  4.     private class Itr implements Iterator<E> {
    5. 

  5.         //游标， 下一个要返回的元素的索引
    6. 

  6.         int cursor; 
    7. 

  7.         // 返回后一个元素的索引; 如果没有这样的话返回-1.
    8. 

  8.         int lastRet = -1; 
    9. 

  9.         int expectedModCount = modCount;
    10. 

    11. 

  11.         Itr() {}
    12. 

  12.         //通过 cursor ！= size 判断是否还有下一个元素
    13. 

  13.         public boolean hasNext() {
    14. 

  14.             return cursor != size;
    15. 

  15.         }
    16. 

    17. 

  17.         @SuppressWarnings("unchecked")
    18. 

  18.         public E next() {
    19. 

  19.         //迭代器进行元素迭代时同时进行增加和删除操作，会抛出异常
    20. 

  20.             checkForComodification();
    21. 

  21.             int i = cursor;
    22. 

  22.             if (i >= size)
    23. 

  23.                 throw new NoSuchElementException();
    24. 

  24.             Object[] elementData = ArrayList.this.elementData;
    25. 

  25.             if (i >= elementData.length)
    26. 

  26.                 throw new ConcurrentModificationException();
    27. 

  27.                 //游标向后移动一位
    28. 

  28.             cursor = i + 1;
    29. 

  29.             //返回索引为i处的元素，并将 lastRet赋值为i
    30. 

  30.             return (E) elementData[lastRet = i];
    31. 

  31.         }
    32. 

    33. 

  33.         public void remove() {
    34. 

  34.             if (lastRet < )
    35. 

  35.                 throw new IllegalStateException();
    36. 

  36.             checkForComodification();
    37. 

    38. 

  38.             try {
    39. 

  39.             //调用ArrayList的remove方法删除元素
    40. 

  40.                 ArrayList.this.remove(lastRet);
    41. 

  41.                 //游标指向删除元素的位置，本来是lastRet+1的，这里删除一个元素，然后游标就不变了
    42. 

  42.                 cursor = lastRet;
    43. 

  43.                 //lastRet恢复默认值-1
    44. 

  44.                 lastRet = -1;
    45. 

  45.                 //expectedModCount值和modCount同步，因为进行add和remove操作，modCount会加1
    46. 

  46.                 expectedModCount = modCount;
    47. 

  47.             } catch (IndexOutOfBoundsException ex) {
    48. 

  48.                 throw new ConcurrentModificationException();
    49. 

  49.             }
    50. 

  50.         }
    51. 

    52. 

  52.         @Override
    53. 

  53.         @SuppressWarnings("unchecked")
    54. 

  54.         public void forEachRemaining(Consumer<? super E> consumer) {
    55. 

  55.             Objects.requireNonNull(consumer);
    56. 

  56.             final int size = ArrayList.this.size;
    57. 

  57.             int i = cursor;
    58. 

  58.             if (i >= size) {
    59. 

  59.                 return;
    60. 

  60.             }
    61. 

  61.             final Object[] elementData = ArrayList.this.elementData;
    62. 

  62.             if (i >= elementData.length) {
    63. 

  63.                 throw new ConcurrentModificationException();
    64. 

  64.             }
    65. 

  65.             while (i != size && modCount == expectedModCount) {
    66. 

  66.                 consumer.accept((E) elementData[i++]);
    67. 

  67.             }
    68. 

  68.             // update once at end of iteration to reduce heap write traffic
    69. 

  69.             cursor = i;
    70. 

  70.             lastRet = i - 1;
    71. 

  71.             checkForComodification();
    72. 

  72.         }
    73. 

  73.         //前面在新增元素add() 和 删除元素 remove() 时，我们可以看到 modCount++。修改set() 是没有的
    74. 

  74.         final void checkForComodification() {
    75. 

  75.             if (modCount != expectedModCount)
    76. 

  76.             //也就是说不能在迭代器进行元素迭代时进行增加和删除操作，否则抛出异常
    77. 

  77.                 throw new ConcurrentModificationException();
    78. 

  78.         }
    79. 

  79.     }
    80.

从上面的代码我们得出，在遍历的时候如果删除或者新增元素都会抛异常出来，而修改不会。看下方例子。

抛出异常：



相关文章