Java Core「18」JCF 及常见问题

作者：Samson

2022 年 6 月 27 日
本文字数：5025 字
阅读完需：约 16 分钟

01-概述

JCF，Java Collection Framework，是 Java 提供的集合表示和操作框架。一般我们讨论 JCF 时，主要关注的有两部分内容：1. Collection 接口及其实现；2. Map 接口及其实现。

图 1. Collection 接口及其常用实现

图 2. Map 接口及其常用实现

02-Collection

如图 1. 所示，Collection 接口包含了三个常用的子接口：

List，有序列表，元素可重复
Set，无序列表，元素不可重复
Queue，有序列表，一端进，一端出

02.1-ArrayList vs. LinkedList

数据结构不同，ArrayList 基于数组实现，LinkedList 基于双向链表实现，且实现了双端队列接口。
ArrayList 支持随机访问，LinkedList 不支持。
取决于数据结构，导致适应的操作也不同。ArrayList 适合查找、追加操作，不适合插入、删除操作。LinkedList 适合插入、删除，不适合查找操作。
内存占用不同。ArrayList 占用的所有内存空间都用来存储其元素，LinkedList 占用的所有空间除了用来存储其元素外，还需存储元素的前驱和后继。所以，存储同样数量的元素，LinkedList 所需的空间更多。

02.2-ArrayList 扩容原理

当数组满时，即列表容量不足以容纳新元素时，ArrayList 会自动扩容。扩容逻辑在java.util.ArrayList#grow方法中：

// 新容量是旧容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);

复制代码

02.3-ArrayList 序列化

ArrayList 基于数组实现，列表中的数据被存储在elementData数组中：

transient Object[] elementData;

复制代码

ransient关键字表明，序列化时会忽略该属性。那么为什么要这样实现呢，直接将列表中的元素全部序列化，反序列化时再将全部元素反序列化，岂不是更简单？

我们知道，ArrayList 的容量和当前保存的元素数并不是一直相等的，也就是说，elementData数组并不是一直都是满的。所以，如果直接对数组进行序列化，需要对数组中的空元素进行处理，会降低序列化和反序列化的效率。

ArrayList 对象的序列化和反序列化逻辑在java.util.ArrayList#writeObject和java.util.ArrayList#readObject方法中。

02.4-ArrayList 实现线程安全的几种方式

通过java.util.Collections#synchronizedList包装，并使用包装后的对象。
通过 CopyOnWriteArrayList（较推荐）或 Vector（不推荐，历史问题）等线程安全的类，而非 ArrayList。
在使用 ArrayList 时，使用synchronized同步机制。

02.5-CopyOnWriteArrayList 原理

图 3. CopyOnWriteArrayList 类图

CopyOnWriteArrayList 是线程安全版本的 ArrayList，它采用了读写分离的并发策略：并发读时，无序加锁；并发写时，先拷贝一份副本，再在副本上执行操作，结束后将原容器的引用指向新副本。

参考：

图 4. 面渣逆袭：Java集合连环三十问

03-Map

不同于 Collection 接口，Map 接口定义的是二维结构。HashMap 是最常用的其实现类之一。

03.1-HashMap 的数据结构

自 Java 8 开始，HashMap 采用”数组 + 链表 / 红黑数“的数据结构。

其底层是一个一维数组：

transient Node<K,V>[] table;

复制代码

数组中的元素 Node 实现了 Map.Entry<K,V> 接口，用来存储键值对。

static class Node<K,V> implements Map.Entry<K,V> { ... }

复制代码

初始时，table[i] 是一个链表，当其长度超过一定值时（默认为 8）且 table 长度不小于 64，链表会被重构成红黑树。

若红黑树中的节点小于 6 时，红黑树变为链表。

table[i] 一般被称作”桶“。

03.2-HashMap#put 方法源码分析

HashMap#put方法的具体实现逻辑在HashMap#putVal中：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,			   boolean evict) {	Node<K,V>[] tab; Node<K,V> p; int n, i;	if ((tab = table) == null || (n = tab.length) == 0)		// 初始化数组		n = (tab = resize()).length;	if ((p = tab[i = (n - 1) & hash]) == null)    // 若 hash 所在的桶中无数据，则创建一个 Node 		tab[i] = newNode(hash, key, value, null);	else {		// 若 hash 所在的桶中有数据		Node<K,V> e; K k;		// 若 hash 与 链表根或树根节点的hash值一致，则返回此元素		if (p.hash == hash &&			((k = p.key) == key || (key != null && key.equals(k))))			e = p;		else if (p instanceof TreeNode)			// 若桶中已是红黑树，则在树中插入元素			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);		else {			// 若桶中仍是链表			for (int binCount = 0; ; ++binCount) {				if ((e = p.next) == null) {					// 在链表最后插入新的节点					p.next = newNode(hash, key, value, null);					// 若链表长度超过限度（默认为8），则尝试将其转换为红黑树					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st						treeifyBin(tab, hash);					break;				}				// 若与链表中的某个元素的hash值相等，则返回此元素				if (e.hash == hash &&					((k = e.key) == key || (key != null && key.equals(k))))					break;				p = e;			}		}		if (e != null) { // existing mapping for key			V oldValue = e.value;			if (!onlyIfAbsent || oldValue == null)				e.value = value;			afterNodeAccess(e);			return oldValue;		}	}	++modCount;	if (++size > threshold)		resize();	afterNodeInsertion(evict);	return null;}

复制代码

3.3-HashMap 扩容机制

HashMap 的容量是 2 的 n 次幂，如果创建 HashMap 时，传入的初始容量不是 2 的 n 次幂，会自动扩大为比它大的、最近的 2 的 n 次幂。

触发扩容时，容量也会扩大为原来的 2 倍。

扩容后，需要将容器中的元素重新插入到新的数组中。假设，扩容前容量为 2n2^n2n，扩容后容量为 2n+12^{n+1}2n+1。扩容前，键的 hash 值的最后 n 位用来计算其所属桶的索引；扩容后，键的 hash 值的最后 n+1n+1n+1 位用来计算其索引。若新增的第 n+1n+1n+1 位是 0，则计算出的索引值不变；若是 1，则新的索引为旧索引+2n2^n2n。

03.4-HashMap 的线程安全问题

Java 7 之前，往桶中列表插入元素时，采用的是头插法。多线程情景下，扩容时可能会出现循环列表。详情分析，参考[1]。Java 8 之后，采用尾插法，保持链表的顺序，不会出现问题。
多线程情景下，同时执行 put 方法时，若 key 计算出的 hash 值相同，则会出现值被覆盖的情况。Java 7 和 Java 8 中都存在这个问题。
多线程情景下，put 方法和 get 方法同时执行时，若遇到扩容，则有可能会出现 get 的结果为 null 的情况。

有什么办法可以避免线程安全问题呢？与 ArrayList 线程安全类似：

使用java.util.Collections#synchronizedMap方法，在包装后的对象上执行操作。
使用线程安全版本来替代 HashMap，例如 HashTable 和 ConcurrentHashMap。前者不推荐使用，因为所有的操作都使用synchronized关键字修饰，效率很低。

03.5-ConcurrentHashmap 的实现

Java 7 之前，ConcurrentHashmap 基于分段锁实现，Java 8 之后，基于 CAS + synchronized关键字实现。

基于分段锁实现 (Java 7)

内部结构与 HashMap 不同，内部包含一个 Segment 数组，每个 Segment 包含 HashEntry 数组，用来存储键值对。换个角度理解，每个 Segment 都相当于一个 HashMap，（默认情况下，Segment 数组的长度为 16），对每个 Segment 的读写都是独立的，避免了对整个哈希表进行加锁。

基于 CAS + synchronized 关键字实现 (Java 8)

当表为空时，通过 CAS 初始化

if (tab == null || (n = tab.length) == 0) 		tab = initTable();
private final Node<K,V>[] initTable() {	Node<K,V>[] tab; int sc;	while ((tab = table) == null || tab.length == 0) {		if ((sc = sizeCtl) < 0)		  //如果正在初始化或者扩容			Thread.yield(); // lost initialization race; just spin		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  // CAS 操作			try {				if ((tab = table) == null || tab.length == 0) {					int n = (sc > 0) ? sc : DEFAULT_CAPACITY;					@SuppressWarnings("unchecked")					Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];					table = tab = nt;					sc = n - (n >>> 2);				}			} finally {				sizeCtl = sc;			}			break;		}	}	return tab;}

复制代码

通过前面的分析，可以知道，多线程场景下，HashMap 执行 put 方法时，当某个桶中无任何元素时，两个线程同时插入会出现元素覆盖的情况（代码如下）：

if ((p = tab[i = (n - 1) & hash]) == null) 		tab[i] = newNode(hash, key, value, null);

复制代码

在 ConcurrentHashmap 中被修改为了：

if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {	// 通过 CAS 自旋写入	if (casTabAt(tab, i, null,				 new Node<K,V>(hash, key, value, null)))		break;                   // no lock when adding to empty bin}

复制代码

当需要扩容时：

if ((fh = f.hash) == MOVED)	tab = helpTransfer(tab, f);
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {	Node<K,V>[] nextTab; int sc;	if (tab != null && (f instanceof ForwardingNode) &&		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {		int rs = resizeStamp(tab.length);		while (nextTab == nextTable && table == tab &&			   (sc = sizeCtl) < 0) {			if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||				sc == rs + MAX_RESIZERS || transferIndex <= 0)				break;			if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {				transfer(tab, nextTab);				break;			}		}		return nextTab;	}	return table;}

复制代码

不需要扩容时，使 synchronized 关键字，确保多线程执行 put 方法能够同步进行：

synchronized (f) {	....}

复制代码

03.6-实现一个简单的 HashMap

数据结构采用：桶数组 + 链表。更具体点讲，桶数组长度为 2 的整数次幂。因此，根据键对象的哈希值确定桶数组下标就相对简单：hash ^ (capacity - 1)。散列到同一个桶中的不同对象（即哈希值碰撞），采用链表的方式，且插入方式使用尾插法。考虑到实现的复杂度，暂时不考虑链表超过指定长度后转化为红黑树。

使用size记录映射表中的键值对数量，当其超过负载因子0.75之后，自动对桶数组进行扩容。扩容后的桶数组是原来的 2 倍。

关键部分 put 方法的代码贴在下面：

private V putVal(int hash, K key, V value) {	Node p;	int i = this.getIndex(hash, this.table.length);	if (this.table == null || this.table.length == 0) {		// 如果桶数组为空，则初始化为默认容量		this.table = new Node[DEFAULT_CAPACITY];	} else if ((p = this.table[i]) == null) {		// 若 hash 对应的桶中尚无任何元素，则插入一个元素		this.table[i] = new Node(key, value);		size++;	} else {		// 若 hash 对应的桶中已包含元素，则遍历链表，找到表尾		while (p.next != null) {			if (p.hash == hash && p.key == key) {				// 链表中存在相同的key，新值覆盖旧值				p.value = value;				return value;			}			p = p.next;		}		p.next = new Node(key, value);		size++;	}	// 当桶数组中元素超过限度，自动对桶数组进行扩容，扩容后的数组容量为原数组的2倍	if (size >= (this.table.length * LOAD_FACTOR)) {		// 包括扩容，再哈希，即将旧桶数组中的元素重新散列到新的桶数组中		resize();	}
	return value;}