Java集合源码剖析——基于JDK1.8中ArrayList的实现原理

简介: Java集合源码剖析——基于JDK1.8中ArrayList的实现原理

文章目录:


1.看看关于ArrayList源码开头的注释

2.ArrayList中的属性

3.ArrayList中的方法

3.1 无参构造方法

3.2 有参构造方法(参数为int

3.3 get方法

3.4 grow方法

3.5 add方法

3.6 set方法

3.7 remove方法

3.8 size方法

3.9 isEmpty方法

3.10 indexOf方法

3.11 lastIndexOf方法

3.12 clear方法

3.13 contains方法


1.看看关于ArrayList源码开头的注释


Resizable-arrayimplementation of the <tt>List</tt> interface. Implements all optional list operations, and permits all elements, including

<tt>null</tt>. In addition to implementing the <tt>List</tt> interface,this class provides methods to manipulate the size of the array that is

used internally to store the list.  (This class is roughly equivalent to <tt>Vector</tt>, except that it is unsynchronized.)


从这段注释中,我们可以得知 ArrayList 是一个动态数组,实现了 List 接口以及 list相关的所有方法,它允许所有元素的插入,包括 null。另外,ArrayList Vector 除了线程不同步之外,大致相等。

·       ArrayList集合底层采用的是Object类型的数组 Object[]

·       ArrayList是非线程安全的。

·       ArrayList集合初始化容量是10,扩容是原容量的1.5倍。建议给定一个预估计的初始化容量,减少ArrayList数组的扩容次数,这也是ArrayList集合比较重要的优化策略。

·       ArrayList集合中存储元素的特点:有序可重复,元素带有下标,从0开始,以1递增。

·       ArrayList集合的优点:检索效率比较高,向数组末尾添加元素时效率也挺高的;缺点是:随机增删元素的效率比较低。

2.ArrayList中的属性


//默认容量大小为10
private static final int DEFAULT_CAPACITY = 10;
//空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放元素的数组,从这可以发现 ArrayList 的底层实现就是一个 Object 数组
transient Object[] elementData; 
//数组中包含元素的个数
private int size;
//数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


3.ArrayList中的方法


3.1 无参构造方法

默认情况下,我们 new ArrayList<>(),实际上就是创建了一个大小为0的空数组。

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

3.2 有参构造方法(参数为int)

当我们指定了初始大小的时候,elementData数组的初始大小就变成了我们所指定的初始大小了。

当指定的 initialCapacity 参数为0时,作用就相当于无参构造;大于0时,直接创建大小为 initialCapacity 的数组;小于0则抛出非法参数异常。

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);
    }
}

3.3 get方法

因为 ArrayList 是采用数组结构来存储的,所以它的 get 方法非常简单,先是判断一下有没有越界,如果当前索引index超出了数组最大长度size,直接抛出数组下标越界异常;反之如果没用越界,就可以直接通过数组下标来获取元素了,所以 get 的时间复杂度是 O(1)

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}

3.4 grow方法

grow方法是在数组进行扩容的时候用到的,从中我们可以看见,ArrayList 每次扩容都是在原容量的基础上扩 1.5 倍(

int newCapacity = oldCapacity + (oldCapacity >> 1);

),然后调用 Arrays 类的 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 = Arrays.copyOf(elementData, newCapacity);
}

3.5 add方法

ArrayList add 方法也很好理解,在插入元素之前,它会先检查是否需要扩容,然后再把元素添加到数组中最后一个元素的后面。ensureCapacityInternal 方法中,我们可以看见,如果当 elementData 为空数组时( elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ),它会使用默认的大小去扩容。所以说,通过无参构造方法来创建 ArrayList 时,它的大小其实是为 0 的,只有在使用到的时候,才会通过 grow 方法去创建一个大小为 10 的数组。

当插入元素的时候,它会将默认容量大小10与插入之后的数组长度作比较( minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); ),取较大的那个值,然后到ensureExplicitCapacity 方法中判断是否超出数组当前长度,如果超出,则调用grow方法进行扩容。


第一个 add 方法的复杂度为 O(1),虽然有时候会涉及到扩容的操作,但是扩容的次数是非常少的,所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法,则复杂度为 O(n),因为涉及到对数组中元素的移动,这一操作是非常耗时的。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

3.6 set方法


set方法的作用是把下标为 index 的元素替换成 element,同时返回替换之前的旧值。


get方法十分类似,在替换元素之前,也是先通过 rangeCheck 方法判断一下下标

index是否越界,越界直接抛异常;不越界的情况下,先通过 elementData 方法获取到当前索引对应的数组值,然后进行替换,最后返回替换之前的旧值。

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}

3.7 remove方法

移除元素也是先进行下标越界判断,然后获取到要移除元素的值。然后将旧数组从移除元素下标往后一位的所有内容拷贝到新数组中从移除元素下标的当前位置到最后,拷贝长度为numMoved,因为每移除一个元素,数组size-1,所以最后将数组长度最后的位置设置为null。返回被移除元素的值。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    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
    return oldValue;
}

3.8 size方法

就是获取当前数组的长度(所存储的元素个数)。

 public int size() {
      return size;
 }

3.9 isEmpty方法

判断数组长度是否为0(换句话说:当前数组中是否有元素)。

  public boolean isEmpty() {
      return size == 0;
  }

3.10 indexOf方法

indexOf方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的,所以它的时间复杂度是 O(n)

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

3.11 lastIndexOf方法


lastIndexOf的原理跟 indexOf 一样,而它是返回最后一个等于给定元素的值的下标。仅仅是从后往前找起罢了。

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

3.12 clear方法


清空当前数组中的所有内容(设置为null),同时将数组长度size修改为0

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

3.13 contains方法

判断数组中是否包含某个元素。就是调用 indexOf 方法查找这个元素在数组中第一次出现的下标,只有下标大于等于0才表示存在,最终返回的是布尔值。

 public boolean contains(Object o) {
      return indexOf(o) >= 0;
  }
相关文章
|
12天前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
32 5
|
25天前
|
存储 缓存 安全
Java 集合框架优化:从基础到高级应用
《Java集合框架优化:从基础到高级应用》深入解析Java集合框架的核心原理与优化技巧,涵盖列表、集合、映射等常用数据结构,结合实际案例,指导开发者高效使用和优化Java集合。
35 4
|
1月前
|
Java
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式。本文介绍了 Streams 的基本概念和使用方法,包括创建 Streams、中间操作和终端操作,并通过多个案例详细解析了过滤、映射、归并、排序、分组和并行处理等操作,帮助读者更好地理解和掌握这一重要特性。
33 2
|
1月前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
7月前
|
存储 Java Windows
Java21 JDK下载安装及Windows环境变量配置
JDK是Java的开发工具包,要进行Java学习或开发之前,需先下载安装,下载地址如下:提示:这网址里面有三个扩展名的文件,分别是“.zip”、“.exe”和“.msi”,鄙人选择的是.exe的文件,下方的安装和环境的配置也是安装该文件的安装程序进行的。
902 2
Java JDK的安装
首先我们先去下载jdk。
|
4月前
|
Java 关系型数据库 MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【8月更文挑战第19天】在Linux上搭建Java Web应用环境,需安装JDK 1.8、Tomcat及MariaDB。本指南详述了使用apt-get安装OpenJDK 1.8的方法,并验证其版本。接着下载与解压Tomcat至`/usr/local/`目录,并启动服务。最后,通过apt-get安装MariaDB,设置基本安全配置。完成这些步骤后,即可验证各组件的状态,为部署Java Web应用打下基础。
65 1
|
3月前
|
关系型数据库 Java MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【9月更文挑战第6天】在Linux环境下安装JDK 1.8、Tomcat和MariaDB是搭建Java Web应用的关键步骤。本文详细介绍了使用apt-get安装OpenJDK 1.8、下载并配置Tomcat,以及安装和安全设置MariaDB(MySQL的开源分支)的方法。通过这些步骤,您可以快速构建一个稳定、高效的开发和部署环境,并验证各组件是否正确安装和运行。这为您的Java Web应用提供了一个坚实的基础。
57 0
|
4月前
|
IDE Java 测试技术
Java零基础(4) - JDK、IntelliJ IDEA的安装和环境变量配置
【8月更文挑战第4天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
145 0
Java零基础(4) - JDK、IntelliJ IDEA的安装和环境变量配置
WXM
|
5月前
|
Oracle Java 关系型数据库
Java JDK下载安装及环境配置超详细图文教程
Java JDK下载安装及环境配置超详细图文教程
WXM
938 3