Talk is cheap , show me your code!
欢迎来到付振南Java博客,让我们一起学习Java吧!

Java集合之List详解 ArrayList的扩容机制你真的了解吗?

Java集合之List详解

我们知道,Java集合中的List是可以重复的,基本上是有顺序的,List下面可以分出基于数组实现的ArrayList和基于链表实现的LinkedList,还有一个线程安全的Vector。

ArrayList

基本概念

  • ArrayList是线程不安全的,底层是一个Object空数组实现的,所以插入等操作相对于链表来说是比较慢的,但是查询是较快的,ArrayList实现了RandomAccess接口,可以支持随机快速访问。

  • ArrayList的初始容量是10,每次扩容都是1.5倍扩容。

扩容机制

1.ArrayList的默认初始化容量是10。
private static final int DEFAULT_CAPACITY = 10;
在new ArrayList的时候可以指定默认大小,也可以不指定。当不指定的时候,add第一个元素进去,会调用ensureCapacity方法将默认初始值赋值给空数组,也就是说,通过无参new ArrayList的时候不是立马有容量的,当add第一个元素的时候才会初始化容量为10。

    public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }

很快,当add到第11个元素的时候,超出了默认容量,便要调用grow方法进行扩容了。

2.grow方法进行扩容

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

从grow方法中我们可以看到,它是通过调用newCapacity这个方法来获得扩容后的新容量,然后使用Array.copyOf方法将旧的数组拷贝到扩容后的新数组里。

3.我们来看看newCapacity方法。

    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
  • 首先获取当前数组的长度赋值给旧容量oldCapacity,然后加上右移一位的结果赋值给新容量newCapacity,在这里,右移操作就是2的负次幂,向右移一位也就是2的负一次幂也就是0.5,也就等于oldCapacity /2这个操作,1+0.5也就是1.5倍扩容了。

  • 获得新容量之后这还没算扩容完成,首先比较一下扩容后的新容量和实际所需要的最小容量,如果扩容后的新容量没有实际所需要的最小容量大,那就把最小需要容量当作扩容后的新容量返回。

  • 如果扩容后的新容量比实际所需要的容量大,说明扩容已经完成一大半了,但是还得考虑一下是否超过了默认最大值,也就是得要和MAX_ARRAY_SIZE比较一下,如果没有超过这个值,那就真的扩容完了,扩容完的新容量就是这个newCapacity。

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  • 在这里,MAX_ARRAY_SIZE的默认值是Integer的最大值-8,为什么要-8呢?因为数组本身也要一些空间来存储元信息。

  • 如果很不幸,由于你的ArrayList本身就很大,扩容完之后,它的大小超过了MAX_ARRAY_SIZE值,那就得调用hugeCapacity方法去判断一下实际需要的最小容量需不需要这么大的空间了。

4.我们来看看hugeCapacity方法。

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

这个方法主要就是判断实际所需要的最小容量有没有MAX_ARRAY_SIZE这么大,如果实际所需要的最小容量也超过了MAX_ARRAY_SIZE,说明你真的需要这么多容量,MAX_ARRAY_SIZE也满足不了你,所以干脆直接把Integer.MAX_VALUE最大值给你,也就是没-8的值,如果说你最小需要容量没有MAX_ARRAY_SIZE这么大,那你扩容后的新容量就是MAX_ARRAY_SIZE,避免频繁扩容。

如何在多线程环境下使用ArrayList?

问题

我们都知道ArrayList是线程不安全的,所以最好在单线程的环境下使用,如果非得在多线程环境下使用,那肯定会导致本可避免出现的错误。
java.util.ConcurrentModificationException

导致原因

由于ArrayList是快速失败(fast-fail)机制的,所以会导致这个错误。 使用ArrayList在输出过程中toString会使用迭代器遍历List容器,遍历过程中会有其它线程对List修改,导致modCount != expectedCount引发异常。

解决方案

  1. 使用jdk1.0的vector来代替ArrayList,因为vector是线程安全的,因为它是加synchronized锁实现的,但是并不推荐这么做,因为vector效率不是很高。
  2. 使用Collections工具类的synchronizedList方法,在方法里new ArrayList。
  3. 使用juc里面的copyOnWriteArrayList来代替ArrayList,copyOnWriteArrayList是写时赋值,读写分离的操作,写的时候加锁,读的时候不加锁,这样可以保证线程安全而且效率也不低,所以这个场景适合写少读多的情况下。

LinkedList

讲完了ArrayList,我们再来讲讲LinkedList。

基本概念

linkedList也是线程不安全的,底层是链表实现的,1.6以前是循环双向链表,1.7之后取消了循环。所以linkdedList的查询速度相较于ArrayList来说是比较慢的,但是修改的速度比ArrayList快,由于linkedList没有实现RandomAccess,所以它是不支持快速随机访问的,所以在遍历linkedList的时候优先选择iterator遍历,foreach底层也是iterator实现的,但是在size比较大的时候千万不要选择普通for循环去遍历,因为每遍历一个元素都是重头去查找的,效率是非常非常低的。

如何在多线程环境下使用LinkedList?

  1. 使用Collections工具类的synchronizedList方法。
  2. 使用juc下的ConcurrentLinkedQueue,因为LinkedList本身就是实现了Deque双端队列,而Deque是实现的Queue。
    public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
    }
赞(2) 打赏
未经允许不得转载:付振南Java博客 » Java集合之List详解

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    平头牛逼

    lycstar4个月前 (05-17)回复

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏