背景图

java中Map学习

这里写的是基于Java7的版本,java8已经改了实现的方式,主要是红黑树的实现,Entry更名为Node。

Map接口

map是一个接口, 但是在这个接口的内部也定义了一个接口Entry,用于标识映射项(键-值对)。

java8中有默认的实现和加了一些方法。

AbstractMap

此类提供 Map 接口的骨干实现,以最大限度地减少实现此接口所需的工作。

要实现不可修改的映射,编程人员只需扩展此类并提供 entrySet() 方法的实现即可,该方法将返回映射的映射关系 set 视图。通常,返回的 set 将依次在 AbstractSet 上实现。此 set 不支持 add 或 remove 方法,其迭代器也不支持 remove 方法。

这个类的设计巧妙之处就是在这个entrySet()的抽象方法。典型的模板方法模式。

这个类的内部的Entry类是SimpleEntry。

这个的类基本实现都是靠着迭代器模式,遍历entrySet来实现基础的各个功能。

我们先看一个基础的实现,不涉及具体的操作:

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 abstract Set<Entry<K,V>> entrySet();

public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}

V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}

public V put(K key, V value) {
throw new UnsupportedOperationException();
}

里面的put方法这个类没有实现,remove函数我们可以看到默认还是使用迭代器的模式实现的。感觉更像是在使用数组实现。

HashMap

默认的初始化大小为16. 最大容量为1>>30,就是2的30次方的大小吧!默认的加载因子是0.75(当然可以指定),也就是扩容的临界值等于容量的0.75。

1
2
3
4
5
6
7
8
9
10
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存放集合
transient Entry<K,V>[] table;
transient int size;
// 下一个重新扩容的阈值(默认capacity * load factor)
int threshold;
final float loadFactor;
transient int modCount;

构造函数

HashMap 包含如下几个构造器:

  • HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
  • ashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

this.loadFactor = loadFactor;
// 决定下次访问的阈值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}

我们来看一下Entry的结构

1
2
3
4
5
6
7
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}

核心方法解读

put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public V put(K key, V value) {
//其允许存放null的key和null的value,当其key为null时,调用putForNullKey方法,放入到table[0]的这个位置
if (key == null)
return putForNullKey(value);
//通过调用hash方法对key进行哈希,得到哈希之后的数值。该方法实现可以通过看源码,其目的是为了尽可能的让键值对可以分不到不同的桶中
int hash = hash(key);
//根据上一步骤中求出的hash得到在数组中是索引i
int i = indexFor(hash, table.length);
//如果i处的Entry不为null,则通过其next指针不断遍历e元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

key相同,新的值会替换旧的值并返回旧的值,如果旧的值不存在就返回null。

从上面的源代码中可以看出:当我们往 HashMap 中 put 元素的时候,先根据 key 的 hashCode 重新计算 hash 值,根据 hash 值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

还有就是put一个为null的key,这个是放在table[0]这个位置的(很重要的一个点)。

注意addEntry(hash, key, value, i)方法根据计算出的 hash 值,将 key-value 对放在数组 table 的 i 索引处。addEntry 是 HashMap 提供的一个包访问权限的方法。这个就是职责分离的一个最基本的应用,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entr
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

hash(int h)方法根据 key 的 hashCode 重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的 hash 冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//得到k的hashcode值
h ^= k.hashCode();
//进行计算
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

“模”运算的消耗还是比较大的,在 HashMap 中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

1
2
3
static int indexFor(int h, int length) {  
return h & (length-1);
}

这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而 HashMap 底层数组的长度总是 2 的 n 次方,这是 HashMap 在速度上的优化。在 HashMap 构造器中有如下代码:

1
2
3
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

这段代码保证初始化时 HashMap 的容量总是 2 的 n 次方,即底层数组的长度总是为 2 的 n 次方。

当 length 总是 2 的 n 次方时,h& (length-1)运算等价于对 length 取模,也就是 h%length,但是 & 比 % 具有更高的效率。

TreeMap

TreeMap基于红黑树实现的。查看“键”或“键值对”时,它们会被排序(次序由Comparable或Comparator决定)。TreeMap的特点在于,所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。

Comparable接口

1
2
3
public interface Comparable<T> {
public int compareTo(T o);
}

Comparamtor接口

1
2
3
4
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}

Entry结构

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
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
// 左孩子
Entry<K,V> left = null;
// 右孩子
Entry<K,V> right = null;
// 父节点
Entry<K,V> parent;
// 默认颜色是黑
boolean color = BLACK;

/**
* 根据给定的键、值、父节点构造一个节点,颜色为默认的黑色
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}

public K getKey() {return key;}
public V getValue() {return value;}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;

return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() { return key + "=" + value;}
}

继承结构

1
2
3
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

NavigableMap接口扩展的SortedMap,具有了针对给定搜索目标返回最接近匹配项的导航方法。方法lowerEntry、floorEntry、ceilingEntry和higherEntry分别返回与小于、小于等于、大于等于、大于给定键的键关联的Map.Entry对象,如果不存在这样的键,则返回null。类似地,方法lowerKey、floorKey、ceilingKey和higherKey只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的(后面会逐个介绍这些方法)。其实就是以此为方法进行分树进行操作。

SortedMap就是可排序的鼻祖接口,里面有基本的分树的接口。

TreeMap属性

1
2
3
4
5
6
7
8
// 用于保持顺序的比较器,如果为空的话使用自然顺保持Key的顺序
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root = null;
// 树中的节点数量
private transient int size = 0;
// 多次在集合类中提到了,用于举了结构行的改变次数
private transient int modCount = 0;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeMap() {
comparator = null;
}
// 构造方法二,提供指定的比较器(这个功能很赞,有木有)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 构造方法四,接收SortedMap参数,根据SortedMap的比较器维持TreeMap中的节点顺序,* 同时通过
// buildFromSorted(int size, Iterator it, java.io.ObjectInputStream str, V defaultVal)方* 法
// 将SortedMap中的内容添加到TreeMap中(其实就是通过其他的SortedMap进行初始化)
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}

put方法

ok,了解了上面的基础知识之后,我们来看看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
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
// 如果根节点为空,将传入的键值对构造成根节点(根节点没有父节点,所以传入的父节点为null)
compare(key, key); // type (and possibly null) check

root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp; // 用于记录比较结果
Entry<K,V> parent;
// split comparator and comparable paths
// 分割比较器和可比较接口的处理
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
// 注意treeMap不支持null的操作
if (key == null)
throw new NullPointerException();
// Key本身是Comparable的接口,也就是说Comparable和Comparator的区别在这个地方
// 一个是类来实现,一个是外部实现而已
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 没有找到节点的话,新建节点,并放入到树中
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 检查是否符合红黑树的规范,不符合进行调整。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

在put(K key,V value)方法的末尾调用了fixAfterInsertion(Entry<K,V> x)方法,这个方法负责在插入节点后调整树结构和着色,以满足红黑树的要求。

  • 每一个节点或者着成红色,或者着成黑色。
  • 根是黑色的。
  • 如果一个节点是红色的,那么它的子节点必须是黑色的。
  • 一个节点到一个null引用的每一条路径必须包含相同数量的黑色节点。

在看fixAfterInsertion(Entry<K,V> x)方法前先看一个红黑树的内容:红黑树不是严格的平衡二叉树,它并不严格的保证左右子树的高度差不超过1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n),所以它算是平衡树。

下面的功能和这里类似,这里我们就不再深入分析了,更多的分析请查看引用

Hashtable

和 HashMap 一样,Hashtable 也是一个散列表,它存储的内容是键值对。

1
2
3
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable

Dictionary

Dictionary类是一个抽象类,用来存储键/值对,作用和Map类相似。

给出键和值,你就可以将值存储在Dictionary对象中。一旦该值被存储,就可以通过它的键来获取它。所以和Map一样, Dictionary 也可以作为一个键/值对列表。这个Dictionary应该是过时了。

成员变量

Hashtable是通过”拉链法”实现的哈希表。它包括几个重要的成员变量:table, count, threshold, loadFactor, modCount。

  • table是一个 Entry[] 数组类型,而 Entry(在 HashMap 中有讲解过)实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
  • count 是 Hashtable 的大小,它是 Hashtable 保存的键值对的数量。
  • threshold 是 Hashtable 的阈值,用于判断是否需要调整 Hashtable 的容量。threshold 的值=”容量*加载因子”。
  • loadFactor 就是加载因子。
  • modCount 是用来实现 fail-fast 机制的。

异同

  1. 默认的初始容量是11,加载因子还是0.75,这意味着扩展的实现可能是不一样的。
  2. put不支持key为null
  3. 方法synchronized同步。

LinkedHashMap

LinkedHashMap保持了插入顺序。是什么样的结构使得LinkedHashMap具有如此特性呢?

LinkedHashMap 实现与 HashMap 的不同之处在于,LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。

实现

对于 LinkedHashMap 而言,它继承与 HashMap(public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>)、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类 HashMap 相似,它通过重写父类相关的方法,来实现自己的链接列表特性。下面我们来分析 LinkedHashMap 的源代码:

成员变量

LinkedHashMap 采用的 hash 算法和 HashMap 相同,但是它重新定义了数组中保存的元素 Entry,该 Entry 除了保存当前对象的引用外,还保存了其上一个元素 before 和下一个元素 after 的引用,从而在哈希表的基础上又构成了双向链接列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 如果为true,则按照访问顺序;如果为false,则按照插入顺序。
*/
private final boolean accessOrder;
/**
* 双向链表的表头元素。
*/
private transient Entry<K,V> header;

/**
* LinkedHashMap的Entry元素。
* 继承HashMap的Entry元素,又保存了其上一个元素before和下一个元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
}

通过源代码可以看出,在 LinkedHashMap 的构造方法中,实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组,但额外可以增加 accessOrder 这个参数,如果不设置,默认为 false,代表按照插入顺序进行迭代;当然可以显式设置为 true,代表以访问顺序进行迭代。如:

1
2
3
4
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

存储

LinkedHashMap 并未重写父类 HashMap 的 put 方法,而是重写了父类 HashMap 的 put 方法调用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现。

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
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

void addEntry(int hash, K key, V value, int bucketIndex) {
// 调用create方法,将新元素以双向链表的的形式加入到映射中。
createEntry(hash, key, value, bucketIndex);

// 删除最近最少使用元素的策略定义
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}

void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
// 调用元素的addBrefore方法,将元素加入到哈希、双向链接列表。
e.addBefore(header);
size++;
}

private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

读取

LinkedHashMap 重写了父类 HashMap 的 get 方法,实际在调用父类 getEntry() 方法取得查找的元素后,再判断当排序模式 accessOrder 为 true 时,记录访问顺序,将最新访问的元素添加到双向链表的表头,并从原来的位置删除。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。

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
public V get(Object key) {
// 调用父类HashMap的getEntry()方法,取得要查找的元素。
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 记录访问顺序。
e.recordAccess(this);
return e.value;
}

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果定义了LinkedHashMap的迭代顺序为访问顺序,
// 则删除以前位置上的元素,并将最新访问的元素添加到链表表头。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}

/**clear链表,设置header为初始状态*/
public void clear() {
super.clear();
header.before = header.after = header;
}

排序模式

LinkedHashMap 定义了排序模式 accessOrder,该属性为 boolean 型变量,对于访问顺序,为 true;对于插入顺序,则为 false。一般情况下,不必指定排序模式,其迭代顺序即为默认为插入顺序。

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个 LinkedHashMap,并打算按从近期访问最少到近期访问最多的顺序(即访问顺序)来保存元素,那么请使用下面的构造方法构造 LinkedHashMap:public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

该哈希映射的迭代顺序就是最后访问其条目的顺序,这种映射很适合构建 LRU 缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序,默认返回 false,这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素。

我们其实可以利用 LinkedHashMap 构建 LRU 缓存。

EnumMap

EnumMap是处理Enum为key的优化,没有仔细看源码,但是看到put方法时,就大概明白优化的地方在哪了!没有hash函数,使用Enum.ordinal()作为散列函数确实妙,这样没有key冲突,直接访问即可,性能会有一定提升。

1
2
3
4
5
6
7
8
9
10
11
12
public V put(K key, V value) {
// 类型检查
typeCheck(key);

// 找到枚举的索引(注意这里是利用枚举的index作为hash值,的确很好使)
int index = key.ordinal();
Object oldValue = vals[index];
vals[index] = maskNull(value);
if (oldValue == null)
size++;
return unmaskNull(oldValue);
}

这里就是简单介绍一下,具体还是查看源码的具体实现

关于fail-fast 和 fail-safe的区别

这里为了解决并发的问题,一般采用这两种机制。一般来说容器都是线程不安全的,特别是迭代器进行访问的时候特别容易出现问题。下面我们来大概解释一下这个概念。

其实就是通过版本号防止并发的问题,但是呢?光通过版本号是解决不了问题的,所以这里的这种机制是带有欺骗性的,只是会减少并发的问题,但是真正并发量大的时候,问题是解决不了的。

fail-fast就是发现版本号不对的时候抛异常,fail-safe不会抛异常,会优雅地返回错误而已。另外fail-safe是通过clone来保证访问没有问题的。下面列个表看一下:

item Fail Fast Iterator Fail Safe Iterator
Throw ConcurrentModification Exception Yes No
Clone object No Yes
Memory Overhead No Yes
Examples HashMap, Vector, ArrayList, HashSet CopyOnWriteArrayList, ConcurrentHashMap

引用

java中fail-fast 和 fail-safe的区别
JDK源码学习(2)-TreeMap源码分析
Java 集合框架
Java Dictionary 类
Hashtable 的实现原理
Java LinkedHashMap工作原理及实现

0%