面试官：请说出线程安全的 ArrayList 有哪些，除了Vector

以下环境是 JDK 1.8

ArrayList 的初始容量

面试官：你看过 ArrayList 的源码？

Python 小星：看过

面试官：那你说下ArrayList 的初始容量是多少？

Python 小星：10

面试官：你确定!？

......

1、ArrayList源码 -- 构造器

从源码里我们可以看到，无参构造函数，容量初始化为 0，有参构造函数的初始容量自定义。

我们也可以做个测试验证，我们通过反射获取 elementData 的长度，即是 ArrayList 的容量

输出结果：

思考哈：为什么默认长度是 10 ？

hashmap 里默认 16，是为了 hash 算法。@Python大星 认为固定长度的数组初始容量不需要考虑 hashmap 里的hash冲突，取 10 可能是不大不小的值，然后一直引用下来。就像你说为什么数组的下标都是从 0 开始，而不是从 1 开始，a [0] 就是偏移为 0 的位置。a [k] 就表示偏移 k 个元素类型大小的位置，少做一步减法，就一直被继承下来，无论是 C语言、Java语言 或者 Python 语言。

知道的小伙伴欢迎在评论下留言，也许无形中帮助了很多迷茫的人。

ArrayList 是“动态数组”-- 扩容

1、“动态”体现在 ArrayList的自动扩容上

ArrayList 如何完成一次扩容？

场景：ArrayList 初始容量是 10 ，如果再 add 一个元素，会怎样？

我们可以看到 JDK8 相比之前做了一点优化，使用了 >> 位运算

数组会按照 10 + 10 * 0.5 = 15 扩容（把原来的数组复制到另一个内存空间更大的数组中），扩容后再把指向原数的地址换到新数组。

ArrayList、LinkedList、Vector 的区别？

① Arraylist 和 Vector 是采用数组方式存储数据，所以插入数据慢，查找有下标，所以查询数据快

此数组元素数大于实际存储的数据以便增加插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，

② Vector 本身所有方法都是用 synchronized 修饰的，线程安全，所以性能上比 ArrayList 要差

③ LinkedList 使用双向链表实现存储

按序号索引数据需要进行向前或向后遍历，查找较慢，但是插入数据时只需要记录本项前后项即可，插入数据较快。

为什么说 ArrayList 不是线程安全？

1、测试

输出结果：999

可以看出和我们预期的不一致。

在 add 操作分 2 步 ：

① 判断 elementData 数组容量是否满足需求

② 在 elementData 对应位置上设置值

在多个线程进行 add 操作时可能会导致 elementData 数组越界。

elementData [size++] = e 设置值的操作同样会导致线程不安全。从这儿可以看出，这步操作也不是一个原子操作，线程不安全。

LinkedList

LinkedList 内部是双向链表结构

面试官：LinkedList 为什么说查找慢？它是怎么查找的？

Python 小星：因为它是链表结构，从表头开始遍历，所以当查找元素在链表后面，会比较慢

面试官：好的。回去等通知！

废话不多说，我们看下源码

从第二张图中我们可以看出：

链表中的 index 只是标记元素的相对于链表头部（first 指向的）node 的个数 ，这样在根据 index 查询时，可以根据 index 和 size 的关系，提高查询性能。当 index 大致在链表的前半部分时（index > 1)），从链表的首部开始遍历显然更快，而当 index 大致在链表的后半部分时（index > (size >> 1)），从链表的尾部开始遍历显然更快，这样就使得查找次数从 n 次将为了 n/2 次，虽然查找算法的时间复杂度还是 O (n)。

我们都知道 LinkedList 是链表结构，那到底是单向链表还是双向链表？

由上图可以看出Linkedlist是双向链表

为什么说 Vector 过时了，弃用了？

https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated#comment12234699_1386288

首先需要说明，在 Java 8 中 ，官方并没有弃用。

① Vector 对每个单独的方法进行同步；

参考 https://javaconceptoftheday.com/not-use-vector-class-code/

① 无需 vector 也能实现线程安全

可以使用 Collections 类中 synchronizedList 来实现线程安全的 ArrayList

② 线程安全的 Vector 非常耗时

Vector 类的所有方法均已同步。这使 Vector 对象线程上的每个操作都安全。但是,这很耗时。因为，您需要为Vecto r在对象上执行的每个操作获取对象锁。通常，我们需要一组操作而不是每个操作都同步。一次锁定对象，为什么每次操作都要一次又一次次地获得锁？这是耗时的，降低性能。

③ Vector 设计不好

Vector 结合 2 个功能，“可调整大小的数组” 和 “同步”。这使设计不佳，而应始终使用ArrayList类。您将拥有可调整大小的数组，每当您要使其同步时，可以使用 Collections 中 synchronizedList 来实现线程安全的 ArrayList。

除了 Vector ，还有哪些线程安全的 ArrayList ？

synchronizedList 和 CopyOnWriteArrayList

1、synchronizedList

① synchronizedList 的用法（适合对数据要求较高的情况）

SynchronizedList 的 add 方法

add 方法

我们可以看出，SynchronizedList 用 synchronized 同步的是代码块，而 vector 用synchronized 同步的是方法。

【1】SynchronizedList 有很好的扩展和兼容功能。他可以将所有的 List 的子类转成线程安全的类；

【2】使用 SynchronizedList 的时候，进行遍历时要手动进行同步处理。

② CopyOnWriteArrayList （适合读多写少的场景）

1、add方法

CopyOnWriteArrayList 中 add 方法的实现（向 CopyOnWriteArrayList 里添加元素），可以发现在添加的时候是需要加锁的，写入时复制（CopyOnWrite），copy 一份新的数组进行相关的操作，在执行完修改操作后将原来集合指向新的集合来完成修改操作

add方法

2、get方法

读的时候不需要加锁，如果读的时候有多个线程正在向 CopyOnWriteArrayList 添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的 CopyOnWriteArrayList。

get方法

CopyOnWriteArrayList 缺点:

【1】 内存占有问题：很明显，两个数组同时驻扎在内存中，如果实际应用中，数据比较多，而且比较大的情况下，占用内存会比较大，针对这个其实可以用 ConcurrentHashMap 来代替。

【2】 数据一致性：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器

| 文

閱讀更多 Python大星 的文章

關鍵字: 线程 C语言 Overflow