ArrayList源码解读—Java8版本(下)

简介: ArrayList源码解读—Java8版本(下)

6.9 clear()方法

   /**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
   从列表中删除所有元素。该调用返回后,列表将为空。
     */
    public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }


这里我们做一个小demo:


package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
    public static void main(String[] args) throws Exception {
        HashMap hashMap = new HashMap();
        ArrayList arrayList = new ArrayList();
        Main main = new Main();
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        Class<? extends ArrayList> aClass = arrayList.getClass();
        Field elementData = aClass.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] objects = (Object[]) elementData.get(arrayList);
        arrayList.clear();
        System.out.println(objects.length);
        System.out.println(arrayList.size());
    }
}


显然,容量虽然扩容了,但是里面的有效元素全部清空了。


七、ArrayList与迭代器模式


迭代器模式(Iterator Pattern):提供一种方法来访问聚合对象中的各个元素,而不用暴露这个对象的内部表示。

在Java中,ArrayList的迭代器有两种:Iterator和ListIterator。


7.1 Iterator

迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。

案例

在写如何实现之前,先看一个使用迭代器Iterator小例子:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
    @org.junit.Test
    public void test() {
        List list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            String str = (String) iterator.next();
            System.out.println(str);
            iterator.remove();
        }
        System.out.println(list.size());
    }
}


运行结果

1
2
3
4
0
• 1
• 2
• 3
• 4
• 5


方法


iterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。

next(),获取序列中的下个元素。

hasNext(),检查序列中向下是否还有元素。

remove(),将迭代器最近返回的一个元素删除。这也意味着调用remove()前需要先调用next()。


实现

迭代器模式中有四个角色:


抽象聚合类Aggregate。在ArrayList的Iterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法iterator()是它自己的。

具体聚合类ConcreteAggregate。在ArrayList的Iterator迭代器实现中,指的是ArrayList。

抽象迭代器Iterator。在ArrayList的Iterator迭代器实现中,指的是Iterator接口。

具体迭代器ConcreteIterator。在ArrayList中的Iterator迭代器实现中,指的是Itr。


ArrayList代码片段

public class ArrayList<E>
{
    /**
     * 保存添加到ArrayList中的元素。
     * ArrayList的容量就是该数组的长度。
     * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
     * 被标记为transient,在对象被序列化的时候不会被序列化。
     */
    transient Object[] elementData; 
    // ArrayList的实际大小(数组包含的元素个数)。
    private int size;
    /**
     * 返回一个用来遍历ArrayList元素的Iterator迭代器
     */
    public Iterator<E> iterator() {
        return new Itr();
    }
    /**
     * AbstractList.Itr的最优化的版本
     */
    private class Itr implements Iterator<E> {
        int cursor;       // 下一个要返回的元素的索引
        int lastRet = -1; // 最近的被返回的元素的索引; 如果没有返回-1。
        int expectedModCount = modCount;
        /**
         * 判断是否有下一个元素
        */
        public boolean hasNext() {
            //如果下一个要返回的元素的索引不等于ArrayList的实际大小,则返回false
            return cursor != size;
        }
        /**
         * 返回下一个元素
         */
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        /**
         * 删除最近的一个被返回的元素
         */
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}


Iterator

import java.util.function.Consumer;
public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}


Itr.java

ArrayList的内部类


7.2 ListIterator

ListIterator是一个更加强大的Iterator的子类型。它只能用于各种List类的访问。它最大的优点是可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。


案例

在写如何实现之前,先看一个使用列表迭代器ListIterator的小例子:


import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class Test {
    @org.junit.Test
    public void test() {
        List list = new ArrayList<>();
        list.add("0");
        list.add("1");
        list.add("2");
        list.add("3");
        ListIterator iterator = list.listIterator();
        System.out.println("--------------------向下遍历--------------------");
        while (iterator.hasNext()) {
            int nextIndex = iterator.nextIndex();
            String next = (String) iterator.next();
            //int previousIndex = iterator.previousIndex();
            System.out.println("当前元素:"+next+",当前元素索引:"+nextIndex/*+",前一个元素的索引"+previousIndex*/);
        }
        System.out.println("--------------------向上遍历--------------------");
        while (iterator.hasPrevious()) {
            int previousIndex = iterator.previousIndex();
            String previous = (String) iterator.previous();
            System.out.println("当前元素:"+previous+",当前元素索引:"+previousIndex);
        }
        System.out.println("-----------测试set()和listIterator(n)----------");
        System.out.println(list);
        iterator = list.listIterator(3);
        while(iterator.hasNext()){
            iterator.next();
            iterator.set("5");
        }
        System.out.println(list);
    }
}


运行结果

-------向下遍历-------
当前元素:0,当前元素索引:0
当前元素:1,当前元素索引:1
当前元素:2,当前元素索引:2
当前元素:3,当前元素索引:3
-------向上遍历-------
当前元素:3,当前元素索引:3
当前元素:2,当前元素索引:2
当前元素:1,当前元素索引:1
当前元素:0,当前元素索引:0
-------测试set()和listIterator(n)-------
[0, 1, 2, 3]
[0, 1, 2, 5]


方法

listIterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。

listIterator(n),list.iterator()用来从容器对象中返回一个指向列表索引为n的迭代器。

next(),获取序列中的下个元素,运行后索引+1。

previous(),获取序列中的上个元素,运行后索引-1。

nextIndex,获取序列中的下个元素的索引。

previousIndex,获取序列中的下个元素的索引。

hasNext(),检查序列中向下是否还有元素。

hasPrevious(),检查序列中向上是否还有元素。

remove(),从列表中删除next()或previous()返回的最后一个元素。这也意味着调用remove()前需要先调用next()或者previous()。

add(E e): 将指定的元素插入列表,插入位置为迭代器当前位置之前。

set(E e):从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e。

实现

迭代器模式中有四个角色:


抽象聚合类Aggregate。在ArrayList的ListIterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法listIterator()是它自己的。

具体聚合类ConcreteAggregate。在ArrayList的ListIterator迭代器实现中,指的是ArrayList。

抽象迭代器Iterator。在ArrayList的ListIterator迭代器实现中,指的是ListIterator。

具体迭代器ConcreteIterator。在ArrayList中的ListIterator迭代器实现中,指的是ListItr。


ArrayList代码片段

public class ArrayList<E>
{
    /**
     * 保存添加到ArrayList中的元素。
     * ArrayList的容量就是该数组的长度。
     * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
     * 被标记为transient,在对象被序列化的时候不会被序列化。
     */
    transient Object[] elementData; 
    // ArrayList的实际大小(数组包含的元素个数)。
    private int size;
    /**
     * 返回一个一开始就指向列表索引为index的元素处的ListIterator
     *
     * @throws IndexOutOfBoundsException 
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    /**
     * 返回一个一开始就指向列表索引为0的元素处的ListIterator
     * 
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }
    /**
     * AbstractList.ListItr的最优化版本
     */
    private class ListItr extends Itr implements ListIterator<E> {
        //用来从list中返回一个指向list索引为index的元素处的迭代器
        ListItr(int index) {
            super();
            cursor = index;
        }
        //获取list中的上个元素
        public boolean hasPrevious() {
            return cursor != 0;
        }
        //获取list中的下个元素的索引
        public int nextIndex() {
            return cursor;
        }
        //获取list中的上个元素的索引
        public int previousIndex() {
            return cursor - 1;
        }
        //获取list中的上个元素
        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }
        //从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e
        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        //将指定的元素插入列表,插入位置为迭代器当前位置之前。
        public void add(E e) {
            checkForComodification();
            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
}


Iterator

import java.util.function.Consumer;
public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}


ListItr.java

ArrayList的内部类。


八、阿里面试实战


7.1 ArrayList如何删除指定元素?

这是一个很麻烦的面试题,很考验对源码的认识和理解,我们来慢慢的剖析一下。

为了大家能够更好的理解ArrayList,以及这道面试题,推荐大家看一下这篇文章:

ArrayList与迭代器模式

如果使用常规的思想:


public class TestListMain {
    public static void main(String[] args) {
        List<String> result = new ArrayList<>();
        result.add("a");
        result.add("b");
        result.add("c");
        result.add("d");
        for (String s : result) {
            if ("b".equals(s)) {
                result.remove("b");
            }
        }
    }
}


image.png

真正抛异常的地方是这个检测方法, 当modCount与expectedModCount不相等的时候直接抛出异常了。那我们要看下modCount以及expectedModCount分别是什么。这里的modCount代表ArrayList的修改次数,而expectedModCount代表的是迭代器的修改次数,在创建Itr迭代器的时候,将modCount赋值给了expectedModCount,因此在本例中一开始modCount和expectedModCount都是4(添加了四次String元素)。但是在获取到b元素之后,ArrayList进行了remove操作,因此modCount就累加为5了。因此在进行检查的时候就出现了不一致,最终导致了异常的产生。到此我们找到了抛异常的原因,循环使用迭代器进行循环,但是操作元素却是使用的ArrayList操作,因此迭代器在循环的时候发现元素被修改了所以抛出异常。



我们再来思考下,为什么要有这个检测呢?这个异常到底起到什么作用呢?我们先来开下ConcurrentModificationException的注释是怎么描述的。简单理解就是不允许一个线程在修改集合,另一个线程在集合基础之上进行迭代。一旦检测到了这种情况就会通过fast-fail机制,抛出异常,防止后面的不可知状况。


/**
 ***
 * For example, it is not generally permissible for one thread to modify a Collection
 * while another thread is iterating over it.  In general, the results of the
 * iteration are undefined under these circumstances.  Some Iterator
 * implementations (including those of all the general purpose collection implementations
 * provided by the JRE) may choose to throw this exception if this behavior is
 * detected.  Iterators that do this are known as <i>fail-fast</i> iterators,
 * as they fail quickly and cleanly, rather that risking arbitrary,
 * non-deterministic behavior at an undetermined time in the future.
 ***
**/
public class ConcurrentModificationException extends RuntimeException {
    ...
}


image.png


7.3 为啥线程不安全还使用ArrayList呢?

因为在我们正常得使用场景中,都是用来查询的,不会涉及太频繁的增删,如果涉及到频繁的增删,可以使用LinkedList,如果需要线程安全的就是可以使用Vector,CopyOrWriteArrayList


7.4 1.7和1.8版本初始化的区别

1.7的时候是初始化就创建一个容量为10的数组,1.8后是初始化先创建一个空数组,第一次add时才扩容为10


7.5 ArrayList在增删的时候是怎么做的?(为什么慢)

//尾插add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//index(索引)插入,指定位置新增的时候,在校验之后的操作很简单,就是数组的copy
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 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);
}
//删除
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;
}


7.6 ArrayList是线程安全的么?

不是,可以用Vector,Collections.synchronizedList(),原理都是給方法套个synchronized,

CopyOnWriteArrayList



7.7 ArrayList⽤来做队列合适么?

队列⼀般是FIFO(先⼊先出)的,如果⽤ArrayList做队列,就需要在数组尾部追加数据,数组头部删除数组,反过来也可以。但是⽆论如何总会有⼀个操作会涉及到数组的数据搬迁,这个是⽐较耗费性能的。

结论:ArrayList不适合做队列。


7.8 那数组适合⽤来做队列么?

数组是⾮常合适的。 ⽐如ArrayBlockingQueue内部实现就是⼀个环形队列,它是⼀个定⻓队列,内部是⽤⼀个定⻓数组来实现的。

另外著名的Disruptor开源Library也是⽤环形数组来实现的超⾼性能队列,具体原理不做解释,⽐较复杂。


7.9 ArrayList的遍历和LinkedList遍历性能⽐较如何?

ArrayList要比LinkedList快得多,ArrayList遍历最大的优势在于内存的连续性,CPU的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销。


7.10 再理解ArrayList数组扩容

image.png

7.11 Java如何获取ArrayList的容量(elementData)大小?

相信你深入解读ArrayList源码之后,一定会知道ArrayList是这样的:

image.png

package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList arrayList = new ArrayList();
        Main main = new Main();
        arrayList.add(main);
        Class<? extends ArrayList> aClass = arrayList.getClass();
        Field elementData = aClass.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] objects = (Object[]) elementData.get(arrayList);
        System.out.println(objects.length);//10
    }
}


我们通过无参构造方法创建ArrayList集合,默认容量为10。

案例二

package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList arrayList = new ArrayList(3);
        Main main = new Main();
        arrayList.add(main);
        Class<? extends ArrayList> aClass = arrayList.getClass();
        Field elementData = aClass.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] objects = (Object[]) elementData.get(arrayList);
        System.out.println(objects.length);//3
    }
}


我们通过有参构造方法创建ArrayList集合,默认容量为3。

案例三

package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList arrayList = new ArrayList();
        Main main = new Main();
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        arrayList.add(main);
        Class<? extends ArrayList> aClass = arrayList.getClass();
        Field elementData = aClass.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] objects = (Object[]) elementData.get(arrayList);
        System.out.println(objects.length);//15
    }
}


我们通过无参构造方法创建ArrayList集合,默认容量为10,当我们新增11个时候,数组扩容默认容量10的1.5倍,结果为15。


相关文章
|
2月前
|
存储 Java 索引
用Java语言实现一个自定义的ArrayList类
自定义MyArrayList类模拟Java ArrayList核心功能,支持泛型、动态扩容(1.5倍)、增删改查及越界检查,底层用Object数组实现,适合学习动态数组原理。
99 4
|
7月前
|
人工智能 安全 JavaScript
Java ArrayList:动态数组
本文探讨Java中的数组,对比C/C++、JS/PHP/Python等语言的数组特性。文章分析了Java数组的定义、创建方式及其规范,指出其优缺点。Java数组作为引用类型,在堆上分配内存,支持动态大小,避免了C/C++中裸数组的常见问题(如越界访问)。然而,Java数组也存在性能瓶颈和设计缺陷,例如运行时的安全检查影响速度,无法创建超大数组或泛型数组,且多线程场景下缺乏同步机制。作者建议在实际开发中用集合替代数组以规避这些问题。
173 1
|
3月前
|
安全 架构师 Java
Java LTS版本进化秀:从8到21的欢乐升级之旅
困惑于Java版本选择?轻松幽默地穿越Java LTS版本时光隧道,掌握从Java 8到21的关键特性。通过一家初创公司的系统升级故事,直观了解每个版本如何解决代码冗余、性能瓶颈等开发痛点,助你在技术选型中做出明智决策。
|
3月前
|
缓存 Java 开发者
Java 开发者必看!ArrayList 和 LinkedList 的性能厮杀:选错一次,代码慢成蜗牛
本文深入解析了 Java 中 ArrayList 和 LinkedList 的性能差异,揭示了它们在不同操作下的表现。通过对比随机访问、插入、删除等操作的效率,指出 ArrayList 在多数场景下更高效,而 LinkedList 仅在特定情况下表现优异。文章强调选择合适容器对程序性能的重要性,并提供了实用的选择法则。
193 3
|
3月前
|
存储 小程序 Java
热门小程序源码合集:微信抖音小程序源码支持PHP/Java/uni-app完整项目实践指南
小程序已成为企业获客与开发者创业的重要载体。本文详解PHP、Java、uni-app三大技术栈在电商、工具、服务类小程序中的源码应用,提供从开发到部署的全流程指南,并分享选型避坑与商业化落地策略,助力开发者高效构建稳定可扩展项目。
|
5月前
|
Java 索引
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
511 30
|
4月前
|
Cloud Native Java API
Java Spring框架技术栈选和最新版本及发展史详解(截至2025年8月)-优雅草卓伊凡
Java Spring框架技术栈选和最新版本及发展史详解(截至2025年8月)-优雅草卓伊凡
740 0
|
5月前
|
安全 Java API
Java 17 及以上版本核心特性在现代开发实践中的深度应用与高效实践方法 Java 开发实践
本项目以“学生成绩管理系统”为例,深入实践Java 17+核心特性与现代开发技术。采用Spring Boot 3.1、WebFlux、R2DBC等构建响应式应用,结合Record类、模式匹配、Stream优化等新特性提升代码质量。涵盖容器化部署(Docker)、自动化测试、性能优化及安全加固,全面展示Java最新技术在实际项目中的应用,助力开发者掌握现代化Java开发方法。
222 1
|
7月前
|
JavaScript Java 关系型数据库
家政系统源码,java版本
这是一款基于SpringBoot后端框架、MySQL数据库及Uniapp移动端开发的家政预约上门服务系统。
216 6
家政系统源码,java版本
|
6月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
303 3