最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

arraylist实现原理与使用_arraylist原理面试必问知识

XAMPP相关 admin 55浏览 0评论
为后面的面试做准备,今天复习一下ArrayList,这是必问的知识点 

在开始之前给大家说一下,昨天发布了《今天面试了吗》系列文章第一篇,看来大家分享喜欢此系列,会继续更新。大家可以标星(置顶)本公众号:Java布局,获取后续更新。

ArrayList使用非常广泛,无论是在数据库表中查询,还是网络信息爬取都需要使用,所以了解ArrayList的原理就十分重要了(此处中若无特地说明,ArrayList版本基于JDK 1.8)。

ArrayList的继承关系

DA0092

如何定义一个ArrayList?

ArrayList有三个构造函数:①无参;②参数为一体;③参数为集合。

举个栗子:

//默认创建一个ArrayList集合
ArrayList<String> a1 = new ArrayList<>();
//创建一个初始长度为12的ArrayList集合
ArrayList<String> a2 = new ArrayList<>(12);
//将其他类型的集合转为ArrayList
ArrayList<String> a3 = new ArrayList<>(new HashSet());
我们读ArrayList构造函数的源码之前,先看看ArrayList的属性的情况:
/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
可以看到,ArrayList是非线程安全的容器,切实实现是Object [],数据会添加到ArrayList的elementData 数组中,而且带有容量DEFAULT_CAPACITY为10。但实际上从jdk7之后,ArrayList的最小容量就是0了,而DEFAULT_CAPACITY在扩容的过程中才会用到。
接下来我们来看看定义的ArrayList的三种构造函数。

ArrayList有参构造函数-入参类型为整型

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

 

可以看到,如果校准正整数,则elementData容量初始化为initialCapacity;如果写入0,则elementData分配赋值一个空数组。可能有读者发现了ArrayList类中有两个属性定义为空数组。

为什么ArrayList会定义两个空数组?

其实注释已经发表了官方解释(下有拙译):
/**
     * Shared empty array instance used for empty instances.
     此共享空数组实例用于空实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /*
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     此共享空数组用于默认大小的空实例。我们将此与EMPTY_ELEMENTDATA区分开,以了解填充第一个元素时需要多少(空间)
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
简单说,EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA 在功能上有不同的符号,前者单纯用于赋值可变空,否则是给elementData初始化的。

ArrayList有参构造函数-入参类型为集合类

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

 

可以看到,只要是实现了Collection的集合类,都会调用toArray()将集合类中的数组赋值给elementData。而且toArray()返回的布局类型不是Object []类型时…等等,toArray()返回的副本类型为什么会不是Object []类型?举个栗子:

 

public class Test<E> extends ArrayList {
    @Override
    public Integer[] toArray() {
        return new Integer[]{0, 23};
    }

    public static void main(String[] args){
        Object[] elementData = new Test<Integer>().toArray();
        System.out.println(elementData.getClass());
        System.out.println(Object[].class);
        System.out.println(elementData.getClass() == Object[].class);
    }
}
运行结果为:
class [Ljava.lang.Integer;
class [Ljava.lang.Object;
false
好,我们接着说当toArray()返回的副本类型不是Object []类型时,会调用Arrays.copyOf()将原始副本复制到新数组中去,而且类型还定义为Object类别:
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

 

ArrayList无参构造函数

 

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
在这里,我们可以看到JDK 1.8之后的ArrayList的默认容量为0
如果ArrayList的容量为0,还可以添加数据吗?
当然可以,通过扩容机制变可以扩展ArrayList的容量:
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
在这里我们可以看到,如果elementData离散依然为
DEFAULTCAPACITY_EMPTY_ELEMENTDATA(即初始状态),则通过ensureExplicitCapacity()方法将ArrayList的容量扩充为10 (DEFAULT_CAPACITY)。
为什么无参构造函数中对ArrayList容量的初始化改变了呢?
虽然JDK 1.8中的ArrayList容量为0,但在JDK1.6的无参构造函数的ArrayList容量为10:
public ArrayList() {
  this(10);
}
个人认为,JDK 1.8中逐步初始化ArrayList的实际容量,应该是考虑如果一开始就初始化为10,那么大小为10的排列中存的全部是null,这种分散多了也会占用大量的空间。所以这也是为了节省预算浪费的空间,体现了懒加载的思想。

 

怎么使用ArrayList?

 

既然我们已经知道了怎么去定义一个ArrayList,接下来就是要使用ArrayList了,而ArrayList提供的方法中常见的有:add,addAll,set,get,remove,size,isEmpty等。
因为ArrayList的一些方法会涉及到数据位置的变换,以便更直观地感受这些变化,在这里我们来举个栗子:
疫情以来,想必很多朋友已经很想念那些美食了。咱们在这里报一下菜单吧:
ArrayList<String> list = new ArrayList<>();
list.add("双皮奶");
list.add("云吞面");
list.add("煲仔饭");
list.add("叉烧包");
list.add("艇仔粥");
list.add("糯米鸡");
也就是说,elementData多少中有这些数据:

DA00092

如果想在菜单中加入“小笼包”,让我们看看这个操作在源码中是怎样的过程:
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
首先,会先通过ensureCapacityInternal(size + 1)检查elementData数组的容量是否存在,然后再将数据放入数组中,我们来看看ArrayList是怎么进行容量检查。
sureCapacityInternal()
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
在这个方法中,确定elementData是不是空副本,如果是的话,将形参minCapacity赋值更改为10(DEFAULT_CAPACITY),然后进入ensureExplicitCapacity()方法。
guaranteeExplicitCapacity()
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
此方法中的modCount变量是从AbstractList继承下来的,用于记录对ArrayList对象操作的次数:
protected transient int modCount = 0;
可以看到当形参minCapacity的数值比当前的elementData数组的长度大,则要调用grow()方法进行扩容操作。
增长()
 
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);
    }
可以看到,扩容规则为“层叠当前的容量+(串行当前的容量/ 2) ”,即扩容后的阵列容量为之前堆叠容量的1.5倍。当然,如果超过了,在hugeCapacity()方法中会进行进行处理。
hugeCapacity()
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
如果形参minCapacity大于MAX_ARRAY_SIZE,则赋值为Integer.MAX_VALUE,实际上MAX_ARRAY_SIZE与Integer.MAX_VALUE相差8
回到我们的示例中,elementData的容量为10,而分散中的数据只有6个,所以“小笼包”的加入并不会引起扩容,此时elementData枚举的中数据如下:

DA000092

与add()类似的方法还有:
加(0,“炸鲜奶”)
此方法将枚举中的元素各自往后移动一位之后,再将“炸牛奶”放到第一个位置上:

DA0000092

addAll(1,list ...“金钱肚”,“蒸凤爪”,“鲜虾饺”)
将“金钱肚”,“蒸凤爪”,“鲜虾饺”放到“炸牛奶”之后,那么多个第二个位置后的元素都需要往后移动三位,而且明显看到了一系列的容量已经不够了,按规则分解会扩容到16。

DA00000092

如果需要在既定位置安插数据,则需要通过rangeCheckForAdd()方法判断是否存在越界。
rangeCheckForAdd()
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

set(int index,E元素)

在add()方法过程中,如果要在副本中(除附加末尾)安插一个数据,需要将安插位置之后的数据往后移动一位。但是如果需要替换一些位置的数据,则需要找到对应的位置,并替换元素即可。
public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
在组()方法执行过程中,需要进行rangeCheck()数组范围检查之后,再将原数据取出用于报道查看,并在该数组位置替换新数据,如将“炸鲜奶”替换为“普洱茶” :

DA000000092

ArrayList中的get()方法获取数据的方式也很简单,只需先进行判断的数组下标是否越界,并通过下标查找,转换类型即可。
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
其中的elementData()方法的实现如下:
E elementData(int index) {
  return (E) elementData[index];
}

 

remove(int index)和remove(Object o)

ArrayList有两种删除方式,一种是通过下标选择删除的元素,另一个是通过值对象删除元素。我们先来了解一下前者:
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;
        return oldValue;
    }
通过下标选择删除的元素的remove(int index)方法中,在删除元素之前,需要先对下标进行范围检查rangeCheck(),然后再计算出需要移动的元素个数,通过arraycopy()即数组复制的方式,将既定位置之后的元素都向前移动一位,最后再设置elementData [size-1]为空,使GC 回收启动。
接下来我们来看另外:
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;
    }
通过值对象删除元素的删除(Object o)方法中,程序将为空单独进行处理,因为null是一种状态,不属于任何类型的值。在设置了既定值对象对应的下标值之后,删除操作将会在fastRemove()方法中进行,而fastRemove()方法中的操作过程就跟remove(int index)类似,在此就不多余述了。
举个栗子,如果将“云吞面”删除了,那么菜单会变成:

DA0000000092

其他方法

上文对ArrayList的增删改查方法进行了介绍,接下来简单介绍一下ArrayList的其他方法:
  • size():用于获取集合的长度,可通过定义在ArrayList中的私有变量size得到。
  • isEmpty():用于确定ArrayList是否为空,可通过定义在ArrayList中的私有变量size得到。
  • contains(Object o):用于确定ArrayList是否包含某个元素,先通过遍历放入元素数据,再通过equals或==判断。
  • clear():将ArrayList里的数据清空,通过遍历替换数组elementData,将数组里的值都设置为null。

 

结语

本文主要对ArrayList进行原理,着重介绍了ArrayList的增加,扩容机制,获取元素,修改元素,删除时元素移动的方式。
如果本文对你的学习有帮助,请给一个赞吧,这会是我最大的动力〜

转载请注明:XAMPP中文组官网 » arraylist实现原理与使用_arraylist原理面试必问知识