浅谈:ArrayList数组1

╰半夏微凉° 2024-03-17 13:15 110阅读 0赞

ArrayList的几大特点

  • ArrayList是一个有序数组
  • ArrayList线程不安全
  • ArrayList可以存放空值

当前基于jdk 1.8源码分析

继承以及实现关系

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

1.继承抽象的AbstractList类

2.实现

  • 实现List基类,具有数组特性
  • 实现RandomAccess类,以此支持快速查询
  • 实现Cloneable类，支持克隆 Object.writeObject 注意:虽然cloneable是个标记接口无任何实现,若未实例上调用Object.clone() 方法，则会抛出CloneNotSupportedException(克隆不被支持)的异常。
  • 实现序列化java.io.Serializable

前提源码分析

  • 创建ArrayList数组默认长度

    • private static final int DEFAULT_CAPACITY = 10;

  • 空元素

    • private static final Object[] EMPTY_ELEMENTDATA = {};

  • 默认空元素，未添加任何元素时时判断数组信息

    • private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  • 实参(待处理的参数)

    • transient Object[] elementData;

  • 当前数组已经添加元素个数

    • private int size;

  • 当前数组已经被改变的次数,注意是当前数组结构发生变化 例如新增,删除都会增加,查询或者修改不会变化

    • protected transient int modCount = 0;

新增操作源码分析

  1. /**
  2.      * Appends the specified element to the end of this list.
  3.      *
  4.      * @param e element to be appended to this list
  5.      * @return <tt>true</tt> (as specified by {@link Collection#add})
  6.      */
  7.     public boolean add(E e) {
  8.         ensureCapacityInternal(size + 1);  //462 Increments modCount!!  462
  9.         elementData[size++] = e;           //463
  10.         return true;
  11.     }
  13. private void ensureCapacityInternal(int minCapacity) {
  14.         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//231
  15.     }
  17. private static int calculateCapacity(Object[] elementData, int minCapacity) {  //223
  18.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                    //224
  19.             return Math.max(DEFAULT_CAPACITY, minCapacity);                        //225
  20.         }                                                                          //226
  21.         return minCapacity;                                                        //227
  22.     }
  24. private void ensureExplicitCapacity(int minCapacity) {     //234
  25.         modCount++;                                            //235
  27.         // overflow-conscious code
  28.         if (minCapacity - elementData.length > 0)              //238
  29.             grow(minCapacity);                                 //239
  30.     }
  32. private void grow(int minCapacity) {                            //256
  33.         // overflow-conscious code                                  //258
  34.         int oldCapacity = elementData.length;                       //259
  35.         int newCapacity = oldCapacity + (oldCapacity >> 1);         //260
  36.         if (newCapacity - minCapacity < 0)                          //261
  37.             newCapacity = minCapacity;                              //262
  38.         if (newCapacity - MAX_ARRAY_SIZE > 0)                       //263
  39.             newCapacity = hugeCapacity(minCapacity);                //264
  40.         // minCapacity is usually close to size, so this is a win:  //265
  41.         elementData = Arrays.copyOf(elementData, newCapacity);      //266
  42.     }
  44. public static <T> T[] copyOf(T[] original, int newLength) {        //3180
  45.         return (T[]) copyOf(original, newLength, original.getClass()); //3181
  46.     }                                                                  //3182
  50.     public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {                                                                        //3208                       
  51.         @SuppressWarnings("unchecked")                                            //3209 
  52.         T[] copy = ((Object)newType == (Object)Object[].class)                    //3210   
  53.             ? (T[]) new Object[newLength]
  54.             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  55.         System.arraycopy(original, 0, copy, 0,                                    //3213   
  56.                          Math.min(original.length, newLength));                   //3214 
  57.         return copy;
  58.     }

新增操作步骤解析

  1. 图一包括两部分操作

    1. 创建一个存储空间,准备用来存储新元素
    2. 将新元素赋值到当前新的存储位置
  2. 图二

  3. 图三

    1. 创建一个可用的存储空间大小

      1. 具体来说,若首次创建224行满足,取225行的最大值即Math.max(10,1),即将开辟一块长度为10的内存空间; 只有首次添加元素时才会走225行
      2. 其他情况取新增元素所需的最小容量值

  4. 图四

    1. 235行此时,已经确定好所需要的空间,当前list即将变化的次数做记录
    2. 238行,判断当前数组容器是否能容纳新增的数据若,不能容纳需要进行扩容处理
    3. 239具体扩容操作

  5. 图五

    1. 259行当前未新增前的数组使用长度
    2. 260行,根据arraylist扩容算法,得到的新的可用长度
    3. 261,262行若新的可用长度还无法满足需要,直接取所需要的长度
    4. 263,264若所需要的长度大于MAX_ARRAY_SIZE提示报错
    5. 266步骤将旧数组copy到新的大数组里

  6. 图六

    1. 3210可参考https://blog.csdn.net/feeltouch/article/details/79190805
    2. 3213进行数组迁移

删除操作源码分析

首先先普及一个方法,以及使用方式

  1. public static native void arraycopy(Object src,  int  srcPos,
  2.                                         Object dest, int destPos,
  3.                                         int length);
  5. int index = 1;
  6. int numMoved = 8;
  7. int[] oldElementData = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  8. log.info("迁移前数据:{}",oldElementData);
  9. System.arraycopy(oldElementData, index + 1, oldElementData, index, numMoved);
  10. log.info("迁移后数据:{}",oldElementData);
  13. ArrayList<Integer> arrayList = new ArrayList<>();
  14. for (int i = 0; i < 10; i++) {
  15.    arrayList.add(i);
  16. }
  17. System.out.println(arrayList);
  18. arrayList.remove(1);

arraycopy就是将某一个数组src,从指定的位置srcPos,按照指定的长度length”迁移”到目标数组destPos中

  1. 目标数组也可以是当前源数组,最终的迁移结果 会把原数组上索引destPos—descPost+length元素替换掉

  2. 对于arrayList的删除，一次执行一条删除操作,即偏移量是1,且arrayList是一个连续的数组,且删除操作数组长度不会增加,即只需在原数组基础进行操作

    public E remove(int index) { //495

    1.     rangeCheck(index);                                                      //496
    3.     modCount++;                                                             //498
    4.     E oldValue = elementData(index);                                        //499
    6.     int numMoved = size - index - 1;                                        //501
    7.     if (numMoved > 0)                                                       //502
    8.         System.arraycopy(elementData, index+1, elementData, index,          //503
    9.                 numMoved);                                                  //504
    10.     elementData[--size] = null; // clear to let GC do its work              //505
    12.     return oldValue;                                                        //507
    13. }
  1. int index = 1;
  2. int numMoved = 8;
  3. int[] oldElementData = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  4. log.info("迁移前数据:{}",oldElementData);
  5. System.arraycopy(oldElementData, index + 1, oldElementData, index, numMoved);
  6. log.info("迁移后数据:{}",oldElementData);

删除操作步骤解析

  1. 步骤一

    1. 源码486行,rangeCheck(index); 校验删除的元素位置有没有越界,越界抛异常

  2. 步骤二

    1. 源码498行,数组结构删除一个元素,数组结构发生变化自增++

  3. 步骤三

    1. 源码499行,即取出当前要删除的元素,最为返回值使用

  4. 步骤四

    1. 要移动的数组长度,如果删除的是最后一位的话,numModed就不需要移动

  5. 图五

    1. 如果删除的是最后一位的话,不需要移动
    2. 否则numMoved>0,执行迁移操作

  6. 图六

    1. 删除的数据,后面所有的数据都会向前平移一位，导致最后一位数据会重复出现两边

    2. int index = 1;

      1.     int numMoved = 8;
      2.     int[] oldElementData = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
      3.     log.info("迁移前数据:{}",oldElementData);
      4.     System.arraycopy(oldElementData, index + 1, oldElementData, index, numMoved);
      5.     log.info("迁移后数据:{}",oldElementData);

      167088bc569a479197f4980315c560fa.png

  7. 步骤七

    1. 最后把最后一位多余的数据，赋null值等待,GC回收

修改操作源码分析

  1. public E set(int index, E element) {            //447
  2.         rangeCheck(index);                          //448
  4.         E oldValue = elementData(index);            //450
  5.         elementData[index] = element;               //451
  6.         return oldValue;
  7.     }

说明:修改操作有点类似于 工作过程中,修改操作场景 index类似于主键id,element类似于修改元素

删除操作步骤解析

  1. 步骤一

    1. 源码448行,rangeCheck(index); 校验修改的元素位置有没有越界,越界抛异常(同删除操作)

  2. 步骤二

    1. 源码450行,即取出当前要删除的元素,最为返回值使用(同删除操作)

  3. 步骤三

    1. elementData[index] = element;将待修改的新元素 放到指定的位置

查询操作源码分析

  1. /**
  2.      * Returns the element at the specified position in this list.
  3.      *
  4.      * @param  index index of the element to return
  5.      * @return the element at the specified position in this list
  6.      * @throws IndexOutOfBoundsException {@inheritDoc}
  7.      */
  8.     public E get(int index) {              //432
  9.         rangeCheck(index);                 //433
  11.         return elementData(index);         //435
  12.     }
  15.     @SuppressWarnings("unchecked")    
  16.     E elementData(int index) {            //421
  17.         return (E) elementData[index];    //422
  18.     }

  1. 步骤一

    1. 源码433行,rangeCheck(index); 校验查询的元素位置有没有越界,越界抛异常(同删除，修改操作)

  2. 步骤二

    1. 返回索引index对应的元素

其他说明

ArrayList与Vector的区别

  • 扩容不同

    1. ArrayList扩容问题,具体扩容多少与初始容积有关,可以指定初始容积，默认初始容积为10 无扩容因子
    2. vector有扩容因子,默认初始容积为10 可以指定每次扩容的大小
  1. ArrayList的扩容说明
  2. int newCapacity = oldCapacity + (oldCapacity >> 1);
  4. arrayList的扩容说明
  5. int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  6.                                  capacityIncrement : oldCapacity);

  • 线程安全性

    • vector增加、删除操作使用synchronized修饰,方法级别是线程安全的
  1. public synchronized E remove(int index)
  3. public synchronized boolean add(E e)
  5. public synchronized E set(int index, E element)
  7. public synchronized E get(int index)

发表评论

表情：
评论列表 （有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

    相关 浅谈数组和链表

    什么是数组？ 相同数据类型的元素按一定顺序连续排列的[集合][Link 1]。内存结构是连续的，每个内存大小是相等的。 内存结构图： ![202007202131

    男娘i男娘i/ 0 赞/ 36 阅读