java集合系列(3)ArrayList(源码分析)

简介: 这篇文章开始介绍ArrayList。ArrayList基本上是我们在平时的开发当中,使用最多的一个集合类了,它是一个其容量能够动态增长的动态数组。所以这篇文章,旨在从源码的角度进行分析和理解。为了使得文章更加有条理,还是先给出这篇文章的大致脉络:首先,ArrayList的基本介绍和源码API(只给出方法分析,重要的方法给出详细代码)。然后,介绍遍历ArrayList的几种方式接下来,叙述一下ArrayList与其他集合关键字的区别和优缺点最后,进行一个总结

一、ArrayList认识


1、概念


概念:ArrayList是一个其容量能够动态增长的动态数组。但是他又和数组不一样,下面会分析对比。它继承了AbstractList,实现了List、RandomAccess, Cloneable, java.io.Serializable。


2、继承关系


为此我们需要先知道ArrayList在整个java集合框架体系里面处于一个什么样的位置。一张图来说明:

v2-24f5a04a77e4336d41822a9373cbb8c1_1440w.jpg

从上面我们发现ArrayList的最根部就是实现了Collection接口。下面我们深入进去,看看从ArrayList的角度来分析一下继承关系:

v2-0bc40e3e6b28e27b6288509412868956_1440w.jpg

上面这张图基本上描述的很清晰了,实现了四个接口一个抽象类。它继承了AbstractList抽象类,实现了List、RandomAccess, Cloneable, Serializable接口。

  • 它继承于AbstractList,实现了List,RandomAccess[随机访问],Cloneable[可克隆], java.io.Serializable[序列化]这些接口。
  • ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能
  • ArrayList 实现了RandmoAccess接口,即提供了随机访问功能。
  • ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆
  • ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输
  • 和Vector不同,ArrayList中的操作不是线程安全的。所以,建议在单线程中才使用ArrayList,而在多线程中可以选择Vector或者CopyOnWriteArrayList。


3、特点


基本的ArrayList,常常用于随机访问元素,但是在List中间插入和移除元素时较慢。同时,ArrayList的操作不是线程安全的!一般在单线程中才使用ArrayList,而在多线程中一般使用Vector或者CopyOnWriteArrayList。对于这些我们先有一个概念。

OK,对于ArrayList的基本认识,主要就是知道是动态的数组,还有其继承关系就可以了,关于他的特点,我们知道其是数组,那么特点就和数组的一样了:随机访问元素比较好。


二、从源码分析ArrayList


既然它继承了AbstractList抽象类,实现了List、RandomAccess, Cloneable, Serializable接口。 那么他肯定就会有继承过来的特性,下面对其方法先进行一个归纳整理。


1、构造方法


  • ArrayList():构造一个初始容量为10的空列表
  • ArrayList(Collection<?extend E> c):构造一个包含指定元素的列表
  • ArrayList( int initialCapcity ):构造一个具有初始容量值得空列表


下面看一下代码实现:

//第一种、调用ArrayList(10) 默认初始化一个大小为10的object数组。
public ArrayList() {
    this(10);
}
//第二种
public ArrayList(int initialCapacity) {    
      //如果用户初始化大小小于0抛异常,否则新建一个用户初始值大小的object数组。  
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
     this.elementData = new Object[initialCapacity];
} 
//第三种:将容器数组化处理并将这个数组值赋给Object数组。
public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray();
     size = elementData.length;
     // 当c.toArray返回的不是object类型的数组时,进行下面转化。
     if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}


2、增删改查操作


对于增删改查的基本操作,在这里只给出一些比较重要的源代码,实现起来比较简单的就不给出了。


(1)增加元素

  • add(E e):添加一个元素到列表的末尾。
  • add( int index, E element ) :在指定的位置添加元素
  • addAll( Collection<? extends E> c ):添加一个集合到元素的末尾.以上返回类型是boolean
  • ensureCapcity(int minCapcity):确保列表中含有minCapcity的最小容量


下面代码看一下其实现(给出第一个增加元素的方法实现):

//第一步:
public boolean add(E e) {
    // 加入元素前检查数组的容量是否足够
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}
//第二步:
private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // 如果添加元素后大于当前数组的长度,则进行扩容
    if (minCapacity - elementData.length > 0)   grow(minCapacity);
} 
//第三步:(扩容)
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //将数组的长度增加原来数组的一半。
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)   newCapacity = minCapacity;
    //如果扩充一半后仍然不够,则 newCapacity = minCapacity;minCapacity实际元素的个数。
    if (newCapacity - MAX_ARRAY_SIZE > 0)    newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

下面代码看一下其实现(给出第二个增加元素的方法实现):

//第一步:
public void add(int index, E element) {
     rangeCheckForAdd(index);
     //检查index的值是否在0到size之间,可以为size。
     ensureCapacityInternal(size + 1);  // 看elementData的长度是否足够,不够扩容
     //将elementData从index开始后面的元素往后移一位。       
     System.arraycopy(elementData, index, elementData, index + 1, size - index);
     elementData[index] = element;
     size++;
}
//第二步:
private void rangeCheckForAdd(int index) {
     if (index > size || index < 0)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//第三步: 
private void ensureCapacityInternal(int minCapacity) {
     modCount++;
     if (minCapacity - elementData.length > 0)    grow(minCapacity);
}


(2)删除操作


  • remove(Object o):删除列表中第一个出现O的元素
  • remove( int index):删除列表中指定位置的元素
  • removeAll(Collection<?> c):删除列表中包含C的所有元素
  • removeIf(Predictcate<? super E> filter):删除列表中给定谓词的所有元素
  • removeRange( int from,int to ):删除从from到to的所有元素
  • clear():清除所有的元素。返回类型为void

看代码实现:

public E remove(int index) {
    //第一步:如果index>=size抛出异常
    rangeCheck(index);
    modCount++;
    //第二步:获取删除元素的值
    E oldValue = elementData(index);
    //第三步:将index后面所有的元素往前移一位。
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; 
    //第四步:返回要删除的原数。
    return oldValue;
}

上面的只是其中一种实现方式,再来看一种:

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


(3)更改操作


  • retainAll( Collection<?> c ):仅仅保留列表中和C相同的元素,相当于&运算
  • set(int index,E element):用element替换index位置上的元素。
  • size():返回此列表的元素数
  • sort(Comparator<? super E> c):按照指定的排序规则排序
  • subList( int from , int to ):返回从from到to之间的列表
  • toArray():将列表转化为数组
  • trimToSize( ):修改当前实例的容量是列表的当前大小。

我们看一下set操作:

//第一步:
public E set(int index, E element) {
//检查index是否小于size,如果不是抛异常
    rangeCheck(index);
    E oldValue = elementData(index);
    //覆盖ArrayList中index上的元素。
    elementData[index] = element;
    //返回被覆盖的元素。
    return oldValue;
}
//第二步:    
private void rangeCheck(int index) {
    if (index >= size)   throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

再来看看subList操作:

public List<E> subList(int arg0, int arg1) {
    subListRangeCheck(arg0, arg1, this.size);
    return new ArrayList.SubList(this, 0, arg0, arg1);
}

还有trimToSize

1)修改次数加1
2)将elementData中空余的空间(包括null值)去除,例如:数组长度为10,其中只有前三个元素有值,其他为空,那么调用该方法之后,数组的长度变为3.
public void trimToSize() {
   modCount++;
   if (size < elementData.length) {
      elementData = (size == 0) ? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
   }
}

最后就是toArray用法

// 第一种方式(最常用)
 Integer[] integer = arrayList.toArray(new Integer[0]);
 // 第二种方式(容易理解)
 Integer[] integer1 = new Integer[arrayList.size()];
 arrayList.toArray(integer1);
 // 抛出异常,java不支持向下转型
 //Integer[] integer2 = new Integer[arrayList.size()];
 //integer2 = arrayList.toArray();

(4)查操作

  • contains(Object o):如果包含元素o,则返回为true
  • get(int index):返回指定索引的元素
  • indexOf( Object o ):返回此列表中指定元素的第一次出现的索引,如果列表不包含此元素,返回-1
  • lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引,如果列表不包含此元素,返回-1
  • isEmpty():如果列表为空,返回true.
  • iterator():返回列表中元素的迭代器
  • listIterator():返回列表的列表迭代器(按适当的顺序)
  • listIterator(int index):从适当的位置返回列表的列表迭代器(按照正确的顺序)

先看一下contain()

public boolean contains(Object o) {
     return indexOf(o) >= 0;
}
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;
}

还有重要的iterator方法,不过在这里我们不去看,因为在遍历的时候会使用。


三、遍历


在这里给出三种常用的遍历方法

public class Test1 {
    public static void main(String[] args) {
        List<String> list1=new ArrayList<>();
        list1.add("张三");
        list1.add("李四");
        list1.add("王五");
        //第一种遍历方式:迭代器
        Iterator<String> it=list1.iterator();
        while(it.hasNext()) {
            System.out.println(it.next());
        }
        //第二种遍历方式,效率最高
        for(int i=0;i<list1.size();i++) {
            String aaa1=list1.get(0);
            System.out.println(aaa1);
        }
        //第三种方式:for-each
        for(String a:list1) {
            System.out.println(a);
        }   
    }
}

要问哪一种效率最高:第二种遍历的效率是最高的。想要验证的话,你只需要加一个时间差就好了。


四、ArrayList需要知道的几个问题


1、与数组的比较

v2-1f03ac766c8958fc6fa875488c732359_1440w.jpg

2、与LinkList、Vector对比区别


分析得出下面结论:


(1)ArrayList 本质上是一个可改变大小的数组.当元素加入时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问.元素顺序存储 ,随机访问很快,删除非头尾元素慢,新增元素慢而且费资源 ,较适用于无频繁增删的情况 ,比数组效率低,如果不是需要可变数组,可考虑使用数组 ,非线程安全.

(2)LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList. 适用于 :没有大规模的随机读取,有大量的增加/删除操作.随机访问很慢,增删操作很快,不耗费多余资源 ,允许null元素,非线程安全.

(3)Vector (类似于ArrayList)但其是同步的,开销就比ArrayList要大。如果你的程序本身是线程安全的,那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间,而ArrayList每次对size增长50%.


五、总结


ArrayList总体来说比较简单,不过ArrayList还有以下一些特点:


  • ArrayList自己实现了序列化和反序列化的方法,因为它自己实现了
    private void writeObject(java.io.ObjectOutputStream s)、
    private void readObject(java.io.ObjectInputStream s) 方法
  • ArrayList基于数组方式实现,无容量的限制(会扩容)
  • 添加元素时可能要扩容(所以最好预判一下),删除元素时不会减少容量(若希望减少容量,trimToSize()),删除元素时,将删除掉的位置元素置为null,下次gc就会回收这些元素所占的内存空间。
  • 线程不安全,会出现fall-fail。下一篇文章会详细讲,
  • add(int index, E element):添加元素到数组中指定位置的时候,需要将该位置及其后边所有的元素都整块向后复制一位
  • get(int index):获取指定位置上的元素时,可以通过索引直接获取(O(1))
  • remove(Object o)需要遍历数组
  • remove(int index)不需要遍历数组,只需判断index是否符合条件即可,效率比remove(Object o)高
  • contains(E)需要遍历数组
  • 使用iterator遍历可能会引发多线程异常


谢谢大家,如有问题还请批评指正。

相关文章
|
29天前
|
算法 Java 数据处理
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。HashSet基于哈希表实现,提供高效的元素操作;TreeSet则通过红黑树实现元素的自然排序,适合需要有序访问的场景。本文通过示例代码详细介绍了两者的特性和应用场景。
40 6
|
29天前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
38 3
|
29天前
|
存储 Java 数据处理
Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位
【10月更文挑战第16天】Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位。本文通过快速去重和高效查找两个案例,展示了Set如何简化数据处理流程,提升代码效率。使用HashSet可轻松实现数据去重,而contains方法则提供了快速查找的功能,彰显了Set在处理大量数据时的优势。
32 2
|
13天前
|
Java 索引 容器
Java ArrayList扩容的原理
Java 的 `ArrayList` 是基于数组实现的动态集合。初始时,`ArrayList` 底层创建一个空数组 `elementData`,并设置 `size` 为 0。当首次添加元素时,会调用 `grow` 方法将数组扩容至默认容量 10。之后每次添加元素时,如果当前数组已满,则会再次调用 `grow` 方法进行扩容。扩容规则为:首次扩容至 10,后续扩容至原数组长度的 1.5 倍或根据实际需求扩容。例如,当需要一次性添加 100 个元素时,会直接扩容至 110 而不是 15。
Java ArrayList扩容的原理
|
9天前
|
Java
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式。本文介绍了 Streams 的基本概念和使用方法,包括创建 Streams、中间操作和终端操作,并通过多个案例详细解析了过滤、映射、归并、排序、分组和并行处理等操作,帮助读者更好地理解和掌握这一重要特性。
18 2
|
9天前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
13天前
|
存储 Java
判断一个元素是否在 Java 中的 Set 集合中
【10月更文挑战第30天】使用`contains()`方法可以方便快捷地判断一个元素是否在Java中的`Set`集合中,但对于自定义对象,需要注意重写`equals()`方法以确保正确的判断结果,同时根据具体的性能需求选择合适的`Set`实现类。
|
17天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
13天前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
13天前
|
Java 开发者