首页 > 编程语言 >【JDK源码】ArrayList的代码实现

【JDK源码】ArrayList的代码实现

时间：2024-01-02 10:34:50浏览次数：47  
标签：index 迭代 JDK int ArrayList elementData 源码 数组

JDK版本: 1.8.0_271

基础介绍

ArrayList 底层数据结构就是一个数组：

  1. index 表示数组下标，从 0 开始计数，elementDatda 表示数组本身
  2. DEFAULT_CAPACITY 表示数组的初始化大小，默认是10
  3. size 表示数组的大小，int 类型，没有使用 volatile 修饰，非线程安全
  4. modCount 统计当前数组被修改的版本次数，数组结构有变动，就会+1

类注释

  1. 允许 put null 值，会自动扩容
  2. size、isEmpty、get、set、add 等方法的时间复杂度都是O(1)
  3. 不是线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList
  4. 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常

源码解析

1、初始化

三种方法：无参数直接初始化、指定大小初始化、指定初始数据初始化。

源码

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 保存数组的容器，默认是null
transient Object[] elementData;

// 无参数直接初始化
public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 指定大小初始化
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(Collection<? extends E> c) {
    Object[] a = c.toArray();
    // 如果给定的集合不为空
    if ((size = a.length) != 0) {
      // 传入的集合类型为ArrayList时，数组直接地址指向a，否则拷贝数据
      if (c.getClass() == ArrayList.class) {
        elementData = a;
      } else {
        elementData = Arrays.copyOf(a, size, Object[].class);
      }
    } else {
      // 给定的集合数据为空时，默认空数组
      elementData = EMPTY_ELEMENTDATA;
    }
}

从源码中可以得到以下几点：

  1. ArrayList 无参构造器初始化时，默认大小是空数组，数组大小 10 是在第一次 add 的时候扩容的数组值。
  2. 指定数据初始化的时候，在传入的数据为空时，依旧会初始化为空数组。当传入的集合类型为ArrayList 时，elementData 会直接使用 toArray 生成的数组。

2、新增和扩容

添加元素时进行了两步操作：

  1. 判断是否需要扩容
  2. elementData 数组赋值，这里是非线程安全的
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
  // 判断数组的大小是否还够存放新数据，不够则扩容，size是当前数组存放元素的个数
  ensureCapacityInternal(size + 1);  
  // 数组赋值，线程不安全
  elementData[size++] = e;
  return true;
}

扩容（ensureCapacityInternal）的源码

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算数组需要的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是初始化时未指定大小，则使用默认的大小 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则返回存放当前元素需要的最小容量值
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // 数组改变的标志+1
    modCount++;

    // 数组需要的最小容量大于数组的长度，数组需要扩容
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

 /**
  * Increases the capacity to ensure that it can hold at least the
  * number of elements specified by the minimum capacity argument.
  *
  * @param minCapacity the desired minimum capacity
  */
private void grow(int minCapacity) {
    // 记录旧的数组长度
    int oldCapacity = elementData.length;
    // 新的数组长度等于旧的数组长度的 1.5 倍，oldCapacity >> 1相当于除以 2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新的数组长度小于需要的最小容量时，扩容值修改为最小容量值
    if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
    // 新的数组长度超过最大值时，MAX_ARRAY_SIZE 的值为 Integer 表示的最大值-8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    // 数组的复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 内存溢出
    if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
    // 需要的最小容量超过最大值时，返回Integer 表示的最大值
    return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

Java 的源码有一些需要注意的点：

  1. 初始化未指定大小的集合，第一次扩容的大小为 10
  2. 添加元素时，不管数组有没有扩容，modCount 都会+1
  3. 数组容量的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了
  4. 新增元素时，没有对值进行严格的校验，所以 ArrayList 可以添加null值。

源码中值得我们去学习的地方：

  1. 代码书写很优雅，一个方法只做一件事，便于理解
  2. 要有边界意识，数组的下标最大不超过 Integer 最大值，最小不能小于 0

3、扩容的本质

ArrayList 中的数组扩容是通过调用 Arrays 的 copyOf 方法。先创建一个符合我们预期容量的新数组，然后把旧数组的元素拷贝过去。通过调用 System.arraycopy 方法进行拷贝，此方法是 native 修饰的方法

/**
 * @param src     被拷贝的数组
 * @param srcPos  从数组那里开始
 * @param dest    目标数组
 * @param destPos 从目标数组那个索引位置开始拷贝
 * @param length  拷贝的长度
 * 此方法是没有返回值的，通过 dest 的引用进行传值
 */
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

4、删除

在源码中关于删除的方法：

  • public boolean remove(Object o)：删除第一个匹配的元素
  • public E remove(int index)：删除指定位置上的元素，并返回该元素
  • private void fastRemove(int index)：私有方法，被remove(Object o)方法调用
  • public boolean removeAll(Collection<?> c)：从此列表中删除包含在指定集合中的所有元素。
  • public void clear()：清空集合
/**
 * 移除此列表中指定位置的元素
 */
public E remove(int index) {
    // 数组越界的检查，index 大于 size 时会抛 IndexOutOfBoundsException 异常
    rangeCheck(index);

    modCount++;
    // 当 index 小于 0 时，在这里取值的时会抛出 ArrayIndexOutOfBoundsException 异常 
    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;
}

/**
 * 如果指定元素存在，则从此集合中删除第一次出现的指定元素，如果不存在，在保持不变，返回false
 */
public boolean remove(Object o) {
    // 如果要删除的元素为 null 时
    if (o == null) {
      for (int index = 0; index < size; index++)
        // 判断元素是否为null
        if (elementData[index] == null) {
          fastRemove(index);
          return true;
        }
    } else {
      for (int index = 0; index < size; index++)
        // 使用equals判断元素是否相等
        if (o.equals(elementData[index])) {
          fastRemove(index);
          return true;
        }
    }
    return false;
}

private void fastRemove(int index) {
    // 记录数组的结构变化
    modCount++;
    // 需要移动的元素个数
    // size 从 1 开始计算，index 从 0 开始，所以需要 -1
    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
}

从源码可以看出一些注意点：

  1. 新增的时候没有对 null 做校验，删除的时候也是可以删除 null 值的
  2. 删除所有元素使用的是clear()方法
  3. 删除的时候，只做了 index 是否大于 size 的判断，index 为负值时在数组取值时抛出异常。小于 0 和大于 size 时的抛出异常不同。
  4. 元素相等的判断在不为 null 的情况下使用 equals 方法，自定义类型元素的删除要注意 equals 的具体实现。

5、单向迭代器

实现java.util.Iterator接口类，迭代器中定义的几个参数：

int cursor;// 迭代过程中，下一个元素的位置，默认从 0 开始。
int lastRet = -1; // 最后一次迭代时返回的值的索引位置；默认为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中，期望的版本号；modCount 表示数组实际的版本号。

常用的迭代器方法有三个：

  • hasNext 还有没有值可以迭代
  • next如果有值可以迭代，迭代的值是多少
  • remove删除当前迭代的值

hasNext 源码

public boolean hasNext() {
    // cursor 表示下一个元素的大小，size 表示实际存放的元素个数，两者相等时，表示没有元素可以便利了
    return cursor != size;
}

next源码

@SuppressWarnings("unchecked")
public E next() {
    // 检查版本号和预期值是否一致，如果被修改则抛异常
    checkForComodification();
    // 获取应该返回的元素位置
    int i = cursor;
    // 超过元素数量，抛出异常
    if (i >= size)
      throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
      throw new ConcurrentModificationException();
    // 下次迭代时，元素的位置
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

// 判断是否修改了 elementData 数组
final void checkForComodification() {
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
}

源码这一块里面，next 做了两件事，第一判断能不能继续迭代，第二找到需要迭代的值，并为下次迭代做准备。

这里面有个很有意思的点，在判断版本号和 i 是否超过元素个数以后，又做了一次是并发修改的判断。新建了一个本地变量，将地址指向 ArrayList 的数组 elementData。此时 elementData 如果修改地址对取值已经没什么影响了。然后判断 i 是否超过数组长度，保证代码正常运行能取值，但是多线程的情况下，取值不一定是对的。

remove源码

public void remove() {
    if (lastRet < 0)
      throw new IllegalStateException();
    // 判断数组是否被修改
    checkForComodification();

    try {
      ArrayList.this.remove(lastRet);
      cursor = lastRet;
      // -1 表示元素已经被删除，防止重复删除
      lastRet = -1;
      // 删除元素会修改modCount，需要给expectedModCount重新复制
      expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
      throw new ConcurrentModificationException();
    }
}

这里有两点需要注意的：

  • lastRet = -1的操作是为了防止重复删除
  • 删除元素成功，数组的 modCount 会改变，需要同步修改 expectedModCount 的值。

6、双向迭代器

除了对java.util.Iterator接口类的实现，ArrayList 还有一个双向迭代器的实现，这个类在继承Iterator接口实现类的基础上，实现了java.util.ListIterator接口。因此又增加了几个逆向迭代方法：

  • hasPrevious 前面还有没有值可以迭代，实现代码类似hasNext
  • nextIndex 正向迭代时，下一个迭代的位置
  • previousIndex 逆向迭代时，下一个迭代的位置
  • previous 逆向迭代时，下一个迭代的值，实现类似next
  • set(E e) 修改当前迭代位置上的元素
  • add(E e) 在当前迭代的位置上添加一个元素

双向迭代器的获取方式，一种是调用listIterator()方法直接获取，默认起始位置是 0 ；另一种是调用listIterator(int index)方法指定迭代器的起始位置

public int nextIndex() {
    return cursor;
}

public int previousIndex() {
    return cursor - 1;
}
// 修改指定迭代位置上的值
public void set(E e) {
  if (lastRet < 0)
    throw new IllegalStateException();
  checkForComodification();

  try {
    ArrayList.this.set(lastRet, e);
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}
// 在迭代的位置上新增一个值
public void add(E e) {
  checkForComodification();
  try {
    int i = cursor;
    ArrayList.this.add(i, e);
    cursor = i + 1;
    lastRet = -1;
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

7、线程安全

ArrayList 是线程不安全的，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁。

其他问题

1、为什么引入 modCount 这个变量？

引入 modCount 变量是为了在遍历集合时，判断是否有并发操作改变数据的标志，在快速失败原理上有使用。

2、为什么在添加数据时扩容10，而不是初始化的时候？

节约空间，有时候初始化之后就赋值成别的 list 了

3、elementData 为什么使用 transient 修饰？

因为elementData里面不是所有的元素都有数据，因为容量的问题，elementData里面有一些元素是空的，这种是没有必要序列化的。ArrayList的序列化和反序列化依赖writeObject和readObject方法来实现。可以避免序列化空的元素。

4、new ArrayList(0) 和 new ArrayList(1)的实现

new ArrayList() 在添加第一个元素时会初始化为 10 个空间，new ArrayList(0)在扩容的时候，执行代码newCapacity = oldCapacity + (oldCapacity >> 1)，得到的新数组容量也是 0 ，这时候就会根据实际元素的个数扩容 newCapacity = size + 1。new ArrayList(0)在添加第一个元素后的容量为 1 。

同样的道理，new ArrayList(1)在添加 2 个元素时，扩容的新容量为 1，不满足最低的容量需求，这时候按照最低的容量要求扩容。

5、ArrayList 存放整型元素，调用remove方法是按照下标移除还是按照元素移除？

当集合添加元素为数字时，添加进去的元素自动装箱成Integer类型。我们在删除元素时，如果直接传入参数，会被当作索引处理。

ArrayList list = new ArrayList(0);
list.add(1);
list.add(3);
list.remove(3);
// 输出：class java.lang.Integer
System.out.println(list.get(0).getClass());
// 抛出异常：IndexOutOfBoundsException
list.remove(3);
// 正常删除
list.remove(new Integer(3));

6、Java 的快速失败和安全失败

快速失败（fail—fast）

用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出 ConcurrentModificationException

原理： 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中会判断 modCount 和expectedmodCount是否相等。两者相等的情况下才会进行迭代。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值，然后导致两者不相等，会抛出异常，终止遍历

注意：通过源码可以看出，虽然做了很多判断，但是并不能保证线程安全。如果正好在判断以后修改了 modCount 的值，并且 elementData 的长度满足条件，那么这次迭代还是能正常运行的。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。

场景： java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

安全失败（fail—safe）yuanmaa

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 ConcurrentModificationException。

场景： java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用和修改。

7、ArrayList 的扩容为什么是 1.5 倍？

扩容参数为 (1, 2) 之间比较好。

假设扩容参数为 x，当 x >= 2 时，每次扩展的新尺寸必然刚好大于之前分配的总和

【JDK源码】ArrayList的代码实现_数组

也就是说之前的内存空间都不能进行复用。

IF x = 2 :
caps: 1 2 4 8 16 32
---
1
 12
   1234
       12345678
               123456789012345
                              12345678901234567890123456789012

IF x = 1.5 :
caps: 1 2 3 4 6 9 13 19 28
---
1
 12
   123
      1234
123456
      123456789
               1234567890123
                            1234567890123456789
1234567890123456789012345678

可以看到，k = 1.5 在几次扩展之后，可以重用之前的内存空间。

标签：index,迭代,JDK,int,ArrayList,elementData,源码,数组
From： https://blog.51cto.com/u_15812995/9063892

相关文章

  • JDK9中的String底层实现为什么用UTF-16而不用UTF-8呢？
    UTF-8是一种对空间利用效率最高的编码集，它是不定长的，使用1~4字节为每个字符编码。这种情况下，如果能用一个字节存放字符就不会使用两个字节，两个字节不够就用三个字节。这种编码集只适用于传输和存储，并不适合拿来做String的底层实现。String有随机访问的方法，比如charAt、subString等......
  • Java超高精度无线定位技术--UWB (超宽带)人员定位系统源码
    UWB室内定位技术是一种全新的、与传统通信技术有极大差异的通信新技术。它不需要使用传统通信体制中的载波，而是通过发送和接收具有纳秒或纳秒级以下的极窄脉冲来传输数据，从而具有GHz量级的带宽。UWB（超宽带）高精度定位系统是一种利用超宽带技术实现精确定位的解决方案。该系统使用高......
  • java中小微医疗机构云服务（云HIS）平台源码
    云HIS（Cloud-BasedHealthcareInformationSystem）重新定义了HIS，目标是为中小型医疗卫生机构提供优质经济的医疗卫生信息化产品及服务；是以健康档案为主线、以电子病历为核心、以云计算技术为基础的医疗卫生系统。云HIS作为基于云计算的B/S构架的HIS系统，为基层医疗机构（包括诊所、社区......
  • Linux内核bind系统调用源码分析
    一、环境说明内核版本：Linux3.10内核源码地址：https://elixir.bootlin.com/linux/v3.10/source(包含各个版本内核源码，且网页可全局搜索函数)二、应用层-bind()函数将socket套接字绑定指定的地址：/**sockfd：由socket函数返回的套接口描述符*sockaddr：一个指向特定于协议......
  • 【B/S架构】医院不良事件报告系统源码
    医院不良事件报告系统为医院内质量控制、患者安全关注、医疗安全不良事件方面的精细化的管理提供了平台，是等级医院评审的必备内容，评审要求医院直报系统要与卫生部“医疗安全(不良)事件报告系统”建立网络对接。不良事件报告系统源码包括护理相关事件、医疗相关事件、药件相关事件......
  • SaaS版Java基层健康卫生云HIS信息管理平台源码
    云his系统源码，系统采用主流成熟技术开发，B/S架构，软件结构简洁、代码规范易阅读，SaaS应用，全浏览器访问，前后端分离，多服务协同，服务可拆分，功能易扩展。多集团统一登录患者主索引建立、主数据管理，统一对外接口管理。1.系统管理及基础数据：科室、病区、人员及其岗位、权限管理，各种基础资料......
  • 安卓期末大作业Android studio-记单词app（资源链接在文末，含注册登录，含设计报告，含导出ap
    安卓期末大作业Androidstudio-记单词app（注册登录、增删改查）1、注册登录界面2.用户点击加号按钮输入单词，键盘会自动弹出并焦点在输入框，用户输入英文和中文释义，单词本上将在最上面显示这个单词，并会有下拉动画。用户可以通过上方放回箭头取消输入。2.用户可以通过单词盘边的按钮来关......
  • 安卓期末大作业-调色App（源码+导出apk+运行截图）
    安卓期末大作业-调色App（源码+导出apk+运行截图）开发软件：AndroidStudio开发语言：Java2023年上半年移动开发期末大作业，比较简单的一个安卓项目，导入即可使用，适合初学者学习使用app进入界面：调色卡app主界面：可以复制颜色代码App主要代码展示：publicclassColorDetailextendsAppCompatAc......
  • 《2023安卓期末大作业-记事本app（可以登录，含完整源码+程序设计报告+运行视频+apk导出文
    2023安卓期末大作业-记事本app（可以登录，含完整源码+程序设计报告+运行视频+apk导出文件）打包文件如下图所示:基于Android系统的简单记事本，它能够便携记录生活和工作的诸多事情,从而帮助人们有条理的进行时间管理。一个记事本，能够输入标题和内容，创建日期、最新修改日期等信息。如果没......
  • 《安卓期末大作业-记账app（含源码+导出app+运行截图） 》
    安卓期末大作业-记账app（含源码+导出app+运行截图）开发软件：AndroidStudio开发语言：Java2023年上半年移动开发期末大作业记账app，老师给了95分，可以记录各种类型的账目支出记录，收入记录，存储到数据库中，可以隐藏账目记录，可以记录和删除记录，还可以将收支记录转图表分析，也可清空所有数据。具......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99