Java的编程过程中经常会和Map打交道，现在我们来一起了解一下Map的底层实现，其中的思想结构对我们平时接口设计和编程也有一定借鉴作用。(以下接口分析都是以jdk1.8源码为参考依据)
1. Map
An object that maps keys to values. A map cannot contain duplicate keys;
each key can map to at most one value.
Map提供三种访问数据的方式： 键值集、数据集、数据-映射，对应下表中的标记为黄色的三个接口。public interface Map<K, V>
| 方法名 | 描述 |
| void clear() | 从此映射中移除所有映射关系（可选操作）。 |
| boolean containsKey(Object key) | 如果此映射包含指定键的映射关系，则返回 true。 |
| boolean containsValue(Object value) | 如果此映射将一个或多个键映射到指定值，则返回 true。 |
| Set<Map.Entry<K,V>> entrySet() | 返回此映射中包含的映射关系的 Set 视图。 |
| boolean equals(Object o) | 比较指定的对象与此映射是否相等。 |
| V get(Object key) | 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 |
| int hashCode() | 返回此映射的哈希码值。 |
| boolean isEmpty() | 如果此映射未包含键-值映射关系，则返回 true。 |
| Set<K> keySet() | 返回此映射中包含的键的 Set 视图。 |
| V put(K key, V value) | 将指定的值与此映射中的指定键关联（可选操作）。 |
| void putAll(Map<? extends K,? extends V> m) | 从指定映射中将所有映射关系复制到此映射中（可选操作）。 |
| V remove(Object key) | 如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 |
| int size() | 返回此映射中的键-值映射关系数。 |
| Collection<V> values() | 返回此映射中包含的值的 Collection 视图。 |
在Java8中的Map有增添了一些新的接口不在上述表格之中，这里不一一列举。
这里涉及到一个静态内部接口：Map.Entry<K,V> ，用于存储一个键值对，该接口中设置set和get键值和value值的接口。
所以Map中存储数据都是以这种Entry为数据单元存储的。
2. AbatractMap
AbstractMap中增加了两个非常重要的成员变量：
transient Set<K> keySet;
transient Collection<V> values;
通过这两个成员变量，我们已经知道Map是如何存储数据的了：键值存入keySet中，value存入values中。（由于Map需要保证键值的唯一性所以选择Set作为键值的存储结构，而Value则对此没有任何要求所以选择Collection作为存储结构）
AbstractMap实现了Map中的部分接口，都是通过调用接口：Set<Entry<K,V>> entrySet() 实现的，而该接口的具体实现却留给了具体的子类。以下代码列出了equal()方法的具体实现：
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) o;
if (m.size() != size())
return false;
try {
Iterator<Entry<K,V>> i =
entrySet().
iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
3. HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable除了继承了AbstractMap中HashMap中的两个成员变量以外，又增加了如下几个成员变量：transient Set<Map.Entry<K,V>> entrySet;transient Node<K,V>[] table;transient int size;transient int modCount;作为table存储的基本类型，Node类的源码如下：
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<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
建议看HashMap源码前了解一些散列表（HashTable）的基础知识：http://www.cnblogs.com/NeilZhang/p/5651492.html
包括：散列函数、碰撞处理、负载因子等。
3.1 hash值计算
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先获取key值的hash值（每个类都有计算hash值的方法），然后将该hash值的高16位异或低16位即得到散列值。
3.2 hash散列函数
通过hash函数可以得到key值对应的hash值，那么如何通过该hash将key散列到hashtale中呢？下面再介绍一个函数：
对应的运算如下所示：length为table的长度（通常选择2^n）
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
这里的取模运算等于 hash%length ，然而&运算比%运算的效率更高。
3.3 碰撞算法：HashTable+链表+红黑树
当hash散列函数对不同的值散列到table的同一个位置该如何处理？何时需要扩容table的大小，分配一个更大容量的table？
下面这张网络上流行的图基本解释了当发生碰撞时的处理办法，
1、HashMap的主要存储为HashTable
2、当散列到的位置已经有元素存在时，通过链表将当前元素链接到table中的元素后面
3、当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。
红黑树的相关知识可以参考：算法导论 第三部分——基本数据结构——红黑树
3.4 hashtable的扩容
这里先列出了HashMap源码中的几个常量：
/**
* 默认hashtable的长度 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* hashtable的最大长度
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* hashtable的默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当Hashtable中链表长度大于该值时，将链表转换成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
HashMap构造函数可以传入table的初始大小和负载因子的大小：
public HashMap(int initialCapacity, float loadFactor) {tableSizeFor(initialCapacity);
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);
this.loadFactor = loadFactor;
this.threshold =
}
这里有一个很巧妙牛逼的tableSizeFor算法：返回一个大于等于且最接近 cap 的2的幂次方整数，如给定9，返回2的4次方16。它的具体实现（全部通过位运算完成）：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
那么关键的问题，什么时候会增大table的容量呢？原来table中的Node如何重新散列到新的table中？下面围绕这两个问题展开：
HashMap中有个成员变量 ： threshhold，当table中存放的node个数大于该值时就会调用resize()函数，给table重新分配一个2倍的容量的数组（具体可能涉及很多边界问题），并且将原来table中的元素重新散列到扩容的新表中（个人猜想这过程应该是非常耗时的，所以为了避免HashTable不断扩容的操作，使用者可以在构造函数的时候预先设置一个较大容量的table）。
那么这个threshhold的值时如何计算的呢？
1、构造函数的时候赋值： this.threshold = tableSizeFor(initialCapacity);
2、resize()的时候 threshold也会随着table容量的翻倍而翻倍。
3、threshold 的初始值： DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
这里有个疑问： 通过HashMap（）和HashMap（int，int）两种构造函数得得到的threshold值计算方法不同，前一种永远是table.length * 0.75 第二种是通过tableSizeFor(cap)计算所得，为table.length 这时负载因子似乎失去了意义？
HashTable重新散列：
当重新分配了一个table时，需要将原来table中的Node重新散列到新的table中。源码中针对hashtable、链表、红黑树中节点分别作了处理。
1. 如果是table中的值（next为null）：直接映射到大的table中，刚看的时候没理解为什么不需要判断如果新位置已经有元素怎么办？
这里不需要考虑大的table中该节点已经有Node了，比如和value | 1111 的元素只有一个（table中不是链表），那么 value | 11111 的元素也一定只有一个。（1111为扩容前table长度减1,11111位扩容后table长度减1）
在扩充HashMap的时候，不需要像JDK1.7的实现那样
2、 如果是链表中的值，则重新散列后他们可能有两种不同的值（增加了一个异或位），需要重新散列到两个位置。
java1.8 重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，HashMap的源码真的有太多精妙的地方了。
3、如果是红黑树中的节点，重新散列后的值也可能出现两种，需要对红黑数进行操作，重新散列（这一块没有具体看源码）。
resize（）函数源码：
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
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 { // 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) {
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;
}
3.5 put方法分析
介绍了上面的这么多下面分析put函数就不是那么难了：
JDK1.8HashMap的put方法源码如下:
1 public V put(K key, V value) {
2 // 对key的hashCode()做hash
3 return putVal(hash(key), key, value, false, true);
4 }
5
6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
7 boolean evict) {
8 Node<K,V>[] tab; Node<K,V> p; int n, i;
9 // 步骤①：tab为空则创建
10 if ((tab = table) == null || (n = tab.length) == 0)
11 n = (tab = resize()).length;
12 // 步骤②：计算index，并对null做处理
13 if ((p = tab[i = (n - 1) & hash]) == null)
14 tab[i] = newNode(hash, key, value, null);
15 else {
16 Node<K,V> e; K k;
17 // 步骤③：节点key存在，直接覆盖value
18 if (p.hash == hash &&
19 ((k = p.key) == key || (key != null && key.equals(k))))
20 e = p;
21 // 步骤④：判断该链为红黑树
22 else if (p instanceof TreeNode)
23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24 // 步骤⑤：该链为链表
25 else {
26 for (int binCount = 0; ; ++binCount) {
27 if ((e = p.next) == null) {
28 p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
30 treeifyBin(tab, hash);
31 break;
32 }
// key已经存在直接覆盖value
33 if (e.hash == hash &&
34 ((k = e.key) == key || (key != null && key.equals(k)))) break;
36 p = e;
37 }
38 }
39
40 if (e != null) { // existing mapping for key
41 V oldValue = e.value;
42 if (!onlyIfAbsent || oldValue == null)
43 e.value = value;
44 afterNodeAccess(e);
45 return oldValue;
46 }
47 }
48 ++modCount;
49 // 步骤⑥：超过最大容量 就扩容
50 if (++size > threshold)
51 resize();
52 afterNodeInsertion(evict);
53 return null;
54 }
参考：
http://www.cnblogs.com/NeilZhang/p/5657265.html
http://www.importnew.com/20386.html