Map是映射表，基本思想是键-值(对)关联，可以使用键来查找值。一般常见的Map有HashMap,LinkedHashMap,TreeMap,WeakHashMap,ConcurrentHashMap,IdentityHashMap。
HashMap不多说，最常见，非线程安全的。
LinkedHashMap取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点；而在迭代访问时反应更快，因为它使用的链表维护内部次序。
TreeMap基于红黑树的实现。查看“键”或“键值对”时，它们会被排序(次序由Comparable或者Comparator决定)。
WeakHashMap弱键(weak key)映射，允许释放映射所指向的对象。如果映射之外没有引用指向某个“键”，则此“键”对应的值可以被垃圾回收器回收。
ConcurrentHashMap一种线程安全的Map。
IdentityHashMap使用==代替equals()对“键”进行比较的散列映射。意思是key在逻辑上可以相等，但是物理地址不能相等。
要对Map更深入的理解，下面代码有助于理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class MyMap<K, V> {
private Object[][] pairs;
private int index;
public MyMap(int length) {
pairs = new Object[length][2];
}
public void put(K key, V value) {
if (index >= pairs.length) {
throw new ArrayIndexOutOfBoundsException();
}
pairs[index++] = new Object[] { key, value };
}
public V get(K key) {
for (int i = 0; i < index; i++) {
if (key.equals(pairs[i][0])) {
return (V) pairs[i][1];
}
}
return null;
}
}
|
但实际上，HashMap的实现不那么简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
|
1
2
3
4
5
6
| static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
|
HashMap的桶是用数组来定的Node<K,V>[] table，但是是根据key进行hash来确定index，即是哪个桶table[index]。每个桶内的元素是Node<K,V>，用链表来存储。也就是说如果由于hash值一样，在桶内是一个链表来存储key-value。
来看put源码：
1
2
3
| public V put(K key, V value) {
return putVal(hash(key), key, value, false, 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
35
36
37
38
39
40
41
42
| 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;
}
|
首先看table是否初始化过，之后根据hash值定位到对应的Node[]中位置，如果该位置的值不存在，直接加入新节点。如果该位置的值存在，说明该位置对应的节点有多个，则分情况讨论：1.该位置的第一个节点即要追寻的目标节点；2.该位置的节点已经退化为了红黑树（链节点的个数超过8个）；3.该位置还是单链，向后遍历寻找目标节点。
注意，这里就会存在数据覆盖的线程安全问题。
1
2
| if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
|
具体原因：假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第1行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
除此之外，还有：
还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的zise大小为10，当线程A执行到这行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。
HashMap的扩容机制resize()是比较关键的地方，一般resize()方法的调用是在这些情况：1. table第一次初始化；2. table容量不够，size > threshold；3. 当tab.length < 64, 而Hash冲突过多，linked nodes退化为tree。HashMap使用数组存储元素的，Java里的数组是无法自动扩容的，因此扩容方法是使用一个新的数组代替已有的容量小的数组。
JDK1.8中也有了改进，解决了JDK1.7中高并发时resize时的死循环（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
| final Node<K,V>[] resize() {
……
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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 {
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
扩容时使用的是2次幂的扩展，即长度扩为原来2倍，所以经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。例如：oldCap是10…00, 而newCap是oldCap的2倍，e.Hash & oldCap==0的话，e.Hash & (oldCap-1)与e.hash & (newCap -1)的值是一样。
在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看e.hash & (newCap -1)的值是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。还有一点，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，这也是死循环的原因所在。而JDK1.8则不会倒置。