登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›4.Java SDK源码分析系列笔记-ArrayList

4.Java SDK源码分析系列笔记-ArrayList

韩素欣 2025-6-29 09:20:09
目录

  • 1. 是什么
  • 2. 如何使用
  • 3. 原理分析

    • 3.1. uml
    • 3.2. 构造方法
    • 3.3. add方法

      • 3.3.1. 确保容量足够容纳新的元素
      • 3.3.2. 把元素放入数组最后一个位置

    • 3.4. remove方法【按下标删除元素】

      • 3.4.1. 把数组index位置之后的数据往前挪
      • 3.4.2. 更新size【数组不缩容】

    • 3.5. remove方法【按元素内容删除】

      • 3.5.1. 首先找到要删除的元素的下标
      • 3.5.2. 把数组index位置之后的数据往前挪
      • 3.5.3. 更新size【数组不缩容】


  • 4. ConcurrentModificationException

    • 4.1. 原因分析
    • 4.2. 解决


1. 是什么

底层由数组实现的，可扩容的顺序表
有序、可以重复
2. 如何使用
  1. public class ArrayListTest
  2. {
  3.     public static void main(String[] args)
  4.     {
  5.         ArrayList<String> list = new ArrayList<>();
  6.         list.add("1");
  7.         list.add("2");
  9.         System.out.println(list);
  10.         
  11.         list.remove(0);
  12.         list.remove("2");
  16.     }
  17. }
复制代码
3. 原理分析

3.1. uml

1.png

可以看出ArrayList是个List、可克隆、可序列化、可以使用下标访问
3.2. 构造方法

使用object数组，并且初始化长度为0
  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  3. {
  4.     //如果使用默认的无参构造初始容量为0，第一次扩容时容量为10
  5.     private static final int DEFAULT_CAPACITY = 10;
  7.     //没有元素时使用空数组，两者区别是啥？
  8.     private static final Object[] EMPTY_ELEMENTDATA = {};
  9.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  11.     //List底层使用Object数组实现
  12.     transient Object[] elementData;
  14.     //Object数组中实际使用的大小
  15.     private int size;
  17.     public ArrayList() {
  18.         //默认空数组
  19.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  20.     }
  21. }
复制代码
3.3. add方法


  • 不扩容O（1），扩容O（N）
  1. public boolean add(E e) {
  2.         //确保容量足够
  3.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  4.     //在默认赋值
  5.     elementData[size++] = e;
  6.     return true;
  7. }
复制代码
3.3.1. 确保容量足够容纳新的元素
  1. private void ensureCapacityInternal(int minCapacity) {
  2.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  3. }
  5. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  6.     //使用默认的无参构造方法创建的容量为0，那么第一次扩容为10个
  7.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  8.         return Math.max(DEFAULT_CAPACITY, minCapacity);
  9.     }
  10.     return minCapacity;
  11. }
  13. private void ensureExplicitCapacity(int minCapacity) {
  14.     modCount++;
  16.     // overflow-conscious code
  17.         //减法比较大小防止溢出
  18.     if (minCapacity - elementData.length > 0)
  19.             //需要扩容
  20.         grow(minCapacity);
  21. }
  24. private void grow(int minCapacity) {
  25.     // overflow-conscious code
  26.     int oldCapacity = elementData.length;
  27.     //新长度=原长度*1.5
  28.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  29.     //新长度<最小需要的长度，那么取最小需要的长度
  30.     if (newCapacity - minCapacity < 0)
  31.         newCapacity = minCapacity;
  32.    
  33.     //新长度比数组最大限制长度还大private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
  34.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  35.             //转而使用最小需要的长度
  36.         newCapacity = hugeCapacity(minCapacity);
  37.     // minCapacity is usually close to size, so this is a win:
  38.     //复制原数组的元素到新数组中
  39.     elementData = Arrays.copyOf(elementData, newCapacity);
  40. }
  42. private static int hugeCapacity(int minCapacity) {
  43.         //最小需要的长度也溢出了，OOM
  44.     if (minCapacity < 0) // overflow
  45.         throw new OutOfMemoryError();
  46.     //最小需要的长度比数组最大限制长度大则使用Integer.MAX_VALUE，否则使用数组最大限制长度
  47.     return (minCapacity > MAX_ARRAY_SIZE) ?
  48.         Integer.MAX_VALUE :
  49.         MAX_ARRAY_SIZE;
  50. }
复制代码
3.3.2. 把元素放入数组最后一个位置
  1. //没啥好说的，赋值然后下标+1
  2. elementData[size++] = e;
复制代码
3.4. remove方法【按下标删除元素】


  • O（N）
  1. public E remove(int index) {
  2.         //防止下标越界
  3.     rangeCheck(index);
  5.     modCount++;
  6.     //保存要删除的数以便返回
  7.     E oldValue = elementData(index);
  9.         //需要移动的个数
  10.     int numMoved = size - index - 1;
  11.     if (numMoved > 0)
  12.             //后面的往前移
  13.         System.arraycopy(elementData, index+1, elementData, index,
  14.                          numMoved);
  15.      //其实数组大小没有变化。当然size属性必须更新的
  16.     elementData[--size] = null; // clear to let GC do its work
  18.     return oldValue;
  19. }
复制代码
3.4.1. 把数组index位置之后的数据往前挪
  1. //计算index后面需要移动的个数
  2. int numMoved = size - index - 1;
  3. if (numMoved > 0)
  4.         //后面的往前移
  5.     System.arraycopy(elementData, index+1, elementData, index,
  6.                      numMoved);
复制代码
3.4.2. 更新size【数组不缩容】
  1. //其实数组大小没有变化。当然size属性必须更新的
  2. elementData[--size] = null; // clear to let GC do its work
复制代码
3.5. remove方法【按元素内容删除】


  • O（N）
  1. public boolean remove(Object o) {
  2.     //为null
  3.     if (o == null) {
  4.             //找到下标
  5.         for (int index = 0; index < size; index++)
  6.             //==null判断
  7.             if (elementData[index] == null) {
  8.                     //删除该下标的元素
  9.                 fastRemove(index);
  10.                 return true;
  11.             }
  12.     } else {
  13.         for (int index = 0; index < size; index++)
  14.             //equals判断
  15.             if (o.equals(elementData[index])) {
  16.                 fastRemove(index);
  17.                 return true;
  18.             }
  19.     }
  20.     return false;
  21. }
复制代码
3.5.1. 首先找到要删除的元素的下标
  1. for (int index = 0; index < size; index++)
  2. {
  3. //...
  4. }
复制代码
如上无非就时遍历查找，效率O（N），然后按照下标删除，如下

  • fastRemove
  1. private void fastRemove(int index) {
  2.     modCount++;
  3.     //计算移动元素的个数
  4.     int numMoved = size - index - 1;
  5.     if (numMoved > 0)
  6.             //复制到前面
  7.         System.arraycopy(elementData, index+1, elementData, index,
  8.                          numMoved);
  9.         //赋为null，并且size--
  10.     elementData[--size] = null; // clear to let GC do its work
  11. }
复制代码
这段代码同上面的remove方法【按下标删除元素】的逻辑
3.5.2. 把数组index位置之后的数据往前挪
  1. //计算移动元素的个数
  2. int numMoved = size - index - 1;
  3. if (numMoved > 0)
  4.         //复制到前面
  5.     System.arraycopy(elementData, index+1, elementData, index,
  6.                      numMoved);
复制代码
3.5.3. 更新size【数组不缩容】
  1. //赋为null，并且size--
  2. elementData[--size] = null; // clear to let GC do its work
复制代码
4. ConcurrentModificationException

参考：fail-fast.md
  1. public class ConcurrentModificationExceptionTest
  2. {
  3.     public static void main(String[] args)
  4.     {
  5.         List<String> stringList = new ArrayList<>();
  6.         for (int i = 0; i < 1000; i++)
  7.         {
  8.             stringList.add(String.valueOf(i));
  9.         }
  11.         for (String s : stringList)
  12.         {
  13.             stringList.remove(s);//java.util.ConcurrentModificationException
  14.         }
  15.     }
  16. }
复制代码
如上的代码运行过程中会抛出ConcurrentModificationException异常
2.png

4.1. 原因分析

遍历时（get）执行删除操作（remove）会抛出这个异常，这叫做fast-fail机制
这是modCount和expectedCount不相等导致的
4.2. 解决

使用fail-safe的JUC包下的CopyOnWriteArrayList

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
韩素欣
2025-6-29 09:20:09

0

粉丝关注

14

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫