java8集合框架(六)-Map的实现类(IdentityHashMap,WeakHashMap,EnumMap)

java8集合框架(六)-Map的实现类(IdentityHashMap,WeakHashMap,EnumMap)

分析完前面的四大常用Map实现类,这里继续了解一下另外三个不经常使用到的。分别是IdentityHashMap,WeakHashMap,EnumMap。我们主要了解其数据结构和使用场景,并大概描述其实现原理。

Note:本篇源码分析基于jdk1.8版本

IdentityHashMap

数据结构

IdentityHashMap的核心数据结构是数组。它没有节点类型,存储的就是Object。数组的偶数位存放key,奇数位存放value。容量为16的哈希表实际申请数组大小为32,当元素个数(11)大于数组大小(32)的三分之一时扩容。计算hash得到桶索引i,如果索引i为空,将key存进i,value存进i+1。否则循环遍历i+2,i+4…0,2,4的位置,直到索引i为空。IdentityHashMap支持nullkey和nullvalue。

1
2
3
4
5
6
//tab的偶数i索引存放key,i+1索引存放value。
transient Object[] table;
//tab索引i是否已存在元素的判断是table[i]!=null,
//而IdentityHashMap支持null作为key,所以需要包装null key
static final Object NULL_KEY = new Object();

使用说明

  • IdentityHashMap的相等是==而HashMap使用的是== || equals()
  • HashMap使用的是hashCode()查找位置,IdentityHashMap使用的是System.identityHashCode(object)
  • IdentityHashMap中key能重复。若要存放两个相同的key,key的地址不能一样
  • jdk的注释所描述,可能使用的场景1.保存代理对象2.深复制3.序列化。

WeakHashMap

数据结构

WeakHashMap的原理和老版的HashMap差不多,也是数组+链表。甚至是实现也差不多。不同的是WeakHashMap的key是弱引用。数据节点Entry继承了WeakReference,构造时需要传递存放key无外界引用的队列ReferenceQueue。每次访问hash表,expungeStaleEntries方法遍历queue清理无效的key/value。WeakHashMap支持nullkey和nullvalue。

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
//hash桶
Entry<K,V>[] table;
//不为外部引用的key队列
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
//继承了WeakReference
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next;
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
public K getKey() {...}
public V getValue() {...}
public V setValue(V newValue) {...}
public boolean equals(Object o) {...}
public int hashCode() {...}
public String toString() {...}
}
private void expungeStaleEntries() {
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;
int i = indexFor(e.hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = null; // Help GC
size--;
break;
}
prev = p;
p = next;
}
}
}
}

使用说明

  • 只有在访问的时候才会尝试去除弱引用键,如果没有访问动作,不会释放内存。
  • 弱引用的是key,value是强引用。
  • key在GC的时候被清除,value在key清除后访问WeakHashMap被清除.

EnumMap

数据结构

EnumMap的key是枚举对象,核心数据结构是数组。以枚举的顺序ordinal确定value存储在vals的索引。相比于使用HashMap<EnumType,Object>,EnumMap<EnumType,Object>的效率非常高。EnumMap不支持nullkey,支持nullvalue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//value存储的数组
private transient Object[] vals;
//Enum的类型,做类型检查时用到
private final Class<K> keyType;
//构造函数需要传入枚举类型
public EnumMap(Class<K> keyType) {
this.keyType = keyType;
keyUniverse = getKeyUniverse(keyType);
vals = new Object[keyUniverse.length];
}
public V put(K key, V value) {
typeCheck(key);
int index = key.ordinal();
Object oldValue = vals[index];
//put就是赋值,简单暴力
vals[index] = maskNull(value);
if (oldValue == null)
size++;
return unmaskNull(oldValue);
}

使用说明

  • 使用的时候一定要传入枚举类型
  • EnumMap核心数据结构是数组,性能更好,推荐在key为枚举时替代其他类型Map实现

总结

这三种Map实现类在我的开发经历中都没投入到生产环境用过。这次分析集合框架Map实现类让我有机会了解到它们。目前没有用到不代表以后也用不到,当有一天常用的Map都不能满足需求的时候,蓦然回首,可能有意想不到的惊喜。所以需要知道,了解其特点就行。

参考

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。