Java 容器(的插入元素方法)


一月的第二周,来补习 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
46
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() 方法可以看出:

  1. ArrayList 内部由数组实现
  2. ArrayList 的默认容量大小是 10,每次扩容时增加到原来的 1.5 倍(通过位运算实现)
  3. ArrayList 每次扩容,都会将之前保存的内容,全部复制拷贝到新数组中。
  4. 每次 ArrayList 增加元素时,会在确保容量足够的时候就增加 modCount。
  5. ArrayList 允许添加 null。

没什么用的小知识

曾经在其他博客中看到 Arrays.asList() 方法,这个方法与 ArrayList 有李逵李鬼的关系。

Arrays.asList() 方法可以将多个元素直接拼接为列表,并返回该列表,如下面这行代码:

1
List<String> list = Arrays.asList("hello", ",", "world", "!");

应当注意的是,这里得到列表是无法增加元素的,例如:

1
2
3
4
list.add("准备报错");

// 执行该语句时报错
// Exception in thread "main" java.lang.UnsupportedOperationException

现在去探索为什么会报错。看源码时发现,在 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 {

// ...构造方法、类方法如size()、get()等

}

但是这个内部定义的 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
// ArrayList的add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

// Vector的add()方法
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
// ArrayList扩容的方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量 = 原始容量 + 原始容量/2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

// Vector扩容的方法
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 输出: {1=1, 2=2, 3=2}
// LinkedHashMap 输出: {1=1, 3=3, 2=2}

分别实例化一个 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 有以下几个特征:

  1. HashMap 采用哈希算法计算存储位置,因此查找速度理论上非常快,为 O(1)。
  2. HashMap 采用数组+链表+红黑树的拉链法存储结构,正常来讲存数组,哈希冲突时存链表,链表长度超过 8 则转红黑树。
  3. 当 HashMap 的实际存储个数超过一定大小时(规则:实际个数 > 数组长度 × 负载因子,负载因子默认 0.75),数组扩容。
  4. 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); | // LinkedHashMap重写了此方法
└----------------------------------┘
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); | // LinkedHashMap重写了此方法
└----------------------------------┘
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); | // 预留给LinkedHashMap使用
└---------------------┘
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
┌----------------------------┐
| afterNodeInsertion(evict); | // 预留给LinkedHashMap使用
└----------------------------┘
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;

// 构造方法、getter方法、setter方法等等...
}

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 完全相同,另一套是一条双向链表。

这条双向链表,有两种用处(排序方式):

  1. 按照插入顺序排序,遍历时可以按照插入的顺序输出
  2. 按照访问顺序排序,遍历时按照曾经访问过的先后顺序输出(LRU 算法)

这两种排序方式都是有意义的,一个可以记录 LinkedHashMap 插入数据的顺序,另一个可以记录 LinkedHashMap 访问数据的顺序,可以用作缓存,按时间先后输出最近看过的数据。


了解了以上这些,我们回看 LinkedHashMap 的 put() 方法,也就是使用父类 HashMap 的 put() 方法时,重写的那三个方法,究竟在做些什么。

LinkedHashMap 一共重写了三个方法:

  1. newNode() 方法,用于创建链表节点
  2. afterNodeAccess() 方法,用于处理按照访问顺序排序的情况
  3. 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 // 参数1
&& (first = head) != null // 参数2
&& removeEldestEntry(first)) { // 参数3

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
    // 缓存最大100,超过100就返回false,准备删除头节点
    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:

  1. ArrayList 类基于动态数组实现,默认初始容量是 10,容量不够则扩充到 1.5 倍,非线程安全。

    这是最常用的类,使用时尽量指定容量大小。

  2. Vector 类是个上古残废类,跟 ArrayList 类几乎一模一样,除了能保证线程安全,笨重。

  3. LinkedList 类基于双向链表实现,增删快,查找慢。

map

重点看了两种新的 map,并且对 HashMap 有了更深的理解:

  1. LinkedHashMap 重定义了链表节点类,因此在 HashMap 的功能之外,多实现了一条双向链表,可以按照插入/访问顺序存储节点。
  2. HashTable 是上古版本的、在各个方法上加了 synchronized 关键字的 HashMap,能够实现多线程安全。这个类已经是个不被推荐的类了,也就没再修改过。通过这个类,能看看 HashMap 年轻时长什么样。
  3. ConcurrentHashMap 是 JUC 包下的线程安全的 HashMap,没看懂……