转载

Java集合框架分析(二)ArrayList分析

相关文章 Java集合框架分析(一)综合概述

本篇文章主要分析一下 Java 集合框架中的 List 部分，ArrayList，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请指正！

ArrayList简介

ArrayList 底层维护的是一个动态数组，每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。ArrayList 不是同步的（也就是说不是线程安全的，同 HashMap、LinkedHashMap 一样），如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步，在多线程环境下，可以使用 Collections.synchronizedList 方法声明一个线程安全的 ArrayList，例如：

List arraylist = Collections.synchronizedList(new ArrayList());
复制代码

源码分析

类结构定义

首先我们来看一下关于ArrayList的类结构，

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
复制代码

上面是是 ArrayList 类的定义，它继承了抽象类 AbstractList，但是真正继承的方法只有 equals 和 hashCode，别的方法在 ArrayList 中都有自己的重新实现；List 接口在 AbstractList 中已经实现，这里是为了表明一下，没有太大含义；RandomAccess 没有方法，表明 ArrayList 支持快速随机访问；实 现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制，如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常；类通过实现 java.io.Serializable 接口以启用其序列化功能，未实现此接口的类将无法使其任何状态序列化或反序列化

变量定义

接着我们分析一下 ArrayList 定义的变量。

//序列化ID
private static final long serialVersionUID = 8683452581122892189L;
//数组初始容量大小
private static final int DEFAULT_CAPACITY = 10;
//
private static final Object[] EMPTY_ELEMENTDATA = {};
//elementData存储ArrayList内的元素
transient Object[] elementData;
//存储在ArrayList内的元素的数量
private int size;
复制代码

构造函数

//设定初始容量大小的构造函数
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //数组初始化
    this.elementData = new Object[initialCapacity];
}
//无参数构造函数
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}
//将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]）
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
复制代码

构造函数还是比较简单的，我们来看看 ArrayList 的最常用的方法 add,

Add(E e)添加数据

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

发现 ArrayList 的 add 方法，只有简单的两行代码，粗略的看一下是在数组 elementData 的尾部添加一个元素 E，那么到底是怎么样操作的呢？我们详细查看一下源码，首先进入 ensureCapacityInternal 方法中一探究竟。看这个方法的名字就大概知道这是确保数组容量的，怎么个确保法呢？

private void ensureCapacityInternal(int minCapacity) {
    //当我们调用ArrayList的无参构造函数时调用此代码
    if (elementData == EMPTY_ELEMENTDATA) {
        //设置数组容量为10，默认的大小
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //
    ensureExplicitCapacity(minCapacity);
}
//确保容量大小,modCount自增，并判断数组大小是否足够，不够的话将增大数组
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果最小需要空间比elementData的内存空间要大，则需要扩容  
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码

到了这里还是有点模糊到底怎么数组扩容的？我们接着看 grow 的方法

//扩容并重新copy一份数组
private void grow(int minCapacity) {

        // oldCapacity为当前数组大小  
        int oldCapacity = elementData.length;
        // newCapacity为新容量的大小等于旧容量的1.5倍大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩充后的容量还是比最少需要的容量还要小的话，就设置扩充容量为最小需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断最新的容量是否已经超出最大数组范围，溢出判断
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间  
    // 并将elementData的数据复制到新的内存空间  
        elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码

我们总结一下 add 操作的过程，首先我们先要判断是否需要扩容，在扩容判断里面，我们主要进行一些判断，如果当前所需要的容量和当前数组的容量进行比较，如果不够的话则进行扩容，在扩容的同时则需要判断是否溢出了，然后将旧的数据数组进行 copy 到新的容量大小的数组中，最后再将需要添加的数据添加到数组的最后一位。

我们接着分析 add 的另一个方法，重载 add(int index, E element) 方法，

//在指定的位置上面插入一个数据
 public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //需要将指定位置及其后面数据向后移动一位，然后在位置上面插入数据
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //插入数据
        elementData[index] = element;
        //大小改变
        size++;
    }
复制代码

中心思想就是，首先判断指定位置 index 是否超出 elementData 的界限，之后调用 ensureCapacity 调整容量（若容量足够则不会拓展），调用 System.arraycopy 将 elementData 从 index 开始的 size-index 个元素复制到 index+1 至 size+1 的位置（即 index 开始的元素都向后移动一个位置），然后将 index 位置的值指向 element，同时改变数组的大小。

addAll 方法

接着我们分析一下 addAll 方法。

public boolean addAll(Collection<? extends E> c) {
       Object[] a = c.toArray();
       int numNew = a.length;
       ensureCapacityInternal(size + numNew);  // Increments modCount
       //将a的第0位开始拷贝至elementData的size位开始，拷贝长度为numNew 
       System.arraycopy(a, 0, elementData, size, numNew);
       size += numNew;
       return numNew != 0;
   }
复制代码

其实这个方法很好理解，首先将批量添加的数据转为数组，然后获取它的容量大小，判断一下，如果我们要在数组中插入这一批数据的话，是否需要扩容，经过这个扩容判断操作，我们的数组容量是足够了，然后我们开始批量导入数据，其中 System.arraycopy(a, 0, elementData, size, numNew) ;意思就是，将需要导入的批数据从 0 开始，导入到数组从 size 位置开始，导入的大小数量就是需要导入的数量。这个时候，总的数组容量就变成了原先的容量加上导入的容量了。

addAll 还有一个重载方法，我们也来看看：

public boolean addAll(int index, Collection<? extends E> c) {
        //判断插入的位置是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
复制代码

这个方法其实在 add 的方法基础上面修改而来，复制数组的时候主要进行两步复制，第一步，现将原数组在指定的位置上面向后移动需要的位数，然后第二步再将需要导进去的数据从 index 位置复制进去。

get方法

分析完了 add 方法，我们来分析分析 get 方法内容，get 方法也是比较简单的

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        return (E) elementData[index];
    }
复制代码

首先判断需要返回的位置是否越界了，其次直接返回数组对应索引里面的值。非常简单，我们再看看其他方法。

其余方法

remove(int index)

我们来看看 remove 方法

public E remove(int index) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      modCount++;
      //保存一下需要删除的数据
      E oldValue = (E) 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;
  }
复制代码

同理，因为涉及到数组的问题，所以首先需要判断一下是否出现越界的问题，然后就开始将指定删除位置后面的数据都向前移动一位，然后将最后的一位设置为 null，最后返回删除的数据。

删除一个数据，remove 也有重载方法

remove(Object o)

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
复制代码

删除一个数据，主要是遍历数组，看看数组中是否存在这个数据，如果存在的话则进行fastRemove，我们进入 fastRemove 中看看

fastRemove(int index)

//删除指定位置上面的数据
private void fastRemove(int index) {
    modCount++;
    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
}
复制代码

将指定位置 index 后面的数据全部向前移动一位，最后将最后一位回收掉。

另外我们看下全部删除数组中的数据方法 clear

clear

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

将数组中所有的数据都重置为 null，等带回收。

removeRange(int fromIndex, int toIndex)

protected void removeRange(int fromIndex, int toIndex) {

if (toIndex < fromIndex) {
        throw new IndexOutOfBoundsException("toIndex < fromIndex");
    }
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);
    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}
复制代码

执行过程是将 elementData 从 toIndex 位置开始的元素向前移动到 fromIndex，然后将 toIndex 位置之后的元素全部置空顺便修改 size。

set(int index, E element)

public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
复制代码

这个方法很简单，就是修改数组 index 里面的数据，并返回旧的数据。

indexOf(Object o)

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;
    }
复制代码

返回在数组中第一次出现的值。如果找到这个值的话就返回 index，找不到就返回-1。

trimToSize()

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}
复制代码

由于 elementData 的长度会被拓展，size 标记的是其中包含的元素的个数。所以会出现 size 很小但 elementData.length 很大的情况，将出现空间的浪费。trimToSize 将返回一个新的数组给elementData，元素内容保持不变，length 跟 size 相同，节省空间。

总结

以上便是 ArrayList 的源码内容，总的来说不是很难，接下来我们来总结一下关于 ArrayList 的方方面面。

ArrayList 底层是基于数组来实现的，可以通过下标准确的找到目标元素，因此查找的效率高；但是添加或删除元素会涉及到大量元素的位置移动，效率低。

ArrayList 提供了三种不同的构造方法，无参数的构造方法默认在底层生成一个长度为 10 的 Object 类型的数组，当集合中添加的元素个数大于 10，数组会自动进行扩容，即生成一个新的数组，并将原数组的元素放到新数组中。

ensureCapacity 方法对数组进行扩容，它会生成一个新数组，长度是原数组的 1.5 倍 +1，随着向 ArrayList 中不断添加元素，当数组长度无法满足需要时，重复该过程。

ArrayList 不是同步的（也就是说不是线程安全的，同 HashMap、LinkedHashMap 一样），如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步，在多线程环境下，可以使用 Collections.synchronizedList 方法声明一个线程安全的 ArrayList，例如：List arraylist = Collections.synchronizedList(new ArrayList());

关于作者

专注于 Android 开发多年，喜欢写 blog 记录总结学习经验，blog 同步更新于本人的公众号，欢迎大家关注，一起交流学习～

Java集合框架分析(二)ArrayList分析
原文  https://juejin.im/post/5dba52e86fb9a02067218e63
正文到此结束
所属分类： 编程技术 Java

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：650 人
  • 运行天数：4,409天
  • 最后更新：2024年11月22日03点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG