一月的第二周，来补习 Java 的容器设计。
自己所欠的 Java 基础实在是多，主要是因为能力不足。如今的我，感觉可以追进 Java 容器的源码中了，之前写过了 HashMap 和 TreeMap，这周来看剩下的容器。
像是之前写 HashMap 和 TreeMap 一样，学习每个容器时从 add() 或 put() 方法开始，牵扯出背后的代码与逻辑。
ArrayList
ArrayList 是列表的一种，特点是能够自动扩容（即动态数组）。
ArrayList 的 add() 方法本身很简短，在检查容量大小之后，在数组中添加元素。
1
2
3
4
5
| public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
|
在这三行代码的方法中只能看出，ArrayList 的内部是由数组实现的，也就是代码中的 elementData。
继续追进去看里面的代码，会发现代码很零碎，一个方法嵌套着另一个，而每一个方法都只有几行代码而已。因此我整理了一下，将涉及到的代码整理成下面这个样子（每一行很长，要水平拖动才能看到全部）：
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
| public boolean add(E e) { |
|
┌-----------------------------------------------------------------------------------------------------------------------┐ |
| ensureCapacityInternal(size + 1); | ■ 确保列表容量足够
| ↘ ↘ ↘ | |
| private void ensureCapacityInternal(int minCapacity) { | |
| | |
| ┌--------------------------------------------------------------------------------------------------------------┐ | |
| | ensureExplicitCapacity( ┌-------------------------------------------------------------------------------┐ ); | | ■ 检查列表容量足够
| | | calculateCapacity(elementData, minCapacity) | | | ■ 计算列表容量，最小是10
| | ↓↓↓ | ↘ ↘ ↘ | | | |
| | ↓↓↓ | private static int calculateCapacity(Object[] elementData, int minCapacity) { | | | |
| | ↓↓↓ | if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { | | | |
| | ↓↓↓ | return Math.max(DEFAULT_CAPACITY, minCapacity); | | | |
| | ↓↓↓ | } | | | |
| | ↓↓↓ | return minCapacity; | | | |
| | ↓↓↓ | } | | | |
| | ↓↓↓ └-------------------------------------------------------------------------------┘ | | |
| | | | |
| | private void ensureExplicitCapacity(int minCapacity) { | | |
| | modCount++; | | ■ 每一次检查容量，都会使modCount+1
| | if (minCapacity - elementData.length > 0) | | |
| | | | |
| | ┌-----------------------------------------------------------------┐ | | |
| | | grow(minCapacity); | | | ■ 当最小容量超过列表长度时，扩容
| | | ↘ ↘ ↘ | | | |
| | | private void grow(int minCapacity) { | | | |
| | | int oldCapacity = elementData.length; | | | |
| | | int newCapacity = oldCapacity + (oldCapacity >> 1); | | | ■ 每次容量扩容1.5倍
| | | if (newCapacity - minCapacity < 0) | | | |
| | | newCapacity = minCapacity; | | | |
| | | if (newCapacity - MAX_ARRAY_SIZE > 0) | | | |
| | | newCapacity = hugeCapacity(minCapacity); | | | |
| | | elementData = Arrays.copyOf(elementData, newCapacity); | | | ■ 将原数组的数据，拷贝到新数组中
| | | } | | | |
| | └-----------------------------------------------------------------┘ | | |
| | } | | |
| | | | |
| └--------------------------------------------------------------------------------------------------------------┘ | |
| } | |
└-----------------------------------------------------------------------------------------------------------------------┘ |
|
elementData[size++] = e; |
return true; |
} |
|
从 ArrayList 添加元素的 add() 方法可以看出：
- ArrayList 内部由数组实现
- ArrayList 的默认容量大小是 10，每次扩容时增加到原来的 1.5 倍（通过位运算实现）
- ArrayList 每次扩容，都会将之前保存的内容，全部复制拷贝到新数组中。
- 每次 ArrayList 增加元素时，会在确保容量足够的时候就增加 modCount。
- ArrayList 允许添加 null。
没什么用的小知识
曾经在其他博客中看到 Arrays.asList() 方法，这个方法与 ArrayList 有李逵李鬼的关系。
Arrays.asList() 方法可以将多个元素直接拼接为列表，并返回该列表，如下面这行代码：
1
| List<String> list = Arrays.asList("hello", ",", "world", "!");
|
应当注意的是，这里得到列表是无法增加元素的，例如：
现在去探索为什么会报错。看源码时发现，在 Arrays.asList() 方法的内部，是这么处理的：
1
2
3
| public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
|
它返回了一个 ArrayList 对象，但是很坑的是，此 ArrayList 非彼 ArrayList，这里的 ArrayList，是 Arrays 类内部定义的列表类，而不是我们常规意义上的动态列表。
1
2
3
4
5
| private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {
}
|
但是这个内部定义的 ArrayList 类，是没有重写父类 AbstractList 类的 add() 方法的，而父类默认的 add() 方法是直接抛 UnsupportedOperationException 异常的。
回看 Arrays.asList() 方法，它在注释中已经说明清楚了：
Returns a fixed-size list …
返回一个定长列表。
Vector
Vector 是上古类，从 JDK 1.0 开始就存在了（ArrayList 在 JDK 1.2 才出现）。这个类怎么说呢，我工作至今，一次都没有用过……我感觉这个类存在的意义，就是为了招聘面试。
Vector 能够实现的功能，跟 ArrayList 几乎完全一样，除了它是线程安全的。Vector 线程安全的实现方式是，在所有方法外面都加上 synchronized 关键字，同时间只允许一个线程执行方法。
对比 Vector 和 ArrayList 的 add() 方法，逻辑上几乎完全相同，唯二值得单独提出来的地方，一处是 Vector 的 add() 方法加了 synchronized 关键字，代码对比如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
|
另一处稍微值得提下的地方是，ArrayList 扩容时每次增加到 1.5 倍，而 Vector 扩容时每次增加到 2 倍。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
|
为什么 ArrayList 扩容是到 1.5 倍，而 Vector 扩容是到 2 倍，为何设计上不相同，我试着查了一下没有查到说法。我目前只能归结为，是因为写代码的大佬不是同一个人，大佬们有自己的想法。
参考别的大佬给出的最佳实践，Vector 类基本是被废弃掉的，如果需要一个线程安全的 list，那么可以使用 JUC 包下的 CopyOnWriteArrayList 类，或者使用 Collections.synchronizedList() 方法：
1
2
| List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
|
不使用 Vector 类，是因为 Vector 类实现线程安全的方式，是在所有方法的外面加上 synchronized 关键字，这个线程同步的方式比较笨重，带来的消耗比较大，因此都建议不去使用。但是为什么 synchronized 关键字消耗大，这个我暂时不清楚，等之后积累并发基础吧。
LinkedList
LinkedList 是另一种数据结构的列表，它通过链表（Node）的形式构成，插入和删除快，但查找慢。
LinkedList 的 add() 方法，简单地令人发指：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public boolean add(E e) {
linkLast(e); ---┐
return true; ↙
} ↙
↙
↙
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
|
就是尾插节点。
LinkedList 的构成元素是双向链表，就是一个值带着两个指针，一个指针指向前一个节点，一个指针指向后一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
| private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
|
ArrayList 增加元素时，如果需要扩容，那么需要拷贝全部数据，删除元素时也需要大量搬移数据。LinkedList 增加和删除元素是直接改动的，但是查找时会慢。
一个没啥好说的类，略了。
LinkedHashMap
LinkedHashMap 类是一个奇怪的 map，在存储上它使用 HashMap 的方式，但是在遍历时，它可以按照插入的顺序输出。举一个例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Map<String, Object> map1 = new HashMap<>();
Map<String, Object> map2 = new LinkedHashMap<>();
map1.put("1", 1);
map1.put("3", 2);
map1.put("2", 2);
map2.put("1", 1);
map2.put("3", 3);
map2.put("2", 2);
System.out.println("HashMap 输出：\t\t" + map1);
System.out.println("LinkedHashMap 输出：\t" + map2);
|
分别实例化一个 HashMap 对象和一个 LinkedHashMap 对象，按照一样的顺序插入三组 key-value（key 的顺序是 “1”、”3”、”2”），然后分别输出这两个对象。发现 HashMap 按照内部存储的顺序输出 1 -> 2 -> 3，而 LinkedHashMap 按照插入的顺序输出 1 -> 3 -> 2。
尽管 LinkedHashMap 按照插入的顺序输出，但实际上 LinkedHashMap 存储时的内部结构，是跟 HashMap 一样的，也就是说它跟 HashMap 有一样快的查找速度。
这真是很有意思。
在学习 LinkedHashMap 之前，必须先回顾 HashMap，因为 LinkedHashMap 就是由 HashMap 而来的。
简单来讲，HashMap 有以下几个特征：
- HashMap 采用哈希算法计算存储位置，因此查找速度理论上非常快，为 O(1)。
- HashMap 采用数组+链表+红黑树的拉链法存储结构，正常来讲存数组，哈希冲突时存链表，链表长度超过 8 则转红黑树。
- 当 HashMap 的实际存储个数超过一定大小时（规则：实际个数 > 数组长度 × 负载因子，负载因子默认 0.75），数组扩容。
- HashMap 内部用于存储的数组默认长度是 16，这个长度可以人为规定，但真正的长度只会是 2 的幂，不足则自动设为下一个 2 的幂（例如指定长度为 7 则实际长度为 8，指定长度为 19 则实际长度为 32），而且每次数组扩容时将扩容到上一次的两倍。这种设计跟 HashMap 的哈希计算存储位置有关。
好吧，看来也不简单。
可以来看 LinkedHashMap 的 put() 方法了。
但是当看 LinkedHashMap 时，会发现它并没有 put() 方法，其实这在上次查看 HashMap 的 put() 方法时就初见端倪了。这是因为，LinkedHashMap 的确没有 put() 方法，它继承自 HashMap 类，直接使用 HashMap 的 put() 方法。
但是 HashMap 的 put() 方法中留下了空实现几个方法，LinkedHashMap 重写了这几个空实现的方法，此外还重写了另一个方法，使得它虽然是继承使用 HashMap 的 put() 方法，但是并不完全一样。
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
| 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)
┌----------------------------------┐
tab[i] = | newNode(hash, key, value, null); |
└----------------------------------┘
else {
Node<K,V> e; K k;
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); |
└----------------------------------┘
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
┌---------------------┐
| afterNodeAccess(e); |
└---------------------┘
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
┌----------------------------┐
| afterNodeInsertion(evict); |
└----------------------------┘
return null;
}
|
这真是很有意思，看 HashMap 的源码时，总会发现一些特别巧妙的设计（以及艰涩难读的代码……）。
先说点基础做铺垫。
从总体上说，LinkedHashMap 内部维护了两套存储内容，一套跟 HashMap 完全相同（实际上就是在使用 HashMap），另一套是一条双向链表。每当继承自 HashMap 的那套存储内容发生变化的时候，例如新建、删除、插入等，都要同时在另一套自己维护的双向链表中去做处理。这样，既能白嫖到 HashMap 的极快的查找速度，也能享受到自己维护的双向链表的额外功能。
LinkedHashMap 实现两套存储内容，是通过特殊设计存储结构实现的。LinkedHashMap 沿用 HashMap 的设计，使用数组+链表来实现（暂时忽略红黑树），数组中存放的是链表节点。
HashMap 的链表节点的源码如下：
1
2
3
4
5
6
7
8
| static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
|
LinkedHashMap 的链表节点的源码如下：
1
2
3
4
| static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
}
|
可以看到，LinkedHashMap 的链表节点类（Entry），继承自 HashMap 的链表节点类（Node）。HashMap 的链表节点具有四个信息，分别是 key、value、hash 值、下一个节点的指针。而 LinkedHashMap 的链表节点类除了具有以上四个属性之外，还具有指向 before 节点和 after 节点的指针（需要注意，after 指向的内容，跟 next 指向的内容，并不是同一个东西）。因此可以认为，LinkedHashMap 的链表节点，实际上是具有三个方向的，是一个三向链表节点，它除了具有指向下一个节点的方向之外，还额外新增了两个方向：一个指向 before，一个指向 after。
因此，LinkedHashMap 内部维护了两套存储逻辑，一套跟 HashMap 完全相同，另一套是一条双向链表。
这条双向链表，有两种用处（排序方式）：
- 按照插入顺序排序，遍历时可以按照插入的顺序输出
- 按照访问顺序排序，遍历时按照曾经访问过的先后顺序输出（LRU 算法）
这两种排序方式都是有意义的，一个可以记录 LinkedHashMap 插入数据的顺序，另一个可以记录 LinkedHashMap 访问数据的顺序，可以用作缓存，按时间先后输出最近看过的数据。
了解了以上这些，我们回看 LinkedHashMap 的 put() 方法，也就是使用父类 HashMap 的 put() 方法时，重写的那三个方法，究竟在做些什么。
LinkedHashMap 一共重写了三个方法：
- newNode() 方法，用于创建链表节点
- afterNodeAccess() 方法，用于处理按照访问顺序排序的情况
- afterNodeInsertion() 方法，用于处理按照插入顺序排序的情况
newNode() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
┌------------------┐
| linkNodeLast(p); | →┐
└------------------┘ ↓
return p; ↙
} ↙
↙
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
|
在原先创建链表节点的基础上，将该节点设为双向链表的最后一个节点。
afterNodeAccess() 方法
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
| void afterNodeAccess(Node<K, V> e) { ■ 传入访问节点
LinkedHashMap.Entry<K, V> last; |
if (accessOrder && (last = tail) != e) { |
LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, |
b = p.before, |
a = p.after; |
p.after = null; ■ 访问节点之后清空
if (b == null) ■ 处理访问节点原先位置的前一个节点
head = a; |
else |
b.after = a; |
if (a != null) ■ 处理访问节点原先位置的后一个节点
a.before = b; |
else |
last = b; |
if (last == null) ■ 将访问节点设为双向链表的最后一个节点
head = p; |
else { |
p.before = last; |
last.after = p; |
} |
tail = p; |
++modCount; |
} |
} |
|
首先解释 accessOrder 是什么：LinkedHashMap 的双向链表有两种排序方式，一种是按照插入顺序排序，一种是按照访问顺序排序。accessOrder 是一个布尔值，当它为 true 时表示按照访问顺序排序，当它为 false 时表示按照插入顺序排序。默认情况下，accessOrder 为 false，也就是说，默认情况下 LinkedHashMap 的双向链表是按照插入顺序排序的。
afterNodeAccess() 方法的意义是，当 accessOrder 为 true 时（按照访问顺序排序），将最新访问的节点，放到 LinkedHashMap 双向链表的最后一个的位置处。具体的实现的逻辑是，将该节点从原位置处删除掉，并设置为双向链表的最后一个节点。
afterNodeInsertion() 方法
1
2
3
4
5
6
7
8
9
10
11
| void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict
&& (first = head) != null
&& removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
|
对于 LinkedHashMap 而言，afterNodeInsertion() 默认是一个无用的方法，执行前后不会发生任何变化。但是如果你自己写一个 LinkedHashMap 的子类，重写某个方法，可以让 afterNodeInsertion() 方法生效。
afterNodeInsertion() 方法的作用是，每当新节点插入时，就把双向链表的最开始的节点删除掉，以保持双向链表的长度在插入前后是不变的。这个方法的意义在于，如果子类想要实现缓存，而缓存的长度是有限的，可以使用该方法来做处理，当缓存的容量满了之后，每插入一个新节点，就删除掉最早插入的旧节点，维持缓存的容量。
afterNodeInsertion() 方法有三个执行逻辑上的参数，只有这三个参数都为 true 时，该方法才会删除双向链表的头节点：
evict 由 HashMap 的 putVal() 方法定义，在插入节点时默认为true，表示可以删除头结点。如果 evict 为 false，表示 map 处于“creation mode”（创造模式，只创造，不删除）。
(first = head) != null 双向链表有头结点（否则没得删）
removeEldestEntry(first)) 默认返回 false，表示不删除之前插入的节点。子类如果想实现缓存，那么需要重写该方法，官方还给了一个示例：
1
2
3
4
5
6
|
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() < MAX_ENTRIES;
}
|
LinkedHashMap 还有很多地方并没有看，这里只简单探究了 LinkedHashMap 插入新元素的逻辑（而且还没关注当链表长度过长转成红黑树是怎么样的）。HashMap 和 LinkedHashMap 的源码实在是有够神奇，我很是服气……
LinkedHashMap 先写到这里了。
最后安利一篇博文：《LinkedHashMap 源码详细分析（JDK1.8）》。
Hashtable
跟 ArrayList 和 Vector 的关系几乎完全一样，HashMap 和 Hashtable 也是如此。
在 JDK 1.0 时，Java.util 包中还只有 Vector 和 Hashtable（当然还有别的类，这里是针对于 ArrayList 和 HashMap 而言的），它们两个都通过在方法前加 synchronized 关键字实现线程安全。在 JDK 1.2 时，Java.util 包中新增了 ArrayList 和 HashMap 这两个线程非安全的类，但是可以通过 Collection 类的静态方法将它们转换成线程安全的类，这样就减轻了性能要求。在 JDK 1.5 时，JUC 包中的 CopyOnWriteArrayList 和 ConcurrentHashMap 出现，基本宣告了 Vector 和 Hashtable 的死刑。
但是和 Vector 稍有不同的是，Hashtable 并不是和 HashMap 的各个方法只有 synchronized 关键字的区别，而是在设计上就有所不同。HashMap 和 Hashtable 都基于哈希算法实现，通过数组+链表的基本数据结构构成，但是在算法和数据存储上都略有区别。本次只关注 Hashtable 的 put() 方法。
Hashtable 的 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
62
63
64
65
66
67
68
69
70
71
72
73
| public synchronized V put(K key, V value) { |
|
if (value == null) { ■ value不能为null
throw new NullPointerException(); |
} |
|
Entry<?,?> tab[] = table; ■ 取Hashtable的存储数组
int hash = key.hashCode(); ■ 取哈希值（暗中要求key也不能为null）
int index = (hash & 0x7FFFFFFF) % tab.length; |
@SuppressWarnings("unchecked") |
Entry<K,V> entry = (Entry<K,V>)tab[index]; ■ 根据key的哈希值找到数组的桶
for(; entry != null ; entry = entry.next) { |
if ((entry.hash == hash) && entry.key.equals(key)) { ■ key相同时替换value，并直接返回
V old = entry.value; |
entry.value = value; |
return old; |
} |
} |
┌------------------------------------┐ |
| addEntry(hash, key, value, index); | ■ 添加key-value，详见下
└------------------------------------┘ |
return null; ↙ |
} ↙ |
↙ .
↙ .
private void addEntry(int hash, K key, V value, int index) { |
modCount++; |
|
Entry<?,?> tab[] = table; |
if (count >= threshold) { ■ 如果容量饱和（默认 size >= 数组大小 × 0.75）
┌-----------┐ |
| rehash(); | ■ 扩大数组容量，并重新装填key-value，详见下
└-----------┘ |
tab = table; |
hash = key.hashCode(); |
index = (hash & 0x7FFFFFFF) % tab.length; ■ 计算需要插入key-value在新数组中的位置
} |
|
@SuppressWarnings("unchecked") |
Entry<K,V> e = (Entry<K,V>) tab[index]; ■ 在数组中存储key-value，链表头插法
tab[index] = new Entry<>(hash, key, value, e); |
count++; ■ 此时才增加容量计数，如果容量饱和，下一次再扩容
} ↙ |
↙ .
↙ .
protected void rehash() { |
int oldCapacity = table.length; |
Entry<?,?>[] oldMap = table; |
|
int newCapacity = (oldCapacity << 1) + 1; ■ 数组扩容，扩容算法是2n+1，例如11扩容到23
| 这样扩容使数组长度尽可能是质数，哈希算法更平均
if (newCapacity - MAX_ARRAY_SIZE > 0) { |
if (oldCapacity == MAX_ARRAY_SIZE) ■ 数组最大长度是int最大值-8，照顾不同的VM情况
return; |
newCapacity = MAX_ARRAY_SIZE; |
} |
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; |
|
modCount++; |
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); ■ 重算容量饱和值
table = newMap; |
|
for (int i = oldCapacity ; i-- > 0 ;) { ■ 重新装填所有的key-value
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { |
Entry<K,V> e = old; |
old = old.next; |
|
int index = (e.hash & 0x7FFFFFFF) % newCapacity; ■ 每一个key-value都要重算哈希位置
e.next = (Entry<K,V>)newMap[index]; |
newMap[index] = e; |
} |
} |
} |
|
Hashtable 的 put() 方法，总体逻辑上是这样的：
- 内部存储通过
数组+链表的数据结构，没有红黑树，数组默认大小11。
- 每当增加新的 key-value 时，根据哈希值对数组长度取余，计算在数组中的位置，如果 key 存在则替换 value，如果 key 不存在，则在数组的相应位置处采用链表头插法插入。
- 当容量饱和（默认算法是
容量 >= 数组长度 × 0.75）时，扩容数组。数组扩容算法是新数组长度 = 旧数组长度 × 2 + 1，例如初始化数组大小是 11，第一次扩容之后变成了 23。每次扩容时，要将旧数组中的数据迁移到新数组中，每一个数据都要重算哈希位置。
JDK 1.0 的 Hashtable 和 JDK 1.2 HashMap 的实现是不相同的，下面简单列一下不相同的点：
- HashMap 通过
数组+链表+红黑树做底层存储（在 JDK 1.8 之后），而 Hashtable 通过数组+链表做底层存储。
- HashMap 的数组大小默认是 16，如果手动指定数组大小或者数组扩容（扩容算法是扩大到两倍），数组大小也只能是 2 的幂（1、2、4、8、16、32……），而 Hashtable 的数组默认大小是 11，扩容算法是
2n + 1，尽可能使数组大小是质数。这个差异跟两种 map 添加 key-value 数据时的算法有关。
- HashMap 的 key 和 value 都可以是 null，而 Hashtable 则都不可以，否则会抛出空指针异常。这要分别解释 key 和 value。
- 我目前查到的说法，Hashtable 不支持 key 为 null，是因为这个类出现得太早，觉得一切 key 都要有 hashCode，而之后的 HashMap 考虑到了 null 的重要，为它单独做了处理，把所以 key 为 null 的数据存储在数组的第 0 个格子中。
- Hashtable 不支持 value 为 null，是线程安全的考虑。如果 value 可以为 null，那么当 Hashtable 执行 put() 方法并且返回值是 null 时，你并不知道，究竟是因为原来没有这个 key，还是因为原来有 key 但它的 value 是null。HashMap 也是如此，但是它可以通过执行 containsKey() 的方法来判断 key 是否存在，这在单线程下是没有问题的，但是在并发状态下，containsKey() 得到的结果是并不可靠的，可能下一秒 key 就被删除掉了。因此多线程环境下，value 必须不能是 null，Hashtable 是这么设计的，ConcurrentHashMap 也是这么设计的。
- HashMap 和 Hashtable 在插入元素，哈希计算它在数组中的位置的算法，是不一样的。
- HashMap 的哈希算法一环扣一环，它希望加快计算位置的速度（这是一方面的原因），因此不使用 % 取余算法，而通过更快的按位与运算来计算位置（(n - 1) & hash），这就要求了数组的长度只能是 2 的幂，以保证按位与计算出来的结果和取余计算出来的结果是相同的。而数组长度是 2 的幂，哈希计算出来的数值很容易相同（哈希冲突），那么只能让哈希值更平均一些，因此 HashMap 将哈希值的高位和低位按位与，以降低哈希冲突。
- Hashtable 的哈希算法比较简单直接一些，直接将哈希值对数组长度取余。这种算法中数组长度很重要，如果是质数的话，取余结果能够更平均一些，因此 Hashtable 的数组长度默认是 11，而且扩容算法是
2n+1，扩容之后一般也是质数（但是可以手动指定成随便一个数）。尽管 HashMap 对哈希值做了处理，但我查到的资料是，也不如 Hashtable 取余结果平均，但是 Hashtable 会慢。
- 扩容时，HashMap 和 Hashtable 的实现也是不一样的，HashMap 由于数组是 2 的幂数，所以扩容更简单（具体的我没看），但是 Hashtable 只能一个个重算位置。
- HashMap 在 JDK 1.8 之前，在链表中插入元素都是头插法，而在 JDK 1.8 后是尾插法。Hashtable 一直是头插法。HashMap 在 JDK 1.8 之后转用尾插法的原因，是为了防止并发时链表死循环，我对此还不是很理解，一方面 HashMap 又不是线程安全的类，另一方面如果这个问题真的存在，那么前面 7 个 JDK 版本为什么不改……我还是要再积累一点经验再回来看这个问题。
我从总体上理解，认为 HashMap 将优化的重心放在数据的维护上，插入慢一点，扩容快，对外兼容好，而 Hashtable 将优化的重心放在数据的插入上，存储时更平均，扩容代价很大。只是感觉而已。
另外我发现，原来 Hashtable 的 table 并不是首字母大写的，原来 hash 和 table 是组合成一个单词的呀。
ConcurrentHashMap
ConcurrentHashMap 是 HashMap 的线程安全类，在 JUC 包下，是宣告了 Hashtable 类死刑的类。
说实话，没看懂这个类的实现……我就先放一下 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
62
63
| final V putVal(K key, V value, boolean onlyIfAbsent) { |
if (key == null || value == null) throw new NullPointerException(); ■ key和value均不允许null，防止并发null歧义
int hash = spread(key.hashCode()); ■ hashCode的高位和低位与运算
int binCount = 0; ■ binCount:插入位置处的链表节点数
for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) { |
ConcurrentHashMap.Node<K, V> f; ■ f:插入位置的已有链表节点
int n, ■ n:数组大小
i, ■ i:坐标，哈希计算出来
fh; ■ fh:插入位置的已有链表节点的哈希值
|
if (tab == null || (n = tab.length) == 0) ■ 初始化数组（若未存储过）
tab = initTable(); |
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { ■ CAS获取数组位置，空则直接添加
if (casTabAt(tab, i, null, new ConcurrentHashMap.Node<K, V>(hash, key, value, null))) |
break; |
} else if ((fh = f.hash) == MOVED) ■ 其他线程正在进行扩容，则帮助一起扩容
tab = helpTransfer(tab, f); |
else { ■ 已有其他节点存在该位置上（哈希冲突）
V oldVal = null; |
synchronized (f) { |
if (tabAt(tab, i) == f) { ■ 再次判断取到的节点是否是头节点（考虑并发）
if (fh >= 0) { ■ 链表中加新节点
binCount = 1; |
for (ConcurrentHashMap.Node<K, V> e = f; ; ++binCount) { |
K ek; |
if (e.hash == hash && |
((ek = e.key) == key || (ek != null && key.equals(ek)))) { |
oldVal = e.val; |
if (!onlyIfAbsent) |
e.val = value; |
break; |
} |
ConcurrentHashMap.Node<K, V> pred = e; |
if ((e = e.next) == null) { |
pred.next = new ConcurrentHashMap.Node<K, V>(hash, key, |
value, null); |
break; |
} |
} |
} else if (f instanceof ConcurrentHashMap.TreeBin) { ■ 红黑树中加新节点
ConcurrentHashMap.Node<K, V> p; |
binCount = 2; |
if ((p = ((ConcurrentHashMap.TreeBin<K, V>) f).putTreeVal(hash, key, |
value)) != null) { |
oldVal = p.val; |
if (!onlyIfAbsent) |
p.val = value; |
} |
} |
} |
} |
if (binCount != 0) { |
if (binCount >= TREEIFY_THRESHOLD) ■ 链表转红黑树
treeifyBin(tab, i); |
if (oldVal != null) |
return oldVal; |
break; |
} |
} |
} |
addCount(1L, binCount); ■ CAS统计数量+1，同时考虑扩容
return null; |
} |
|
就这样吧……
总结
list
一共查看了三种 list：
ArrayList 类基于动态数组实现，默认初始容量是 10，容量不够则扩充到 1.5 倍，非线程安全。
这是最常用的类，使用时尽量指定容量大小。
Vector 类是个上古残废类，跟 ArrayList 类几乎一模一样，除了能保证线程安全，笨重。
LinkedList 类基于双向链表实现，增删快，查找慢。
map
重点看了两种新的 map，并且对 HashMap 有了更深的理解：
- LinkedHashMap 重定义了链表节点类，因此在 HashMap 的功能之外，多实现了一条双向链表，可以按照插入/访问顺序存储节点。
- HashTable 是上古版本的、在各个方法上加了 synchronized 关键字的 HashMap，能够实现多线程安全。这个类已经是个不被推荐的类了，也就没再修改过。通过这个类，能看看 HashMap 年轻时长什么样。
- ConcurrentHashMap 是 JUC 包下的线程安全的 HashMap，没看懂……