集合框架理解

宋正兵 on 2021-01-08

阅读博客Java 集合框架原理分析的笔记记录,挑了一些觉得重要的内容。

Java 提供的集合都在 java.utils 包下,它们的关系如下面这张类图所示:image.png

Iterator迭代器

Iterator 是一个集合上的迭代器,用于对集合进行遍历、迭代。它因为有更短的方法名字,允许调用者在遍历过程中语法正确地删除元素而替代掉了 Enumeration 类。

注意这里的 【语法正确】,事实上在使用 Iterator 对容器进行迭代的时候,如果修改容器可能会报 ConcurrentModificationException 的错误。官方称这种情况下的迭代器是 fail-fast 迭代器。

fail-fast:fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。

ConcurrentModificationException 出现的原因(fail-fast)

以 ArrayList 为例,在调用迭代器的 remove 方法时,程序抛出 ConcurrentModificationException 异常,也就是成为了 fail-fast:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
ArrayList<String> list=new ArrayList<String>();
list.add("111");
list.add("222");
list.add("333");

for(Iterator<String> iterator=list.iterator();iterator.hasNext();){
String ele=iterator.next();
if(ele.equals("111"))
list.remove("222"); // 抛出 ConcurrentModificationException 异常
}
System.out.println(list);
}

可以看到在调用迭代器遍历时,如果使用 Collection 的 remove 方法删除会造成 ConcurrentModificationException 异常。具体可以阅读这篇文章

如何解决呢?单线程的时候删除元素的时候使用迭代器的 remove 方法就可以实现正常的删除了,多线程的时候使用并发集合类。

API

方法 用途
boolean hasNext() 如果此列表迭代器在向前遍历列表时有更多元素,则返回true
E next() 返回列表中的下一个元素并前进光标位置
void remove() 从列表中删除next()返回的最新元素

ListIterator双向迭代器

ListIterator 的功能:

  • 允许我们向前、向后两个方向遍历 List;
  • 可以在遍历时修改 List 的元素;
  • 遍历时获取迭代器当前游标所在的位置。

迭代器没有当前所在元素一说,它只有一个游标(cursor)的概念,游标总是在元素之间。即长度为 N 的集合会有 N+1 个游标的位置。

image.png

ListIterator的获取

方法 用途
ListIterator listIterator() 返回此 list 中的 ListIterator 迭代器
ListIterator listIterator(int index) 返回此 list 中的 ListIterator 迭代器,起始位置为 index

API

ListIterator 继承自Iterator 接口,在 Iterator 的基础上增加了 6 个方法:

方法 用途
boolean hasPrevious() 判断游标前面是否有元素
E previous() 返回游标前面的元素,同时游标前移一位。游标前没有元素就报 java.util.NoSuchElementException 的错,所以使用前最好判断一下
int nextIndex() 返回游标后边元素的索引位置,初始为 0 ;遍历 N 个元素结束时为 N
void add(E e) 在 next() 返回的最新元素之前或者是 previous() 返回的元素之后插入元素。
void set(E e) 替换从 next() 或 previous() 返回的最新元素;注意,当没有迭代,也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错
void remove() 删除迭代器最后一次操作的元素,注意事项和 set 一样。

Collection集合

集合的概念

集合,或者叫做容器,是一个包含多个元素的对象。

集合可以对数据进行存储,检索,操作。

集合框架

集合框架是一个代表、操作集合的统一架构。所有的集合框架都包含以下几点:

  • 接口:表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现,从而达到“多态”。在面向对象变成语言中,接口通常用来形成规范。
  • 实现类:集合接口的具体实现,是重用性很高的数据结构。
  • 算法:用来根据需要对实体类中的对象进行计算,比如查找、排序。

Java集合框架主要结构图

image.png

Java 的集合主要分为 Collection 和 Map 两类。

15个核心API

方法 用途
int size() 获取元素个数
boolean isEmpty() 是否个数为 0
boolean contains(Object e) 是否包含指定元素
boolean add(E e) 添加元素,成功时返回 true
boolean remove(Object e) 删除元素,成功时返回 true
Iterator iterator() 获取迭代器
boolean containsAll(Collection<?> c) 是否包含指定集合 c 的全部元素
boolean addAll(Collection<? extends E> c) 添加集合 c 中的所有元素到本集合中,如果集合有改变就返回 true
boolean removeAll(Collection<?> c) 删除本集合中和集合 c 中一致的元素,如果集合有改变就返回 true
boolean retainAll(Collection<?> c) 保留本集合和集合 c 中共有的元素,如果集合有改变就返回 true
void clear() 删除所有元素
Object[] toArray() 返回一个包含集合中所有元素的数组
T[] toArray(T[] a) 返回一个包含集合中所有元素的数组,运行时根据集合元素的类型指定数组的类型

JDK 8 以后,Collection 接口还提供了从集合获取连续流或者并行流:

  • Stream<E> stream()
  • Stream<E> parallelStream()

点击这里了解流【待补充】

遍历Collection的方法

1、for-each语法

1
2
3
4
Collection<Person> persons = new ArrayList<Person>();
for (Person person : persons) {
System.out.println(person.name);
}

2、Iterator迭代器

1
2
3
4
5
Collection<Person> persons = new ArrayList<Person>();
Iterator iterator = persons.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}

List<E>接口

List 是一个在元素有序的(保存的顺序就是存储的顺序),可以重复的,可以为 null 的集合(有时也称为“序列”)。

Java 集合框架中最常用的几种 List 实现类是 ArrayList、LinkedList 和 Vector。在各种 List 中,最好的做法是以 ArrayList 作为默认选择。当插入、删除频繁时,使用 LinkedList。Vector 总是比 ArrayList 慢,所以要尽量避免使用它。

List接口扩展的方法

方法 用途
E get(int index) 获取指定索引上的数据
E set(int index, E element) 修改指定索引数据
ListIterator listIterator() 返回 ListIterator 接口对象
static List of(E …e) 返回包含 n 个元素的不可修改列表,n 不超过10

List、Set 和 Map 如果想要根据两个对象的内容而不是地址比较是否相等时,需要重写 equals()hashCode() 方法。remove()contains()indexOf() 等等方法都需要依赖它们。

AbstractCollection抽象类

AbstractCollection 抽象类是 Java 集合框架中 Collection 接口的一个直接实现类,Collection 下的大多数子类都继承 AbstractCollection 抽象类,比如 List 的实现类、Set 的实现类。

我们之所以可以使用 System.out.println() 直接输出集合的全部内容,而不用挨个遍历输出,全都是 AbstractCollection 中 toString() 方法的功劳。

ArrayList类

以数组实现的,遍历时很快,但插入、删除时都需要移动后面的元素,效率略差些。

ArrayList 是 Java 集合框架中 List 接口的一个实现类。它可以说是我们使用最多的 List 集合,它有以下特点:

  • 容量不固定
  • 有序(元素输出顺序与输入顺序一致)
  • 元素可以为 null
  • 效率高
    • size()、isEmpty()、get()、set()、iterator()、listIterator() 方法的时间复杂度都是 O(1)
    • 其他所有操作的时间复杂度几乎都是 O(n)
  • 占用空间更小:对比 LinkedList,不用占用额外空间维护链表结构

ArrayList 继承自 RandomAccess,RandomAccess 是一个空的接口,用来标记某个类是否支持 随机访问 (相比较于“按顺序访问”)。

ArrayList的成员变量

1、底层数据结构:数组

1
transient Object[] elementData;

由于数组类型为 Object,所以允许添加 null。初始时该数组赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

transient 说明这个数组无法序列化。

2、默认的空数组

1
2
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

默认的空数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,它与 EMPTY_ELEMENTDATA 都是空数组,区别在于第一个元素被添加进数组时如何进行扩容

  • 如果初始的空数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的话,第一个元素被添加进来后,数组 elementData 扩容到数组初始容量 DEFAULT_CAPACITY = 10
  • 如果初始的空数组是 EMPTY_ELEMENTDATA 的话,第一个元素被添加进来后,数组 elementData 扩容到容量为 size(此时size = 0) + 1 = 1

可以观察 add() 方法来理解上面的话。

3、数组的初始容量为10

1
private static final int DEFAULT_CAPACITY = 10;

4、数组中当前元素个数

1
private int size;

5、数组最大容量

1
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList的关键方法

1、构造函数

默认的无参构造,初始为空数组:

创建一个空 list,初始容量大小为 10。(创建完为空时 size 为0,当第一个元素被添加后容量大小为 10)

1
2
3
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造,根据指定容量, 创建对象数组:

当指定容量为 0 时,将用 EMPTY_ELEMENTDATA 来表示空数组,和无参构造的区别在于:第一个新元素加入后,数组进行扩容的方法不同。EMPTY_ELEMENTDATA 加入第一个新元素时数组容量加 1,具体参考 AraayList的成员变量->2、默认的空数组

1
2
3
4
5
6
7
8
9
10
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

有参构造,直接创建和指定集合一样内容的 ArrayList:

1
2
3
4
5
6
7
8
9
10
11
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

2、添加元素

每次添加前会对数组的容量进行调整

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

3、对数组容量进行调整

可以主动调用 ensureCapacity() 方法来增加 list 的容量,避免每次元素满了时每次添加都需要等待扩容的的消耗。

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
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 如果当前数组不是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,那么当前最小容量为 0
? 0
// 如果是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,那么当前最小容量为默认容量 10
: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
// 所需的最小容量大于当前最小容量,需要扩容
ensureExplicitCapacity(minCapacity);
}
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

4、扩容

默认每次扩容容量为旧容量的1.5倍。(如果是空 list,在第一个元素被添加进来后容量大小为默认容量大小 10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新的容量 = 旧的容量 + 旧的容量 / 2 = 1.5 * 旧的容量
int newCapacity = oldCapacity + (oldCapacity >> 1);

// 所需的最小容量大于旧容量的 1.5 倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;

// 新容量大于了最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

总结:ArrayList 是采取延迟分配对象数组大小空间的,当第一次添加元素时才会分配 10 个对象空间,当添加第 11 个元素的时候,会扩容 1.5 倍,当添加到 16 个元素的时候扩容为 15*1.5=22,以此类推。

Queue接口,队列

Java 集合中的 Queue 继承自 Collection 接口,Deque、LinkedList、PriorityQueue、BlockingQueue 等类都实现了它。

Queue 用来存放等待处理元素的集合,这种场景一般用于缓冲、并发访问。

额外添加的API

操作 抛出异常 返回特殊值 用途
插入 boolean add(e) boolean offer(e) 在尾部添加(建议实现类禁止添加 null 元素,只有 LinkedList 类没有遵守)
删除 E remove() E poll() 删除并返回头部
检查 E element() E peek() 获取但不删除

为什么建议禁止添加 null 元素

一般情况下 Queue 的实现类都不允许添加 null 元素,因为 poll()、peek() 方法在异常的时候会返回 null,如果你添加了 null 元素,当获取时不好分辨究竟是否正确返回。

Deque接口,双端队列

Deque 接口继承自 Queue接口,直接实现了它的类有 LinkedList、ArrayDeque、ConcurrentLinkedDeque 等。Deque 支持容量受限的双端队列,也支持大小不固定的。一般双端队列大小不确定。

20161019193301571.png

Deque 当队列用:

20161019194500774.png

Deque 当栈用:

这里写图片描述

Deque 的实现类

  • 一般场景
    • LinkedList 大小可变的链表双端队列,允许元素为 null
    • ArrayDeque 大小可变的数组双端队列,不允许元素为 null
  • 并发场景
    • LinkedBlockingDeque 如果队列为空时,获取操作将会阻塞,直到有元素添加

LinkedList类

LinkedList 继承自 AbstractSequentialList 接口,同时还实现了 Deque、Queue 接口。

以链表实现的,插入、删除时只需要改变前后两个节点指针指向即可。

LinkedList双向链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

LinkedList 的成员变量只有三个:

  • size:容量
  • first:头节点
  • last:尾节点

Node 类是一个双向节点:

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

LinkedList的方法

1、关键的几个内部方法

方法 用途
void linkFirst(E e) 插入到头部
void linkLast(E e) 插入到尾部
void linkBefore(E e, Node succ) 在指定节点 succ 前插入一个元素,假设 succ 不为 null
E unlinkFirst(Node f) 删除头节点并返回该节点上的数据,假设不为 null
E unlinkLast(Node l) 删除尾部节点并返回该节点上的数据,假设不为 null
E unlink(Node x) 删除某个指定节点
Node node(int index) 获取指定位置的节点

头部添加删除

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
// 插入到头部
private void linkFirst(E e) {
// 记录头节点
final Node<E> f = first;
// 新建一个节点,尾部指向之前的头节点 first
final Node<E> newNode = new Node<>(null, e, f);
// first 指向新的节点
first = newNode;
if (f == null)
// 如果新建的是空链表,新建的节点也是最后一个节点
last = newNode;
else
// 原来的第一个节点的头部指向新建的节点
f.prev = newNode;
size++;
modCount++;
}

// 删除头节点并返回该节点上的数据,假设不为 null
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

尾部添加删除

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
// 插入到尾部
void linkLast(E e) {
// 记录尾节点
final Node<E> l = last;
// 新建一个节点,头部指向之前的尾节点 last
final Node<E> newNode = new Node<>(l, e, null);
// last 指向新的节点
last = newNode;
if (l == null)
// 如果之前是空链表,新节点也是第一个节点
first = newNode;
else
// 原来的尾节点尾部指向新的尾节点
l.next = newNode;
size++;
modCount++;
}

// 删除尾部节点并返回,假设不会 null
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}

获取指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 获取指定位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
// 二分,如果小于 size 的一半,从头开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

指定节点的添加删除

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
// 在指定节点(不为 null)前插入一个元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
// 新建一个尾节点,头部指向 succ 前面的节点,尾部指向 succ 节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 让 succ 的头部指向新节点
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

// 删除某个指定节点
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

2、常用的 API

添加方法

方法 用途
boolean add(E e) 在尾部添加元素
void add(int index, E e) 在指定位置添加元素
boolean addAll(Collection<? extends E> c) 添加一个集合的元素
boolean addAll(int index, Collection<? extends E> c) 从指定的位置,添加一个集合的元素
void addFirst(E e) 在头部添加元素
void addLast(E e) 在尾部添加元素

删除方法

方法 用途
E remove() 删除头部节点
E remove(int index) 删除指定位置节点
boolean remove(Object o) 删除包含指定元素的节点(遍历)
E removeFirst() 删除头部节点
E removeLset() 删除尾部节点
boolean removeFirstOccurrence(Object o) 删除首次出现的指定元素(从头节点开始遍历)
boolean removeLastOccurrence(Object o) 删除最后一次出现的指定元素(从尾部节点开始遍历)
void clear 清除全部元素

修改方法

方法 用途
E set(int index, E e) 修改指定位置的元素

查询方法

方法 用途
int indexOf(Object o) 获取指定元素第一次出现的位置
int lastIndexOf(Object o) 获取指定元素最后一次出现的位置(倒着遍历)
boolean contains(Object o) 是否包含指定元素
E get(int index) 获取指定位置的元素
E getFirst() 获取第一个元素
E poll() 获取第一个元素,同时删除它
E peek() 获取第一个元素
E peekFirst() 获取第一个元素
E getLast() 获取最后一个元素
E peekLast() 获取最后一个元素

ArrayList和LinkedList的比较

ArrayList:

  • 基于数组,在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);
  • 但是添加、删除时该元素后面的所有元素都要移动,所以添加/删除数据效率不高;
  • 长度不够时,默认扩容为旧容量的 1.5 倍,这个操作比较影响效率。

LinkedList:

  • 基于双端链表,添加/删除元素只会影响周围的两个节点,开销很低;
  • 只能顺序遍历,无法按照索引获得元素,因此查询效率不高;
  • 没有固定容量,不需要扩容;
  • 需要更多的内存,LinkedList 每个节点中需要多存储前后节点的信息,占用空间更多些。

Vector类

Vector 类被认为是线程安全的 ArrayList,和 ArrayList 一样也是继承自 AbstractList。它是 Stack 的父类。

成员变量

1、底层也是个数组

1
protected Object[] elementData;

2、数组元素个数

1
protected int elementCount;

3、扩容时增长数量

允许用户自己设置,如果这个值为 0 或者负数,扩容时会扩大 2 倍,而不是 1.5 倍。

1
protected int capacityIncrement;

Vector特点

  • 底层由一个可以增长的数组组成
  • Vector 通过 capacity 和 capacityIncrement 来尽量少的占用空间
  • 扩容时默认扩大两倍
  • 最好在插入大量元素前增加 vector 的容量,以减少重新申请内存的次数
  • 同步类,每个方法前都有同步锁 synchronized

Vector和ArrayList的比较

共同点:

  • 都是基于数组的
  • 都支持随机访问
  • 默认容量都是 10
  • 都有扩容机制

区别:

  • Vector(JDK 1.0) 早于 ArrayList (JDK 1.2)出现
  • Vector 比 ArrayList 多一种迭代器 Enumeration(该迭代器不是 fail-fast 的)
  • Vector 是线程安全的,ArrayList 不是
  • Vector 默认扩容 2 倍,ArrayList 是 1.5 倍

Stack栈

Stack 集成自 Vector,是由数组实现的栈。

Stack的方法

方法 用途
Stack() 构建一个空栈
E push(E item) 入栈,调用的是 Vector.addElemnt()
synchronized E peek() 获取顶端元素,但不删除,调用的是 Vector.elementAt()
synchronized E pop() 出栈,调用 Vector.removeElementAt() 删除顶端元素
synchronized int search(Object o) 查找元素是否在栈中,返回栈顶到该元素出现的位置的距离
boolean empty() 栈是否为空

Map接口

Map 接口是和 Collection 接口同一等级的集合根接口,它表示一个键值对(key-value)的映射。

Map 中元素的顺序取决于迭代器迭代时的顺序,有的实现类保证了元素输入输出时的顺序(TreeMap),有的实现类则是无序的(HashMap)。

视图

Map 接口提供了三个角度来分析 Map:

  • KeySet——Set
  • Values——Collection
  • Entry——Set

KeySet

KeySet 是一个 Map 中键(Key)的集合,以 Set 的形式保存,不允许重复,因此键存储的对象需要重写 equals() 和 hashCode() 方法。

可以通过 Map.keySet() 方法获得。

Values

Values 是一个 Mao 中值(value)的集合,以 Collection 的形式保存,因此可以重复。

通过 Map.values() 方法获得。

Entry

Entry 是 Map 接口中的静态内部接口,表示一个键值对的映射。

Entry的方法

方法 用途
K getKey() 获取这组映射中的键 key
V getValue() 获取这组映射中的值 value
V setValue() 修改这组映射中的值
int hashCode() 返回这个 Entry 的哈希值
boolean equals() 对比 key-value 是否相等

通过 Map.entrySet() 方法获得的是一组 Entry 集合,保存在 Set 中,所以 Map 中的 Entry 也不能重复。

Map的三种遍历方式

根据 Map 提供的三种视图,可以由三种遍历方式。

1、使用 KeySet 遍历

1
2
3
4
Set set = map.keySet();
for (Object key : set) {
System.out.println(map.get(key));
}

2、使用 Values 遍历

1
2
3
4
5
Collection values = map.values();
Iterator iterator = values.iterator();
while (iterator.hasNext()) {
System.out.println("value" + iterator.next());
}

3、使用 Entry 遍历

1
2
3
4
5
6
Set entrySet = map.entrySet();
for (Object o : entrySet) {
Map.Entry entry = (Map.Entry) o;
System.out.println(entry); // key = value
System.out.println(entry.getKey() + "/" + entry.getValue());
}

Map的实现类

image.png

Map 的实现类主要有 4 种:

  • Hashtable:古老,线程安全
  • HashMap:速度很快,但没有顺序
  • TreeMap:有序的,效率比 HashMap 慢
  • LinkedHashMap:结合 HashMap 和 TreeMap 的优点,有序的同时效率也不错,仅比 HashMap 慢一点。

可以使用 Map 作为 Map 的值,但禁止使用 Map 作为 Map 的键。因为复杂的 Map 中 equals() 和 hashCode() 方法比较难定义。

HashMap

HashMap 是一个采用哈希表实现的键值对集合,底层实现是数组 + 链表。

HashMap的特点:

  • 底层实现是链表数组,JDK 8 之后加了红黑树
  • 实现了 Map 的全部方法
  • key 用 Set 存放,所以想做到 key 不允许重复,key 对应的类需要重写 equals() 和 hashCode() 方法
  • 允许空键和空值(但空键只有一个,且放在第一位)
  • 元素是无序的,而且顺序会不定时改变
  • 插入、获取的时间复杂度基本是 O(1)(有个前提是有适当的哈希函数,让元素分布在均匀的位置)
  • 遍历整个 Map 需要的时间与桶(数组)的长度成正比(因此初始化时 HashMap 的容量不宜太大)
  • 两个关键因子:初始容量、加载因子

HashMap的成员变量

1、默认初始容量:16,必须是 2 的整数次方,原因点击这里

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2、默认的加载因子的大小:0.75(该大小是结合时间和空间效率考虑得到的)

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

3、最大容量:$2^{30}$

1
static final int MAXIMUM_CAPACITY = 1 << 30;

4、当前 HashMap 修改的次数,这个变量用来保证 fail-fast 机制

1
transient int modCount;

5、阈值、下次需要扩容时的值,等于 容量 * 加载因子

1
int threshold;

6、树形阈值:JDK 1.8 新增的,当容量超过 8 之后,使用树而不是链表来作为桶,必须大于 2

1
static final int TREEIFY_THRESHOLD = 8;

7、非树形阈值:JDK 1.8 新增的,扩容时如果发现桶中长度小于 6 ,则会由树重写退化为链表

1
static final int UNTREEIFY_THRESHOLD = 6;

8、树形最小容量:当 HashMap 的容量大于该值时,才允许树形化链表(即将链表转换成红黑树),否则若桶内元素太多时则直接进行扩容。(为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD)

1
static final int MIN_TREEIFY_CAPACITY = 64;

当桶中的数量小于 TREEIFY_THRESHOLD 时不会转换成树形结构存储;如果桶中的数量大于 TREEIFY_THRESHOLD,但 capacity 小于 MIN_TREEIFY_CAPACITY 则依然使用单链表结构进行存储,此时会对 HashMap 进行扩容;如果 capacity 大于了 MIN_TREEIFY_CAPACITY 则会进行树化。

9、缓存的键值对集合(另外两个视图:KeySet 和 Values 在 AbstractMap 中声明的)

1
transient Set<Map.Entry<K,V>> entrySet;

10、哈希表中的链表数组

1
transient Node<K,V>[] table;

11、键值对的数量

1
transient int size;

12、哈希表的加载因子

1
final float loadFactor;

HashMap的初始容量和加载因子

由于 HashMap 扩容开销很大(需要创建新数组、重新分配哈希、分配等等),因此与扩容相关的两个因素:

  • 容量:数组的容量
  • 加载因子:决定了 HashMap 中的元素占有多少比例时扩容

HashMap 的默认加载因子为 0.75,这是在时间、空间两方面均衡考虑下的结果:

  • 加载因子太大的话发生冲突的可能就会变大,查找的效率反而低
  • 太小的话频繁 rehash,导致性能降低

当设置初始容量时,需要提前考虑 Map 中可能有多少对键值对,设计合理的加载因子,尽可能避免进行扩容。

如果存储的键值对很多,干脆直接设置一个大点的容量,这样可以少扩容几次。

阈值 = 容量 * 加载因子

HashMap 中的链表节点

HashMap 的底层数据结构之一(JDK 1.8 之前单纯是)是链表数组:

1
transient Node<K,V>[] table;

每一个链表节点如下:

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
static class Node<K,V> implements Map.Entry<K,V> {
// 哈希值,即位置
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个节点的指针
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
// Map.Entry 相等的条件:键相等、值相等
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

▲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
// 添加指定的键值对到 Map 中,如果已经存在则替换
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

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 {
// 如果要插入的桶已经有元素,那么用 e 指向被替换的元素
Node<K,V> e; K k;
// 此时 p 是桶中的第一个元素,如果 p 的 hash、key 和要插入的元素相同
// 那么用 e 指向 p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果不同,且 p 是 JDK 1.8 之后的树形节点,那么调用 putTreeVal() 函数进行插入
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 ,则需要将桶进行树形化
// 这里大于等于 7 是因为 binCount 从 0 开始计数的
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到了则停止,e 已经指向了要被替换的元素
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;
}

根据代码总结插入逻辑:

  1. 调用 hash() 方法计算键 key 所对应的哈希值
  2. 调用 putVal() 方法根据哈希值进行相关操作
  3. 如果当前的哈希表内容为空,新建一个哈希表
  4. 如果要插入的桶中没有元素,新建一个节点并放入桶中
  5. 否则从桶中第一个元素开始查找哈希值对应位置
    1. 如果桶中第一个元素的哈希值和要添加元素的哈希值一样,替换,结束查找
    2. 如果桶中第一个元素的哈希值和要添加元素的哈希值不一样,而且当前采用的是 JDK 8 以后的树形节点,则调用 putTreeVal() 进行插入
    3. 否则还是用传统的链表遍历方法进行查找、替换,结束查找
    4. 当这个桶中元素个数大于等于 8 时,调用 treeifyBin() 方法进行树形化
  6. 检查是否需要扩容

插入过程中的几个关键的其他方法:

  • hash():计算键 key 在哈希表中对应的位置
  • resize():扩容
  • putTreeVal():树形节点的插入
  • treeifyBin():对桶进行树形化

▲HashMap中的哈希函数hash()

HashMap 中通过把传入键的 hashCode 和 hashCode 无符号右移 16 位得到的结果进行按位异或,得到这个键的哈希值。

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

由于哈希表的容量都是 2 的 N 次方,元素的 hashCode() 在很多时候下低位(二进制下)是相同的,这将容易导致冲突(碰撞),因此 JDK 1.8 之后添加了一个位移操作:将元素的 hashCode() 和自己无符号右移 16 位后的结果求异或。为什么这样实现 hash()

这样可以避免只靠低位数据来计算哈希时容易导致冲突,计算结果由高低位结合决定,可以避免哈希值分布不均匀。且采用位运算效率更高。

▲HashMap中的初始化/扩容方法resize()

HashMap 每次添加时会比较当前元素个数和阈值,如果超出阈值就需要进行扩容:

1
2
if (++size > threshold)
resize();

扩容

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量 = 旧容量 * 2
// 新的阈值 = 旧阈值 * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 旧容量为 0 且 旧阈值大于 0,说明之前创建了哈希表但是没有添加元素
// 那么初始化容量为阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 旧容量、旧阈值都是 0,说明还没创建哈希表,容量为默认容量 16,阈值为 容量*加载因子
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新阈值为 0 ,需要用 新容量*加载因子 重新算一遍
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值
threshold = newThr;
// 创建新的哈希表,容量为原来容量的两倍
// 如果之前没有创建哈希表,那么容量为默认容量 16
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果旧哈希表中有数据,则进行遍历复制
// 根据位运算的结果把通中的链表分为了低位和高位两个链表,然后分别塞到桶 newTab[j] 和 newTab[j + oldCap] 中
// 低位链表存放在扩容之后的下标位置,与当前数组的下标位置一致
// 高位链存放在当前数组下标位置+扩容之前的数组长度
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 旧的桶不为空,用 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) {
// 如果低位尾节点为 null 的话,说明还没开始遍历这个桶下的链表,就把 e 赋值给低位首节点
if (loTail == null)
loHead = e;
// 否则低位尾节点不为 null 的话,说明已经在遍历了
else
loTail.next = e;
loTail = e;
}
// 如果 e 节点的 hash 值对 oldCap 取余不等于 0,说明这个节点是下标 0 之外的数组节点
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 如果低位尾节点不为 null
if (loTail != null) {
loTail.next = null;
// 就把首节点赋值给新数组下标为 j 的桶,和旧数组的位置是一样的
// 也就是说节点原来对应在旧数组的哪个下标,在新数组也不变。
// 这里说点抽象的,把首节点赋值给新数组的桶,其实不单单只是首节点,因为每个节点都会有指针指向后继节点
// 所以其实可以想成是直接拉了一个链表到这个数组的某个桶里了。
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 就把首节点赋值给新数组下标为[j+oldCap]的桶,和旧数组的位置j相比,这里多偏移了旧数组长度oldCap个位置,变成了[j+oldCap]
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

扩容过程中的几个关键的点:

  • 新初始化哈希表时,容量为默认容量 16,阈值为 容量*加载因子

  • 已有哈希表时去扩容,容量、阈值均为原来的 2 倍

  • 如果旧哈希表中有数据,则进行遍历复制

    • 第一种情况:如果旧桶只有一个元素,那么直接在新的桶的对应位置赋值
    • 第二种情况:如果之前这个桶的节点类型是树形节点,则需要把新哈希表里的当前桶也变成树形结构,调用 split() 做扩容
    • 第三种情况:桶中已经形成链表,那么将原链表拆分成低位链表和高位链表,低位链表存放在扩容之后的原下标位置,高位链表存放在当前数组下标+扩容之前的数组长度

    判断是属于低位链表还是高位链表的方法:e.hash & oldCap,结果为 0 就是低位链表中的节点,结果为 1 就是高位链表中的节点

先略过红黑树的情况,描述下简单流程,在 JDK 1.8 中发生 hashmap 扩容时,遍历 hashmap 每个桶里的链表,每个链表可能会被拆分成两个链表,不需要移动的元素置入 loHead 为首的链表,需要移动的元素置入 hiHead 为首的链表,然后分别分配给老的桶和新桶。

JDK 1.8 没有再像之前一样再重新 rehash 了,效率自然是提高了很多。

HashMap的获取方法get()

V get(K key) 方法返回键对应的值

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
public V get(Object key) {
Node<K,V> e;
// 先计算哈希值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// tab 指向哈希表,n 为哈希表的长度,first 指向哈希表的 [(n - 1) & hash] 处桶的第一个元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查第一个元素是否是我们要查找的元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 第一个元素不是我们要找的元素,且桶中还有其他元素
if ((e = first.next) != null) {
// 如果是桶中元素是树形节点,那么调用 getTreeNode() 函数进行查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 遍历桶中元素进行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

查找的步骤:

  • 计算哈希值
  • (n - 1) & hash 计算出桶在哈希表中的位置
  • 在桶中遍历进行查找

时间复杂度一般跟桶中的元素多少有关,因此哈希算法越好,元素分布越均匀,get() 方法就越快。

但是在 JDK 1.8 之后 HashMap 新增了红黑树节点,优化了极端情况(所有元素都在一个桶中,一个链表中)下的性能。

总结

  1. HashMap 的缺点是:不是同步的,多线程并发访问一个哈希表时需要在外部进行同步操作,否则会引发数据不同步问题,也可以选择加锁。

  2. HashMap 的三个视图返回的迭代器都是 fail-fast 的:如果在迭代时使用了非迭代器方法修改了 map 的内容、结构,迭代器就会报 ConcurrentModificationException 的错。

  3. 当 HashMap 中有大量元素都存放到一个桶中时,这时哈希表中只有一个桶,这个桶下边有一条很长的链表,此时的 HashMap 就相当于一个单链表。假设此时 HashMap 中有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。

    针对这种情况,JDK 1.8 引入了红黑树(时间复杂度为)(logn))来优化这个问题。

  4. 为什么哈希表的容量一定要是 2 的整数次幂

    1. capacity 为 2 的整数次幂,计算桶的位置 (length - 1) & hash 就相当于 hashlength 取模,提升了计算效率;
    2. capacity 为 2 的整数次幂的话,capacity 为偶数,capacity - 1 为奇数,奇数的最后一位是 1,那么 (length - 1) & hash 的最后一位可能为 0 也可能为 1(这取决于 hash 的值),即按位与操作后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性;
    3. 如果 capacity 是奇数的话,capacity - 1 为偶数,它的最后一位是 0,这样 (length - 1) & hash 的最后一位肯定是 0,即只能为偶数,这样任何 hash 值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间。
  5. HashMap 允许 key、value 为 null,同时 key 为 null 的元素都保存在第一个桶中。

    1
    2
    3
    4
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    计算哈希值时,如果为 null 就直接返回 0,说明了这一点。

  6. HashMap 中 equals() 和 hashCode() 的作用:

    1. 当 HashMap 进行添加、获取时需要通过 key 的 hashCode() 方法进行 hash() 操作,然后计算下下标 (n - 1) & hash),从而获得要找的桶的位置。
    2. 当发生冲突(碰撞)时,利用 key.equals() 方法去桶(链表或树)中查找对应的节点。
  7. hash 为什么要这样实现?

    在 JDK 1.8 的实现中,是通过hashCode() 的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16)

    主要是从速度、功效、质量 来考虑的,这么做可以在桶的 n 比较小的时候,保证高低 bit 都参与到 hash 的计算中,同时位运算不会有太大的开销。

HashMap在JDK1.8后新增的红黑树结构

传统HashMap的缺点

在 JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百的均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表中有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了 HashMap 的优势。

针对这种情况,JDK 1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。

红黑树

红黑树学习资料:

在 JDK 1.8 的 HashMap 中除了链表节点 Node 之外,还有一种节点:TreeNode,它是 JDK 1.8 新增的,属于数据结构中的红黑树。

1
2
3
4
5
6
7
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}

它继承自 LinkedHashMap.Entry,而 LinkedHashMap.Entry 继承自 HashMap.Node,因此还有额外的 6 个属性:

1
2
3
4
5
6
7
8
// 继承自linkedHashMap.Entry 的属性
Entry<K, V> before, after;

// 继承自HashMap.Node 的属性
final int hash;
final K key;
V value;
Node<K,V> next;

HashMap中关于红黑树的三个关键参数

1、TREEIFY_THRESHOLD

1
static final int TREEIFY_THRESHOLD = 8;

一个桶的树化阈值,当桶中的元素超过这个值时,需要使用红黑树节点替换链表节点。这个值为 8,是从转换效率考虑的。

2、UNTREEIFY_THRESHOLD

1
static final int UNTREEIFY_THRESHOLD = 6;

一个树的链表还原阈值,当扩容时,桶中的元素个数小于这个值,就会把树形的桶元素还原(切分)为链表结构。这个值应该比树化阈值 TREEIFY_THRESHOLD 小,至少为 6,避免频繁转换。

3、MIN_TREEIFY_CAPACITY

1
static final int MIN_TREEIFY_CAPACITY = 64;

哈希表的最小树形化容量,当哈希表中的容量大于这个值时,表中的桶才能进行树形化,否则桶内元素大于树化阈值 TREEIFY_THRESHOLD 时会进行扩容,而不是树形化。为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD。

桶的树形化操作treeifyBin()

在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8),就使用红黑树来替换链表,从而提高速度。

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
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果当前哈希表为空,或者哈希表的容量小于最小树形化容量(默认为 64),就去新建/扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 如果哈希表的容量超过了最小树形化容量,进行树形化
// e 指向哈希表中指定桶中的第一个节点
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 新建一个树形节点,内容和当前链表节点 e 一致
TreeNode<K,V> p = replacementTreeNode(e, null);
// 确定树头节点
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 让桶的第一个元素指向新建的红黑树的头结点(根结点),以后这个桶里的元素就是红黑树而不是链表了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}

上述操作做了:

  • 根据哈希表中元素个数,确定是扩容还是树形化
  • 如果是树形化
    • 遍历桶中的元素,创建相同个数的树形节点,复制内容,建立联系
    • 然后让桶中第一个元素指向新建的树头节点(根节点),替换桶的链表内容为树形内容

但是我们发现,上述的操作并没有设置红黑树的颜色值,现在只能算得到了一个二叉树。在最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树。

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
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// x 指向红黑树的根节点(桶中第一个元素),因为是 hd.treeif(tab) 这样调用的
// 第一层循环遍历当前桶中所有元素,将这些元素插入到红黑树当中
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 第一次进入循环,确定根节点,颜色为黑色
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 第二层循环遍历红黑树,确定当前 x 节点插入到红黑树中的位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 确定 dir,dir 表示 x 应该处于当前节点的左子树还是右子树
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 如果 hash 相等
else if (
// 如果没实现 Comparable 接口,通过特殊的方法给个结果
(kc == null && (kc = comparableClassFor(k)) == null) ||
// 如果实现了 Comparable 接口,那么用 Comparable 接口比较键 key
(dir = compareComparables(kc, k, pk)) == 0)
// 虽然 hash 相等,但是键没有实现 Comparable 接口无法比较,所以只能用特殊的方法给个结果
dir = tieBreakOrder(k, pk);

TreeNode<K,V> xp = p;
// 如果 p 的左子树或者右子树为空,则把 p 节点当作是 x 节点的父亲节点
// 并根据 dir 的大小确定 x 节点为 p 节点的左子树还是右子树
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 平衡红黑树
root = balanceInsertion(root, x);
break;
}
}
}
}
// 确保 root 节点是桶中的第一个节点
moveRootToFront(tab, root);
}

// 这个方法用于 a 和 b 哈希值相同但是无法比较时,直接根据两个引用的地址进行比较
// 这里源码注释也说了,这个树里不要求完全有序,只要插入时使用相同的规则保持平衡即可
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}

这里有个双重循环,拿树中的所有节点和当前节点的哈希值进行对比(如果哈希值相等,就对比键),然后根据比较结果确定在树中的位置。

总结 treeifyBin() 的操作:

  • 根据哈希表中元素个数,确定是扩容还是树形化
  • 如果是树形化
    • 遍历桶中的元素,创建相同个数的树形节点,复制内容,建立联系(确定前后关系)
    • 让桶中第一个元素指向新建的树头节点(根节点),替换桶的链表内容为树形内容
    • 调用 treeify() 函数,遍历桶中所有元素,依次插入,塑造红黑树

红黑树中添加元素putTreeVal()

在添加元素时,如果一个桶已经是红黑树结构,就要调用 putTreeVal() 方法。

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
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
// 寻找插入的位置
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 根据 hash 判断插入的位置在当前节点的左边还是右边
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 如果当前节点 p 和节点 x 的 hash 相等,但键却不是同一个类
// 在 p 的左右子树中去寻找
else if (// 如果没实现 Comparable 接口,通过特殊的方法给个结果
(kc == null && (kc = comparableClassFor(k)) == null) ||
// 如果实现了 Comparable 接口,那么用 Comparable 接口比较键 key
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
//如果从 ch 所在子树中可以找到要添加的节点,就直接返回
return q;
}
// 走到这里就说明,遍历了所有子节点也没有找到和当前键equals相等的节点,必须进行插入操作
// 虽然 hash 相等,但是键没有实现 Comparable 接口无法比较,所以只能用特殊的方法给个结果
dir = tieBreakOrder(k, pk);
}

TreeNode<K,V> xp = p;
// 如果恰好要添加的方向上的子节点为空,此时节点p已经指向了这个空的子节点
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 平衡红黑树,且确保根节点是桶中的第一个元素
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}

//这个方法用于 a 和 b 哈希值相同但是无法比较时,直接根据两个引用的地址进行比较
//这里源码注释也说了,这个树里不要求完全有序,只要插入时使用相同的规则保持平衡即可
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}

通过上面的代码知道,HashMap 中往红黑树添加一个新的节点时有以下操作:

  • 从红黑树的根节点开始寻找,如果目标键的哈希值小于当前节点键的哈希值,那么到左子树寻找;如果大于当前节点键的哈希值,到右子树寻找;如果找到键的哈希值相同且键 equals 相等的节点 p,那么直接返回节点 p。

  • 如果键的哈希值相同,但是键并不是 equals 相等,进而通过 Comparable 接口进行比较,如果比较的结果还是相等,则在左右子树递归的寻找是否有与要插入的元素的 key equals 相等的元素。如果有那么直接返回,如果没有就只能通过特殊的方法给个结果。

    (也就是说,没有实现 Comparable 接口,大小由 tieBreakOrder() 函数判定,如果实现了,则由 Comparable 接口的比较方法判定)

  • 如果遍历完所有的节点都没有找到哈希值和键 equals 相等的节点,就需要插入该新节点。

  • 插入完成后,需要重新平衡红黑树,且确保根节点是桶中的第一个元素。

红黑树中查找元素getTreeNode()

HashMap 的查找方法是 get(),它通过计算指定 key 的哈希值后,调用内部方法 getNode(),该方法根据 (n-1) & hash 得到 key 所在的桶的头结点,判断头结点是否为所要查找的元素,如果不是且桶中节点类型是红黑树节点,就需要调用红黑树节点的 getTreeNode() 方法,否则就遍历链表中的节点。

1
2
3
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}

getTreeNode() 方法通过调用树形节点的 find() 方法进行查找:

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
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null || (kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}

由于之前添加时已经保证这个红黑树是有序的,因此查找时效率很高(相当于折半查找)。

树形结构修剪split()

在 HashMap 中,resize() 方法的作用是初始化或者扩容哈希表。当扩容时,如果当前桶中元素的结构是红黑树,就会把桶中的树形结构缩小,并且判断元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD(默认为 6),若小于则直接还原(切分)为链表,调用的就是 split():

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
// ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 将树形结构拆分为两个小红黑树,如果太小就还原成链表
// map:当前hashMap对象、tab:新数组、index:正在遍历的旧数组下标、bit:旧数组的长度
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 区分树链表的高低位
if ((e.hash & bit) == 0) {
// 低位尾部标记为 null,表示还未开始处理
// 此时 e 是第一个要处理的低位树链表节点
if ((e.prev = loTail) == null)
// 低位树链表的第一个树链表节点
loHead = e;
else
loTail.next = e;
loTail = e;
// 低位树链表元素个数计数
++lc;
}
else {
if ((e.prev = hiTail) == null)
// 高位树链表的第一个树链表节点
hiHead = e;
else
hiTail.next = e;
hiTail = e;
// 高位树链表元素个数计数
++hc;
}
}
// 如果低位树链表头节点不为 null,说明链表存在
if (loHead != null) {
// 如果低位树链表中的元素小于等于链表还原阈值 6
if (lc <= UNTREEIFY_THRESHOLD)
// 去树化操作(将 TreeNode 节点都转换成 Node 节点)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
// 若高位树链表头节点不为空,说明还没有处理完高位,还不能进行树形化操作
if (hiHead != null) // (else is already treeified)
// 低位树链表的元素个数大于 6 且高位树链表的头节点不为 null
// 将低位树链表真正树化成红黑树(前面都只是挂着 TreeNode 的名号,但实际只是链表结构,还没包含红黑树的特性,这里才赋予了它红黑树的特性)
loHead.treeify(tab);
}
}
// 高位树链表不为 null,同上
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}

从上述代码可以看到,HashMap 扩容时对红黑树节点的修建主要分两部分,先分类,再根据元素个数决定是还原成链表还是精简一下元素仍然保留红黑树结构。

  1. 分类

    指定位置、指定范围,让指定位置中 (hash & bit) == 0 的放到低位树链表中,(hash & bit) == 1 的放到高位树链表中。

  2. 根据元素个数决定处理情况

    树链表中的元素个数小于树的链表还原阈值 6 时,将树还原成链表;在元素个数大于 6 时,还是用红黑树。

    其中低位树链表存放在当前桶所在的下标,高位树链表存放在当前桶所在的下标 + 扩容之前的数组长度。

总结

JDK 1.8 以后哈希表的添加、删除、查找、扩容方法都增加了一种 节点为 TreeNode 的情况:

  • 添加时,当桶中链表个数超过 8 且哈希表中的元素超过了最小树形化容量时,会被转换成红黑树;
  • 删除、扩容时,如果桶中结构为红黑树,并且树中元素个数小于 6 时,会进行去树化操作,还原成链表;
  • 查找时即使哈希函数不优,大量元素集中在一个桶中,由于有红黑树结构,性能也不会差。

image.png