欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JavaSE开发中使用的ArrayList源码解析

程序员文章站 2022-06-21 14:21:01
面试过程中常见问题ArrayList和LinkList有什么区别?通常答:两者数据结构不同,ArrayList是基于数组,LinkList是基于链表,ArrayList查询比较快,LinkList插入比较快。那么插入过程中LinkList真的比ArrayList快吗?那为什么coding过程无论插入还是查询都是使用ArrayList的情况多呢?你真的了解日常使用的ArrayList和LinkList的吗?......

面试过程中常见问题ArrayList和LinkList有什么区别?

通常答:两者数据结构不同,ArrayList是基于数组,LinkList是基于链表,ArrayList查询比较快,LinkList插入比较快。

那么插入过程中LinkList真的比ArrayList快吗?那为什么coding过程无论插入还是查询都是使用ArrayList的情况多呢?你真的了解日常使用的ArrayList和LinkList的吗?

public static void main(String[] args) {
        int length = 100000;
        List arrList = new ArrayList(length);
        List linkList = new LinkedList();

        long startTime=System.nanoTime();
        for (int i = 0; i < length; i++) {
            arrList.add(i);
        }

        long endTime = System.nanoTime();
        System.out.println("arrayList插入耗时:" + (endTime - startTime));


        System.out.println("=================");

        long startTime1 = System.nanoTime();
        for (int i = 0; i < length; i++) {
            linkList.add(i);
        }
        long endTime1 = System.nanoTime();

        System.out.println("linkList插入耗时:" + (endTime1 - startTime1));
    }

JavaSE开发中使用的ArrayList源码解析

结果和我们日常所熟知的并不太一样,带着这个疑问,开始这篇文章的内容。本文主要从数组开始讲解,到ArrayList相关源码实现,希望可以帮助朋友彻底掌握ArrayList。

前提

ArrayList中有几个属性

//存储arrayList的真正容器,就是数组
transient Object[] elementData;

//默认容量
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//数组真实的容量
private int size; 

1.ArrayList构造函数

先看ArrayList中的属性,为什么定义两个{}?

//无初始化容量
public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//设置初始化容量
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);
     }
}

关键点

默认构造函数

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
有参构造函数

this.elementData = EMPTY_ELEMENTDATA;
利用两个不同的属性值,就将ArrayList是通过哪种方式创建的进行了区分,这个区分为了之后的扩容。下边添加元素的时候咱在看。

那么问题又来了为什么给默认构造函数一个默认值?

数组属于引用类型,如果没有默认值,那么创建n个默认无参集合,就需要占用n个内存地址。而此时都指向了同一个地址,减少内存的占用。

2.查找

之前在博客中已经介绍过【算法&数据结构篇】——数组和链表,关于数组基础概念请移步。这里只强调几个重点概念,数组支持下标查询,而且是连续内存,存储相同类型的元素,所以每个元素占用的内存空间是相同的。也就是这里为数组支持随机访问元素提供了基础。

先说通常大家提到数组的普遍认知,支持随机访问,但是本质上这种表述不准确,数组是适合查找操作,但是查找的时间复杂度并不是O(1)。即使排好顺序的数组,使用二分查找,时间复杂度也是O(logn)。正确的描述应该是,根据下标随机访问的时间复杂度为O(1),即get(i) 数组的起始位置+i*元素占用的内存。在ArrayList中get方法就是通过下标进行的随机访问

public E get(int index) {
        //检查下标是否越界
        rangeCheck(index);
        //获取数组的第i个元素
        return elementData(index);
    }

3.插入和删除

数组是有固定容量的,所以使用ArrayList进行add,需要考虑容量大小,并实现自动扩容。ArrayList中add有两种方式,默认是尾部添加,另一种指定下标添加元素。

1) 、默认尾部添加元素

public boolean add(E e) {
        //确定ArrayList容量,不够则进行扩容
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
  }

private void ensureCapacityInternal(int minCapacity) {
        //如果elementData为默认无参构造函数创建,则初始化容量为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //
        ensureExplicitCapacity(minCapacity);
    }

 private void ensureExplicitCapacity(int minCapacity) {
        //todo 操作数,咱们将迭代器的在处理
        modCount++;

        //如果数组容量已满,则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

  private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        //默认扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后还不够,则已入参设置的容量为主
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断数组是否超过限定的最大值Integer.MAX_VALUE - 8,如果超过则扩容为Integer.MAX
        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);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

在添加元素的时候,开头讲的两个值一样,但是属性名称不同的操作,在此处有了答案,这个判断决定通过默认构造函数创建的ArrayList默认容量为10。

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }

这此处纠正一个误区,ArrayList的最小容量并不是10,利用有参构造函数创建的时候,ArrayList的最小容量可以为0.

2)、指定下标添加元素

public void add(int index, E element) {
        //下标越界检查
        rangeCheckForAdd(index);
        //同上判断扩容,记录操作树
        ensureCapacityInternal(size + 1); 
        //依次复制插入位置及后面的数组元素,到后面一格,不是移动,因此复制完后,添加的下标位置和下一个位置指向对同一个对象
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //再将元素赋值给该下标
        elementData[index] = element;
        size++;
    }

利用这种方式进行插入,时间复杂度为O(n),与移动元素个数正相关,所以如果利用add(E e)能解决问题,优先使用尾部元素添加。

3)、指定下标删除元素

public E remove(int index) {
        //检查数组元素下标是否合法
        rangeCheck(index);
        // todo 操作树,之后将迭代器再说有何用
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        //判断要删除的元素是否是最后一个位,如果 index 不是最后一个,
        //就从 index + 1 开始往后所有的元素都向前拷贝一份。
        //然后将数组的最后一个位置空,如果 index 是最后一个元素那么就直接将数组的最后一个位置空
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
       //让指针最后指向空,进行垃圾回收
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    } 

4)、删除指定元素

//当我们调用 remove(Object o) 时,会把 o 分为是否为空来分别处理。
//然后对数组做遍历,找到第一个与 o 对应的下标 index,
//然后调用 fastRemove 方法,删除下标为 index 的元素。
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;
    }

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
    } 

删除指定元素,从代码可以看出来,如果集合中有重复的值,只能默认删除一个值

从时间复杂度角度来分析,无论是哪种情况的时间的复杂度至少为O(n),利用删除指定元素删除的时候时间复杂度为O(n^2)。

4.灵魂拷问容器能否完全替代数组?

每天都在用ArrayList,与数组相比,到底有什么优势呢?

ArrayList最大的优势可以将很多数组操作细节进行封装,例如数组的插入,删除是需要搬移数据,而且还支持动态扩容。

那么数组是不是就无用武之地了呢?答案:不是的!

1)、ArrayList无法存储基本类型,例如int,long需要封装成Integer,Long类,而拆装箱则有一定性能损耗,如果特别关注性能,或希望使用基本类型,则可以选用数组。

2)、如果数组大小已知,并且对数据操作非常简单,用不到ArrayList提供的大部分方法,也可以直接使用数组。

3)、表示多维数组时,利用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<ArrayList<object>> array,但是这点依据个人的使用喜好。

对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

5.ArrayList的父类关系

JavaSE开发中使用的ArrayList源码解析

ArrayList有三个特性,实现了三个标记接口:RandomAccess, Cloneable, java.io.Serializable

1)、RandomAccess

支持随机访问(基于下标),为了能够更好地判断集合是ArrayList还是LinkedList,从而能够更好选择更优的遍历方式,提高性能

 List arrayList = new ArrayList();

        long startTime2=System.nanoTime();
        for (int i = 0; i < length; i++) {
            arrayList.add(i);
        }

        long endTime2 = System.nanoTime();
        System.out.println("arrayList插入耗时:" + (endTime2 - startTime2));

        Collections.binarySearch(arrayList,Integer.class);

  public static <T>  int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        //利用Random区分查询是哪种list,采用不同的查询方式
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

2)、Cloneable
支持拷贝:实现Cloneable接口,重写clone方法、方法内容默认调用父类的clone方法。
2.1)、浅拷贝
基础类型的变量拷贝之后是独立的,不会随着源变量变动而
String类型拷贝之后也是独立的
引用类型拷贝的是引用地址,拷贝前后的变量引用同一个堆中的对象

public Object clone() throws CloneNotSupportedException {
    Study s = (Study) super.clone();
    return s;
}

2.2)、深拷贝
变量的所有引用类型变量(除了String)都需要实现Cloneable(数组可以直接调用clone方法),clone方法中,引用类型需要各自调用clone,重新赋值

public Object clone() throws CloneNotSupportedException {
    Study s = (Study) super.clone();
    s.setScore(this.score.clone());
    return s;
}

java的传参,基本类型和引用类型传参
java在方法传递参数时,是将变量复制一份,然后传入方法体去执行。复制的是栈中的内容
所以基本类型是复制的变量名和值,值变了不影响源变量
引用类型复制的是变量名和值(引用地址),对象变了,会影响源变量(引用地址是一样的)
String:是不可变对象,重新赋值时,会在常量表新生成字符串(如果已有,直接取他的引用地址),将新字符串的引用地址赋值给栈中的新变量,因此源变量不会受影响

3)、Serializable
序列化:将对象状态转换为可保持或传输的格式的过程。与序列化相对的是反序列化,它将流转换为对象。这两个过程结合起来,可以轻松地存储和传输数据,在Java中的这个Serializable接口其实是给jvm看的,通知jvm,我不对这个类做序列化了,你(jvm)帮我序列化就好了。如果我们没有自己声明一个serialVersionUID变量,接口会默认生成一个serialVersionUID,默认的serialVersinUID对于class的细节非常敏感,反序列化时可能会导致InvalidClassException这个异常(每次序列化都会重新计算该值)
4)、AbstractList
继承了AbstractList ,说明它是一个列表,拥有相应的增,删,查,改等功能。
5)、List
为什么继承了 AbstractList 还需要 实现List 接口?

JavaSE开发中使用的ArrayList源码解析

6.插入LinkList不一定比ArrayList快

ArrayList不适合插入的原因是因为在插入过程中涉及到数组的扩容拷贝,如果预先设定后ArrayList的容量,采用尾部添加时间复杂仅为O(1)。

那么不预先设定ArrayList为容量,那么LinkList插入一定比ArrayList快吗?

 long startTime1 = System.nanoTime();
        for (int i = 0; i < length; i++) {
            linkList.add(i);
        }
        long endTime1 = System.nanoTime();

        System.out.println("linkList插入耗时:" + (endTime1 - startTime1));

        System.out.println("=================");
        List arrayList = new ArrayList();

        long startTime2=System.nanoTime();
        for (int i = 0; i < length; i++) {
            arrayList.add(i);
        }

        long endTime2 = System.nanoTime();
        System.out.println("arrayList插入耗时:" + (endTime2 - startTime2));

JavaSE开发中使用的ArrayList源码解析

LinkList在插入过程中需要创建新的节点,而ArrayList在扩容的时候直接创建好了数组,两者在插入过程中到底谁更快?还需要根据创建的数据量来判断。所以在coding过程无论插入还是查询都是使用ArrayList的情况多。

总结

ArrayList以数组作为底层数据结构,针对数组的插入和删除进行二次封装,隐藏了直接数组涉及到的数据搬移,扩容等复杂内容。ArrayList的使用给业务开发带来了极大的便利性,但是如果对性能要求极高,而且涉及到基本类型的操作,推荐优先使用数组。同时纠正误区在做插入操作的时候LinkList不一定比ArrayList快,这个具体需要比较是LinkList创建新节点更耗时,还是扩容更耗时。

通过看ArrayList源码,收获最大的一点是构造函数的巧妙,利用常量,让所有通过无参创建的ArrayList,指向内存中同一位置,节省了大量内存的消耗。而且为了区分扩容,利用两个不同的常量,将ArrayList的创建方式分开,也便利利用无参构造函数的初识容量的设定。

本文地址:https://blog.csdn.net/jiadajing267/article/details/108700091