arraylist 并发_面试宝典:数据结构ArrayList

前言

这篇文章咱介绍下 ArrayList面试考点 有备无患 ?

默认大小

默认大小为10

扩容为原来的一半 扩容一次以后为15

扩容使用Arrays.copyOf(elementData, size, Object[].class);

懒加载

1.7之后都是延迟初始化

使用默认容量时采取的是“懒加载” 即等到add元素的时候才进行实际容量的分配

无参构造器，指向的是默认容量大小的Object数组，注意使用无参构造函数的时候并没有直接创建容量为10的Object数组,而是采取懒加载的策略：使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA(实际容量为0)作为标识，在真正add元素时才会开辟Object数组

当我们向数组中添加第一个元素时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会知道数组该扩充多少

内部结构

ArrayList内部结构，是一个Object[]类型的数组

构造函数

• ArrayList(int initialCapacity)

构造方法：表示接受指定容量值，初始化创建数组，

• ArrayList()

构造方法：是默认的构造方法，它创建一个空数组

• ArrayList(Collection extends E> c)

构造方法：接收一个Collection的实体，将该Collection实体转换为ArrayList对象。

failFast机制

• ArrayList只能在单线程环境下使用，在多线程环境下会出现并发安全问题

• modCount主要用于记录对ArrayList的修改次数，如果一个线程操作期间modCount发生了变化即，有多个线程同时修改当前这个ArrayList，此时会抛出“ConcurrentModificationException”异常，这又被称为“failFast机制”

• 在很多非线程安全的类中都有failFast机制：HashMap、 LinkedList等。

• 这个机制主要用于迭代器、加强for循环等相关功能，也就是一个线程在迭代一个容器 时，如果其他线程改变了容器内的元素，迭代的这个线程会抛出“ConcurrentModificationException”异常

在使用Java的集合类的时候，如果发生ConcurrentModificationException，优先考虑fail-fast有关的情况，实际上这可能并没有真的发生并发，只是Iterator使用了fail-fast的保护机制，只要他发现有某一次修改是未经过自己进行的，那么就会抛出异常

双向列表

• LinkedList底层采用双向列表实现，所以在添加新元素的时候要先构造一个Node对象(item为我们加入的值)，只需要将Node的next赋值为新的Node即可

• 相对于ArrayList而言，LinkedList可以更加高效的插入元素，因为它不会涉及到ArrayList扩容。但也因为这种数据结构，导致它不具备有随机访问的能力

如何保证线程安全

1、线程安全的方法

List list = Collections.synchronizedList(new ArrayList<>());

Collections提供了方法synchronizedList保证list是同步线程安全的

2、CopyOnWriteArrayList：写时复制

• CopyOnWrite容器是写时复制的容器，往一个容器添加元素的时候，不直接往当前的容器Object[]添加，而是先将当前容器Object[] 进行Copy,复制出一个新的容器Object[] newElements,然后往新的容器Object[] newElement里面添加元素，添加完元素之后，再将原容器的引用指向新的容器，setArray(newElements );

• 这样做的好处是可以对CopyOnWriter容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素，所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

是否允许空值

允许空值和重复元素

时间复杂度

底层基于数组实现，所以其可以保证在 O(1) 复杂度下完成随机查找操作

static修饰的EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA

add方法大致流程

当 要 add 进第1个元素时，minCapacity为(size+1=0+1=)1

在Math.max()方法比较后，minCapacity 为10

然后紧接着调用ensureExplicitCapacity更新modCount的值

并判断是否需要扩容

oldCapacity为旧数组的容量

newCapacity为新数组的容量(oldCap+oldCap/2:即更新为旧容量的1.5倍)

检查新容量的大小是否小于最小需要容量，如果小于那就将最小容量置为数组的新容量

如果新容量大于MAX_ARRAY_SIZE，使用hugeCapacity比较二者

hugeCapacity逻辑：

对minCapacity和MAX_ARRAY_SIZE进行比较

若minCapacity大，将Integer.MAX_VALUE作为新数组的大小

若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

add方法执行流程总结

• 这是第一次调用add方法的过程，当扩容值capacity为10之后，

• 继续添加第2个元素(先注意调用ensureCapacityInternal方法传递的参数为size+1=1+1=2)

• 在ensureCapacityInternal方法中，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成立，所以直接执行ensureExplicitCapacity方法

• ensureExplicitCapacity方法中minCapacity为刚刚传递的2，所以第二个if判断(2-10=-8)不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 grow 方法。数组容量为10，add方法中 return true,size增为1。

• 假设又添加3、4......10个元素(其中过程类似，但是不会执行grow扩容方法)

• 当add第11个元素时候，会进入grow方法时，计算newCapacity为15，比minCapacity(为10+1=11)大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11

add(int index,E element)方法

add(int index, E element)方法(在元素序列指定位置(假设该位置合理)插入)的过程大概是下面这些

• 检测数组是否有足够的空间(这里的实现和上面的)

• 将 index 及其之后的所有元素向后移一位

• 将新元素插入至 index 处.

• 将新元素插入至序列指定位置，需要先将该位置及其之后的元素都向后移动一位，为新元素腾出位置。这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时

• 在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二个插入方法

ArrayList的remove方法

remove(int index) 按照下标删除

remove(Object o) 按照元素删除，会删除和参数匹配的第一个元素

nteger.MAX_VALUE - 8

主要是考虑到不同的JVM,有的JVM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的

参考资料

https://www.cnblogs.com/lcj12121/p/11710065.html