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
包提供的并发线程安全的集合类