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。


相关文章
|
1天前
|
数据采集 前端开发 Java
Java医院绩效考核系统源码maven+Visual Studio Code一体化人力资源saas平台系统源码
医院绩效解决方案包括医院绩效管理(BSC)、综合奖金核算(RBRVS),涵盖从绩效方案的咨询与定制、数据采集、绩效考核及反馈、绩效奖金核算到科到组、分配到员工个人全流程绩效管理;将医院、科室、医护人员利益绑定;全面激活人才活力;兼顾质量和效益、长期与短期利益;助力医院降本增效,持续改善、优化收入、成本结构。
4 0
|
1天前
|
移动开发 前端开发 Java
第一次用java17记录运行ruoyi-vue-plus5.X版本
第一次用java17记录运行ruoyi-vue-plus5.X版本
|
1天前
|
存储 安全 算法
Java一分钟之-Java集合框架入门:List接口与ArrayList
【5月更文挑战第10天】本文介绍了Java集合框架中的`List`接口和`ArrayList`实现类。`List`是有序集合,支持元素重复并能按索引访问。核心方法包括添加、删除、获取和设置元素。`ArrayList`基于动态数组,提供高效随机访问和自动扩容,但非线程安全。文章讨论了三个常见问题:索引越界、遍历时修改集合和并发修改,并给出避免策略。通过示例代码展示了基本操作和安全遍历删除。理解并正确使用`List`和`ArrayList`能提升程序效率和稳定性。
7 0
|
2天前
|
监控 前端开发 Java
Java基于B/S医院绩效考核管理平台系统源码 医院智慧绩效管理系统源码
医院绩效考核系统是一个关键的管理工具,旨在评估和优化医院内部各部门、科室和员工的绩效。一个有效的绩效考核系统不仅能帮助医院实现其战略目标,还能提升医疗服务质量,增强患者满意度,并促进员工的专业成长
9 0
|
2天前
|
存储 安全 Java
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
|
2天前
|
Java 云计算
Java智能区域医院云HIS系统SaaS源码
云HIS提供标准化、信息化、可共享的医疗信息管理系统,实现医患事务管理和临床诊疗管理等标准医疗管理信息系统的功能。优化就医、管理流程,提升患者满意度、基层首诊率,通过信息共享、辅助诊疗等手段,提高基层医生的服务能力构建和谐的基层医患关系。
16 2
|
2天前
|
Java
从源码出发:JAVA中对象的比较
从源码出发:JAVA中对象的比较
12 3
|
3天前
|
前端开发 Java 关系型数据库
Java医院绩效考核系统源码B/S架构+springboot三级公立医院绩效考核系统源码 医院综合绩效核算系统源码
作为医院用综合绩效核算系统,系统需要和his系统进行对接,按照设定周期,从his系统获取医院科室和医生、护士、其他人员工作量,对没有录入信息化系统的工作量,绩效考核系统设有手工录入功能(可以批量导入),对获取的数据系统按照设定的公式进行汇算,且设置审核机制,可以退回修正,系统功能强大,完全模拟医院实际绩效核算过程,且每步核算都可以进行调整和参数设置,能适应医院多种绩效核算方式。
22 2
|
5天前
|
传感器 人工智能 前端开发
JAVA语言VUE2+Spring boot+MySQL开发的智慧校园系统源码(电子班牌可人脸识别)Saas 模式
智慧校园电子班牌,坐落于班级的门口,适合于各类型学校的场景应用,班级学校日常内容更新可由班级自行管理,也可由学校统一管理。让我们一起看看,电子班牌有哪些功能呢?
47 4
JAVA语言VUE2+Spring boot+MySQL开发的智慧校园系统源码(电子班牌可人脸识别)Saas 模式
|
5天前
|
分布式计算 Java API
Java8 Lambda实现源码解析
Java8的lambda应该大家都比较熟悉了,本文主要从源码层面探讨一下lambda的设计和实现。