ArrayList 底层结构和源码分析

这篇具有很好参考价值的文章主要介绍了ArrayList 底层结构和源码分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

ArrayList 基本介绍

ArrayList实现了List接口。它可以存储包括null的任何类型的对象,允许重复元素。ArrayList在内部使用一个数组来存储元素,当元素数量超过数组容量时,ArrayList会自动重新分配更大的内部数组,并且将现有元素复制到新数组中。ArrayList基本等同于Vector,但是ArrayList是线程不安全的(执行效率高),在多线程情况下不建议使用ArrayList

ArrayList 源码阅读及操作机制

首先ArrayList中用来存储元素的数组是 Object 类型的数组 elementData,ArrayList的容量就是这个数组的大小。

transient Object[] elementData;

通过 debug 下面这段代码来观察ArrayList的扩容机制。

public class TestArrayList() {
  public static void main(String[] args) {
    ArrayList list = new ArrayList();
    // ArrayList list = new ArrayList(4);
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }
        for (int i = 11; i <= 15; i++) {
            list.add(i);
        }
  }
}

构造方法

当使用无参构造器创建ArrayList对象时,会创建一个默认容量为10的空数组。

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 用于默认大小的空实例的共享空数组。将其与 EMPTY_ELEMENTDATA 区分开,
// 以便在添加第一个元素时知道需要扩容多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

使用指定大小的构造器创建ArrayList对象时,则初始 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);
  }
}

add(E e)

add(E e)方法将指定元素添加到列表末尾,该方法先调用ensureCapacityInternal()方法确保容量至少是所需的最小容量(即当前大小加一),然后再赋值。

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

由于ArrayList允许的元素类型是 Object,所以添加基本类型的数据时,会先将其转换为对应的包装类型。

ensureCapacityInternal(int minCapacity)

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

calculateCapacity()

该方法计算需要的容量,如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA(使用无参构造器时即符合该条件),则返回DEFAULT_CAPACITY(10),否则返回 minCapacity(size + 1)。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
private static final int DEFAULT_CAPACITY = 10;

ensureExplicitCapacity(int minCapacity)

modCount 记录列表被结构性修改的次数(结构性修改是指添加或删除一个或多个元素,或显式调整后备数组的大小,仅仅设置元素的值不是结构性修改)。如果需要的容量大于 elementData 的长度,则调用grow()方法进行扩容。

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

grow()

该方法增加容量以确保列表至少能够容纳最小容量参数minCapacity指定的元素数量。计算得到新容量应为旧容量的 1.5 倍。如果计算得到的新容量小于需要的最小容量,则新容量应为需要的最小容量(使用无参构造器第一次添加元素时即为这种情况,第一次扩容为 10)。如果请求的数组大小超过了虚拟机的限制,可能会导致 OutOfMemoryError。最后通过数组复制copyOf.copyOf()来进行真正的扩容。

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = copyOf.copyOf(elementData, newCapacity);
}

总结

当使用无参构造器创建ArrayList对象时,elementData 初始容量为 0,第一次添加元素时 elementData 扩容为 10,以后再需要扩容,按 1.5 倍来扩容。若使用有参构造器创建ArrayList对象,elementData 初始容量为指定大小,如果需要扩容,则扩容为 1.5 倍。

值得注意的是,由于每次调整容量都需要将所有元素复制到新数组中,所以在元素数量较多时,频繁地调整容量可能会导致性能下降。为了避免频繁地调整容量,可以使用ArrayList的指定大小的构造方法或在添加大量元素之前使用ensureCapacity()方法预先指定较大的容量,以减少容量调整的次数。

另外,当从ArrayList中删除元素时,并不会立即缩小内部数组的容量。如果希望减少内存占用,可以使用trimToSize()方法来调整ArrayList的容量,使其与元素数量匹配。这样可以释放未使用的内存空间。文章来源地址https://www.toymoban.com/news/detail-480258.html

到了这里,关于ArrayList 底层结构和源码分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 源码分析——HashMap(JDK1.8)源码+底层数据结构分析

    HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。 JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈

    2024年02月13日
    浏览(44)
  • Java实现ArrayList和底层源码讲解

    🎉🎉🎉 点进来你就是我的人了 博主主页: 🙈🙈🙈戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔 🦾🦾🦾 目录 一. 模拟实现ArrayList​编辑 1.定义顺序顺序表 2. 函数实现 (1) 打印顺序表display()函数 (2) 新增元素函数add() (默认在数组最后新增) (3) 在 pos 位置新增元

    2023年04月16日
    浏览(39)
  • Java中ArrayList的底层扩容机制和Vector的底层扩容机制,以及ArrayList和Vector的对比与选择。附源码

    在 Java 的 ArrayList 中,当数组的容量不足以存储新元素时,会触发扩容操作。ArrayList 的底层使用数组来存储元素,而扩容机制主要涉及到创建一个更大的数组,并将现有元素复制到新数组中。ArrayList 支持无参扩容和有参扩容两种机制。 无参扩容机制 : 无参扩容是指 首次的

    2024年02月11日
    浏览(39)
  • Java中TreeSet的基本介绍,细节讨论,使用注意事项,常用方法,底层源码分析

    TreeSet 是 Java 中的一个有序集合实现,它基于红黑树数据结构来存储元素, 可以保持元素的自然顺序(默认情况下升序)或者根据自定义比较器来进行排序 。下面是关于 TreeSet 的基本介绍、细节讨论、使用注意事项、常用方法以及一些底层实现细节。 基本介绍: TreeSet 是

    2024年02月11日
    浏览(42)
  • 源码分析——ArrayList源码+扩容机制分析

    ArrayList 的底层是数组队列,相当于动态数组。与 Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。 ArrayList 继承于 AbstractList ,实现了 List , RandomAccess , Cloneable , ja

    2024年02月14日
    浏览(46)
  • Java集合框架之ArrayList源码分析

    ArrayList是Java提供的线性集合,本篇笔记将从源码(java SE 17)的角度学习ArrayList: 什么是ArrayList? ArrayList底层数据结构是怎么实现的? 作为一个容器,分析增删改查的过程 ArrayList的扩容机制 由ArrayList的定义可知,ArrayList继承了AbstractList抽象类,实现了List、RandomAccess、Cloneabl

    2024年02月07日
    浏览(62)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(77)
  • LinkedList部分底层源码分析

    JDK版本为1.8.0_271,以插入和删除元素为例,LinkedList部分源码如下: 插入删除结点的过程如图所示: 只有1个元素的LinkedList 包含4个元素的LinkedList add(E e)方法 add(int index,E e)方法 remove(Object obj)方法 remove(int index)方法

    2024年04月13日
    浏览(37)
  • MyBatis底层源码分析

    🎄欢迎来到@边境矢梦°的csdn博文🎄 🎄本文主要梳理MyBatis底层源码分析 🎄 🌈我是边境矢梦°,一个正在为秋招和算法竞赛做准备的学生🌈 🎆喜欢的朋友可以关注一下 🫰🫰🫰 ,下次更新不迷路🎆 Ps: 月亮越亮说明知识点越重要 (重要性或者难度越大)🌑🌒🌓🌔🌕 

    2024年02月08日
    浏览(49)
  • ArrayList底层的实现原理

    ArrayList底层的实现原理 ArrayList底层是用动态数组实现的 ArrayList初始化容量为0,当第一次添加数据的时候才会初始化为10。 ArrayList在进行扩容的时候是原来容量的1.5倍,每次扩容都需要拷贝数组。 ArrayList在添加数据的时候 确保数组已使用长度size+1之后足够存下下一个数据 计

    2024年01月22日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包