Java 集合类面试题之一
集合类基础
常见的集合类有哪些
Map 接口和 Collection 接口是所有集合框架的父接口，其中 Collection 接口的子接口包括 Set 接口和 List 接口：
- Set 接口的实现类主要有：HashSet、TreeSet、LinkedHashSet 等
- List 接口的实现类主要有：ArrayList、LinkedList、Stack、Vector 等
- Map 接口的实现类主要有：HashMap、TreeMap、HashTable、ConcurrentHashMap 以及 Properties 等
HashMap 与 HashTable 的区别
- HashMap 允许 K/V 都为 Null，Hashtable 规定 K/V 都不允许为 Null
- HashMap 继承自 AbstractMap 类，而 HashTable 继承自 Dictionary 类
- HashMap 没有考虑同步，是线程不安全的；Hashtable 使用了
synchronized关键字，是线程安全的
集合类源码分析
HashMap 的 Put 方法的具体流程
★展开源代码★
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
// 1.如果table为空或者长度为0，即没有元素，那么使用resize()方法扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.计算插入存储的数组索引i，此处计算方法同 1.7 中的indexFor()方法
// 如果数组为空，即不存在Hash冲突，则直接插入数组
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3.插入时，如果发生Hash冲突，则依次往下判断
else {
HashMap.Node<K, V> e;
K k;
// a.判断table[i]的元素的key是否与需要插入的key一样，若相同则直接用新的value覆盖掉旧的value
// 判断原则equals() - 所以需要当key的对象重写该方法
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b.继续判断：需要插入的数据结构是红黑树还是链表
// 如果是红黑树，则直接在树中插入 or 更新键值对
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 如果是链表，则在链表中插入 or 更新键值对
else {
// i .遍历table[i]，判断key是否已存在：采用equals对比当前遍历结点的key与需要插入数据的key
// 如果存在相同的，则直接覆盖
// ii.遍历完毕后任务发现上述情况，则直接在链表尾部插入数据
// 插入完成后判断链表长度是否 > 8：若是，则把链表转换成红黑树
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 对于i 情况的后续操作：发现key已存在，直接用新value覆盖旧value&返回旧value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后，判断实际存在的键值对数量size > 最大容量
// 如果大于则进行扩容
if (++size > threshold)
resize();
// 插入成功时会调用的方法（默认实现为空）
afterNodeInsertion(evict);
return null;
}
HashMap 的扩容操作如何实现的
★展开源代码★
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* 该方法有两种使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;// 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 扩容前的数组容量（数组长度）
int oldThr = threshold;// 扩容前数组的阈值
int newCap, newThr = 0;
if (oldCap > 0) {
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若没有超过最大值，就扩容为原来的2倍（左移1位）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每一个bucket都移动到新的bucket中去
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
集合类的线程安全性
集合类的非线程安全问题
问题：普通的集合类是非线程安全的，请编写一个线程不安全的使用案例并给出解决方案
★展开案例代码★
1
2
3
4
5
6
7
8
9
10
11
12
13
public class ArrayListUnSafe {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
new Thread(() -> {
list.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(list);
}).start();
}
}
}
1
运行结果可能会抛出 java.util.ConcurrentModificationException 异常
回答：
- 第一方法：使用 Vector 替代 ArrayList，即
List<String> list = new Vector<>(); - 第二种方法：使用 Collectons 类，即
List<String> list = Collections.synchronizedList(new ArrayList()); - 第三种方法：使用 CopyOnWriteArrayList 类，即
List<String> list = new CopyOnWriteArrayList<>();
集合类的写时复制（CopyOnWrite）
写时复制（CopyOnWrite）介绍
CopyOnWrite 容器即写时复制的容器。往一个容器添加元素的时候，不直接往当前容器的 Object[] 添加，而是先将当前 Object[] 进行 Copy，复制出一个新的容器 Object[] newElements，然后新的容器 Object[] newElements 里添加元素，添加完元素之后，再将原容器的引用指向新的容器（setArray（newElements））。这样做的好处是可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写的是不同的容器。JDK 8 的 CopyOnWriteArrayList 的源码如下：
写时复制（CopyOnWrite）优缺点
应用场景：应用于读多写少的并发场景
使用注意：为了减少扩容开销，尽量使用批量添加（减少复制次数）
缺点：存在内存占用问题、数据一致性问题（CopyOnWrite 机制只能保证最终的数据一致，不能保证实时数据的强一致性，因此如果希望写入的数据能马上能读到，此时就不应该使用 CopyOnWrite）
线程安全的集合类总结
CopyOnWriteArrayList：CopyOnWriteArrayList 中的 add、set、remove 等方法，都是用了 ReentrantLock 的lock()来加锁，unlock()来解锁。当增加元素时使用Array.copyOf()来拷贝副本，在副本上增加元素，然后改变原引用指向副本，读操作不加锁，适合读操作远远多于写操作的应用。CopyOnWriteArraySet：CopyOnWriteArraySet 是在 CopyOnWriteArrayList 的基础上使用了 Java 的装饰模式，底层还是使用 CopyOnWriteArrayList 来实现。List 和 Set 的区别同样适用于 CopyOnWriteArrayList 和 CopyOnWriteArraySet。ConcurrentHashMap：ConcurrentHashMap 是 HashMap 的线程安全版（但此类不允许 Null 做键或者值），同 HashTable 相比，ConcurrentHashMap 不仅保证了访问的线程安全性，而且在效率上与 HashTable 相比有较大的提高。ConcurrentHashMap 允许多个修改操作并发进行，底层使用了锁分离的技术，即代码块锁，而不是方法锁。其中使用了多个锁来控制对 HashTable 的不同部分进行的修改。ConcurrentHashMap 内部使用段（Segment）来表示不同的部分，每个段其实就是一个小的 HashTable，它们有自己的锁（使用 ReentrantLock 来实现）。只要多个修改发生在不同的段上，它们就可以并发进行。
总结：
- HashMap 是非线程安全的，HashTable 是线程安全的
- LinkedList、ArrayList、HashSet 是非线程安全的，Vector 是线程安全的
- ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet 是线程安全的，这几个都是
java.util.concurrent包提供的并发线程安全的集合类