栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

JDK源码阅读--ArrayList

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

JDK源码阅读--ArrayList

文章目录
  • 层次结构
  • 字段及构造
    • 三个构造方法
  • 源码流程分析
    • 创建
    • add添加
    • grow扩容
    • 查找get
    • 删除
  • 总结

层次结构


字段及构造
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;

//用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};


private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


//数组缓冲区,ArrayList 的元素存储在其中。 ArrayList 的容量就是这个数组缓冲区的长度.
//添加第一个元素时,任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
//的空 ArrayList 都将扩展为 DEFAULT_CAPACITY
transient Object[] elementData;

//所包含元素的个数,不是数组的大小
private int size;
三个构造方法

ArrayList();
ArrayList(int cap);
ArrayList(Collection c);

源码流程分析

从list的创建, 添加, 查找, 删除, 扩容这几个方面分析

创建

ArrayList(); 默认初始化容量10,首次add时将创建长度为10的数组
ArrayList(int cap);
ArrayList(Collection c);

add添加
  1. 每次add时,先调用ensureCapacityInternal()确保list容量可以进行add操作,如果不够,则会进行扩容
  2. 确认容量后,新加入的元素放入数组缓冲区elementData 索引为size+1的位置
grow扩容

每次调用add()方法,都会调用ensureCapacityInternal()以确保内部容量,容量不够就扩容
以无参构造创建的list举例:

  1. 首次添加元素时,计算容量calculateCapacity(),因为是无参构造,所以算出待创建数组的容量为10
  2. 当前list所需的容量 大于 list数组缓冲区实际大小时,触发扩容grow()
if (minCapacity - elementData.length > 0)
   grow(minCapacity);


private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 10 >> 1  =>5
    // 5 >> 1  =>2
    // >>1,右移位1,可看成0.5倍扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容后与缓冲区最小容量比较
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 扩容后容量是否大于容量上限
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // hugeCapacity() 返回 Integer.MAX_VALUE 或 MAX_ARRAY_SIZE
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 复制并生成指定长度的新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

查找get

在ArrayList中,get/set方法在访问底层数组之前,都会进行访问检查rangeCheck(index),来避免索引越界;
因为底层使用数组这种数据结构,所以get时直接通过数组下标获取,如下:

E elementData(int index) {
    return (E) elementData[index];
}
删除

提供多个API,通过对象删除,通过索引删除
通过索引删除:
情况1:如果删除元素是数组的最后一位,则将最后一位直接置为null;elementData[–size] = null
情况2:如果不是,则根据参数索引,计算出需要移动的元素个数numMoved,调用arrayCopy进行数组赋值

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

通过对象删除:
底层对数组进行for循环遍历,只会删除匹配到的第一个元素(索引最低位,第一次出现),删除过程与上述情况2相同.

总结
  1. ArrayList底层是对象数组(elementData)
  2. size是ArrayList中元素个数,不是底层数组对象的长度
  3. 扩容时机:在add操作时,ArrayList会进行内部容量的确认,如果最小所需容量大于数组缓冲区的长度,则进行扩容
  4. 扩容大小:old + old >>1,即0.5倍扩容
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981310.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号