容器分析

容器分析

ArrayList

序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化

ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

删除元素

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的

Fail-Fast

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。代码参考上节序列化中的 writeObject() 方法。

数组的默认大小为 10

ConcurrentHashMap

存储结构

实现

采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）

size 操作

每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数

在执行 size 操作时，需要遍历所有 Segment 然后把 count 累计起来

ConcurrentHashMap 在执行 size 操作时先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那么可以认为这个结果是正确的

尝试次数使用 RETRIES_BEFORE_LOCK 定义，该值为 2，retries 初始值为 -1，因此尝试次数为 3。

如果尝试的次数超过 3 次，就需要对每个 Segment 加锁

JDK 1.8 的改动

JDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发度与 Segment 数量相等。JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。并且 JDK 1.8 的实现也在链表过长时会转换为红黑树

CopyOnWriteArrayList

读写分离

适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

缺陷

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右

数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中

HashMap

拉链法的工作原理

新建一个 HashMap，默认大小为 16

查找

计算键值对所在的桶

在链表上顺序查找，时间复杂度显然和链表的长度成正比

put 操作

HashMap 使用第 0 个桶存放键为 null 的键值对。

使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部。

确定桶下标

计算 hash 值

取模

令 x = 1<<4，即 x 为 2 的 4 次方

位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。

扩容-基本原理

设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此查找的复杂度为 O(N/M)

为了让查找的成本降低，应该使 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。

参数

capacity table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。

size 键值对数量

threshold size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作

loadFactor  装载因子，table 能够使用的比例，threshold = (int)(capacity* loadFactor)

扩容-重新计算桶下标

计算数组容量

HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。

链表转红黑树

一个桶存储的链表长度大于等于 8 时会将链表转换为红黑树