ArrayList扩容机制

作者:神秘网友 发布时间:2021-11-25 14:06:34

ArrayList扩容机制

写在前面

数据结构在面试中基本都是常问的,但是一般开发中基本上都是在使用没有去关心过怎么实现的。

在数据结构中,链表是一种线性存储结构,也就是常说的线性表。

概念:线性表,是数据结构中的一种数据存储结构,数据元素之间具有“一对一”的逻辑关系。可以理解为把所有数据用一根线串起来,在存储到物理空间中

顺序表ArrayList

概念:将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表)。类似下图用一个线把他们连接起来,形成一条线性的结构。

ArrayList就是属于这样的一种。

ArrayList是基于数组实现的,数组是一种最简单的数据结构,在使用时必须要给它创建大小,在日常开发中,往往我们是不知道给数组分配多大空间的,如果数组空间分配多了,内存浪费,分配少了,装不下。而ArrayList在使用时可以添加多个元素切不需要指定大小,因为ArrayList是动态扩容的。

类的继承关系

源码分析

类的属性

/**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 *ArrayList 实际数据存储的一个数组
 *存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。
 *添加第一个元素时,任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。
 */
transient Object[] elementData;

/**
 * 共享的空数组实例,用于默认大小的空实例
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * elementData 的大小
 */
private int size;

类的构造函数

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

new ArrayList()做了什么

public class TestClient {

    public static void main(String[] args) {
        ListString list = new ArrayList();
        Integer capacity = getCapacity(list);
        System.out.println("没添加元素时的容量:" + capacity);
        System.out.println("没添加元素时的大小:" + list.size());
        list.add("添加元素");
        capacity = getCapacity(list);
        System.out.println("添加1个元素时的容量:" + capacity);
        System.out.println("添加1个元素时的大小:" + list.size());
    }

    /**
     * 通过反射获取list的容量
     *
     * @param list
     * @return
     */
    public static Integer getCapacity(ListString list) {
        Integer length = null;
        Class c = list.getClass();
        Field f;
        try {
            f = c.getDeclaredField("elementData");
            f.setAccessible(true);
            Object[] o = (Object[]) f.get(list);
            length = o.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
        return length;
    }
}

打印结果

没添加元素时的容量:0
没添加元素时的大小:0
添加1个元素时的容量:10
添加1个元素时的大小:1

因此,当new ArrayList()时,默认会有一个空的Object空数组,在没有添加有元素的时候,其初始化容量是0,只有当添加第一个元素的时候,容量才会设置成10。

基本方法

添加元素add(E e)

/**
 * 将指定的元素追加到此列表的末尾
 */
 public boolean add(E e) {
     ensureCapacityInternal(size + 1);
     //直接赋值
     elementData[size++] = e;
     return true;
}

add(int index, E element)

在指定索引位置添加元素

String[] elementData = {"1", "2", "3", "4", "5", "6", "7", "8"};
int index = 4;
//从下标为4的位置开始复制,复制的长度为8-4=4(复制"5", "6", "7", "8"),从下标为4+1=5的位置开始替换为"5", "6", "7", "8"
System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);

ArrayList 扩容机制

ensureExplicitCapacity(int minCapacity)

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

        //如果其元素数量大于其容量,则进行扩容
        if (minCapacity - elementData.length  0)
            grow(minCapacity);
    }

grow(int minCapacity)

    /**
     * 扩容
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        //原来的容量
        int oldCapacity = elementData.length;
        //新的容量  通过位运算右移一位  如,默认为10 101=5  右移过程:10的二进制为  1010   右移1位-0101 转十进制-5
        //可以理解为oldCapacity  1 == oldCapacity/2 再加上原来的长度就扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity  1);
        if (newCapacity - minCapacity  0)
            newCapacity = minCapacity;
        //如果大于ArrayList 可以容许的最大容量,则设置为最大容量
        if (newCapacity - MAX_ARRAY_SIZE  0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

想了解位运算的可以看看这篇文章

Java中的位运算

ArrayList 的内部实现,其实是用一个对象数组进行存放具体的值,然后用一种扩容的机制,进行数组的动态增长。

其扩容机制可以理解为,如果元素的个数,大于其容量,则把其容量扩展为原来容量的1.5倍。

拓展延伸

  • ArrayList的大小是如何自动增加的
  • 什么情况下你会使用ArrayList
  • 在索引中ArrayList的增加或者删除某个对象的运行过程效率很低吗解释一下为什么
  • ArrayList如何顺序删除节点
  • ArrayList的遍历方法

本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

ArrayList扩容机制 相关文章

  1. ArrayList 扩容机制源码分析

    本篇通过阅读JDK1.8源码,了解ArrayList是如何进行自动扩容的。 初始化 无参构造方法创建ArrayList() ArrayList arrayList = new ArrayList(); 源码: private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() { this.ele

  2. 源码系列ArrayList动态扩容机制

    源码系列ArrayList动态扩容机制 ArrayList继承了AbstractList类,实现了List接口,并且ArrayList底层是一个动态扩容的数组。ArrayList实现了RandomAccess接口,此接口是一个随机访问的标记接口(不需要遍历,直接通过下标访问数组元素的...

  3. ArrayList和LinkedList的初始化以及扩容机制的源码分析

    ArrayList和LinkedList的初始化以及扩容机制的源码分析 ArrayList源码分析 ArrayList的类图结构 初始操作 ArrayList中定义的final常量 /** Default initial capacity. 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10; private static fin

  4. Java ArrayList源码分析(含扩容机制等重点问题分析)

    写在最前面 这个项目是从20年末就立好的 flag,经过几年的学习,回过头再去看很多知识点又有新的理解。所以趁着找实习的准备,结合以前的学习储备,创建一个主要针对应届生和初学者的 Java 开源知识项目,专注 Java 后端面...

  5. java基础之:ArrayList的扩容机制(JDK1.8)?

    java基础之:ArrayList的扩容机制(JDK1.8)? java基础之:ArrayList的扩容机制(JDK1.8)? 要明确知道的是扩容机制是在往集合中添加元素时才会去触发的,所以我们从ArrayList的add方法开始跟进源码,观察源码可知,当add一个元素时,会依次调用add、en...

  6. Arraylist动态扩容详解

    Arraylist动态扩容详解 ArrayList 概述 ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长。ArrayList不是线程安全的,只能用在单线程环境下。实现了Serializable接口,因此它支持序列化,能够通过序列化传输;实现了Random...

  7. Arraylist动态扩容

    Arraylist动态扩容 JDK1.7环境 1、构造参数 ArrayList() ArrayList(int initialCapacity)用指定的大小来初始化内部的数组 ArrayList(Collection? extends E c)用一个ICollection对象来构造,并将该集合的元素添加到ArrayList 2、ArrayList() ArrayList list

  8. ArrayList是怎么扩容的呢?

    ArrayList是怎么扩容的呢? 你是否读过ArrayList的源码呢? import java.util.ArrayList;import java.util.List;public class Main { public static void main(String[] args) { ListString list = new ArrayList(); for(int i=0;i100;i++){ list.add(a); } }

  9. 集合框架之ArrayList底层长度扩容实现

    集合框架之ArrayList底层长度扩容实现 ArrayList:底层为数组,元素有序,存在索引 在jdk1.8之后,它的默认构造函数的长度为0;(之前默认10) private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; priv

  10. 数据结构:C# ArrayList扩容

    数据结构:C# ArrayList扩容 上一篇自己实现了数组的动态扩容,然后反编译了看了下ArrayList如何实现的扩容。先贴上来几行简单的代码: private static void Main(string[] args){ArrayList arrayList = new ArrayList();int length = 3;for (int i = 0; i le

  11. 【集合详解】ArrayList 源码解读之动态扩容

    【集合详解】ArrayList 源码解读之动态扩容 本文所使用的 JDK 版本:1.8.0_144 ArrayList 是一个 Java 集合,它的底层数据结构实际上就是一个数组,只不过这个数组长度不固定,动态可变,其中数组元素的类型是 Object 类型的,可以说...

  12. ArrayList源码解读(集合扩容、添加元素、删除元素)

    ArrayList源码解读(集合扩容、添加元素、删除元素) 本文会主要从集合扩容、添加元素、删除元素三个方面来进行源码解读 在开始解读之前,我们先来看一下 ArrayList添加一个元素 的流程 基本在图中已经比较全面的说明了add一...

  13. ArrayList部分源码了解(扩容、删除)--个人理解

    ArrayList部分源码解释(扩容、删除) 扩容 ArrayListInteger list=new ArrayList(); int i=0; while (i=9){ list.add(i++); } list.add(2); 1、第一行进入构造函数(无参) //有参构造函数,除了负数,initialCapacity多大就开辟多大的空间public ArrayList(int

  14. Java使用数组实现ArrayList的动态扩容的方法

    提到数组大家肯定不会陌生,但我们也知道数组有个缺点就是在创建时就确定了长度,之后就不能更改长度。所以Java官方向我们提供了ArrayList这个可变长的容器。其实ArrayList底层也是用数组进行实现的,今天我们就自己使用数...

  15. 4.22Java自定义实现ArrayList底层+数组扩容方法

    4.22Java自定义实现ArrayList底层+数组扩容方法 实现代码 往后再一个功能写完了以后就调试一下: package com.MyCollection; ? /** * 自定义实现一个ArrayList,体会底层原理 * 增加数组扩容功能 * @author Lucifer */ public class LcfArrayList03E { ? /*A

  16. Java|ArrayList源码分析|add()增加方法和grow()扩容方法

    本文结构: 1.介绍特点 2.基本方法 3.重点源码分析 1.介绍特点 ArrayList: 是List的一个具体实现子类,是List接口的一个数组实现 (里面必定维护了一个数组)。 默认初始容量10, 扩容机制1.5倍。(数组必然有初始容量和扩容机制) ...

  17. es横向扩容机制

    es横向扩容机制 es横向扩容机制 (1):primary 和replica 自动负载均衡。6个shard,primary ,3replica (2):每个node有更少的shard。IO/CPU/Memory资源给每个shard分配更多, 每个shard性能更好 (3):扩容的极限,6个shard(3 primar ,3 replica)。最多扩容

  18. 深入理解python数组的动态扩容机制以及摊销分析

    深入理解python数组的动态扩容机制以及摊销分析 [var1] (一) 动态数组的运行机制 为了方便列表对元素的增添,python采用了 分离式结构动态数组 的方法 关于动态序列内部构造方式的介绍 :https://0x9.me/D4qxd 用户持续添加列表元...

  19. c# HashSet的扩容机制需要注意的

    一:背景 1. 讲故事 自从这个纯内存项目进了大客户之后,搞得我现在对内存和CPU特别敏感,跑一点数据内存几个G的上下,特别没有安全感,总想用windbg抓几个dump看看到底是哪一块导致的,是我的代码还是同事的代码? 很多看...

  20. 七、JDK1.7中HashMap扩容机制

    七、JDK1.7中HashMap扩容机制 前面文章一、深入理解-Java集合初篇 中我们对Java的集合体系进行一个简单的分析介绍,上两篇文章二、Jdk1.7和1.8中HashMap数据结构及源码分析 、三、JDK1.7和1.8HashMap数据结构及源码分析-续 中我们分别对J...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词