HashMap源码浅析
1.引子
"HashMap"由“hash”和“map"两个单词组成，这里的”map"表示“映射”而不是“地图”的意思，两个单词连起来就是“哈希映射表”。Map是一个接口，它有TreeSet 、LinkedHashMap、EnumMap、HashMap等实现类，其中HashMap无疑最重要也很复杂的一个实现类。理清楚了HashMap的原理，对其他的Map实现类也就触类旁通了，其他Map实现类大部分都相对简单.
哈希是一种算法也是一种数据结构。哈希算法能够根据给定的键key快速定位到对应的值value ,HashMap是利用哈希算法实现的一个数据结构。
散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
HashMap内部常用到Object的"hashCode()"和"equal(Object)",要使用HashMap这种集合类型必须重写元素的这两个方法。
2.HashMap的类结构
HashMap继承AbstractMap，实现了Map接口,Map接口中的”addAll()“ 、"containsAll()"等方法由父类AbstractMap实现。
静态内部类Node实现了Map.Entry接口(Map中的内部接口)，它用来保存一个键-值对，表示一个链表类型节点。而TreeNode扩展了Node，当哈希人冲突严重的时候，使用TreeNode保存健单个键-值对，表示一个二叉树节点。
内部类EntrySet表示HashMap中的entry集合，KeySet表示HashMap的所有Key集合，Values表示所有的value集合。
EntrySet 、KeySet 、Values均是成员内部类而不量静态内部类，这是因为这3个内部类均要直接访问外部部类HashMap的相关成员变量，它们必须与外部类HashMap相绑定。
3.内部组成
1).静态内部类Node
Node表示包含一个键-值对基础的哈希节点。
一个Node实例表示单向链表的一个节点，当这个实例是头节点时，这个实例又可以直接表示整个链表。
Node类中有4个成员变量:
final int hash; final K key; V value; Node<K,V> next;
key value分别表示当前节点的键和值
next表示下个节点的引用（默认情况下使用链表处理哈希冲突，所以必须要有后继节点的引用）
hash表示将key进行哈希运算后的结果(使用HashMap的静态方法"hash（Object）"计算)，此属性非常重要，它决定当前节点放在哈希的哪个桶上。
2).静态内部类TreeNode
TreeNode也表示包含一个键-值对基础的哈希节点，一个红黑树节点，由于它间接继承上面提到的Node,因此它也可以表示为一个单向链表节点。
当一个桶上的节点少于8个时，使用Node当作哈希节点，当一个桶上的节点多于8个时，即哈希冲突严重时，使用TreeNode。
TreeNode中有5个成员变量。
parent、left 、right 、prev分别表示父节点、左节点、右节点、前节点
red表示当前节点的红/黑点
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;3).常量与成员变量
主要有这几个静态常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;
DEFAULT_INITIAL_CAPACITY为映射表的最默认容量，值为16,无参构造方法使用这个容量。
MAXIMUM_CAPACITY为映射表的最大容量，一般情况下容量不会超过这个数。
DEFAULT_LOAD_FACTOR是默认的加载因子，无构造方法使用这个加载因子。
TREEIFY_THRESHOLD和UNTREEIFY_THRESHOLD分别是从链表转为红黑树和红黑树转为链表的单个桶节点个数阀值。一个桶上链表节点超8个就将其为红黑树，当一个桶上红黑树结点少于6个就将其转为链表。
MIN_TREEIFY_CAPACITY是从链表转为红黑树时所要求的tabel最小长度(只有同时满足TREEIFY_THRESHOLD和MIN_TREEIFY_CAPACITY时才能从链表转化为红黑树)。
成员变量
transient Node<K,V>[] table; transient Set<Map.Entry<K,V>> entrySet; transient int size; transient int modCount; int threshold; final float loadFactor;
table是Node类型的数组，表示哈希桶。其中的每个元素是一个单向链表或红黑树。
entrySet是HashMap的所有Entry的集合。
size表示键值对的个数。
modCount表示当前实例被修改（添加或删除键值对）的次数，这用来作为快速失败的参考依据。
loadFactor表示加载因子，元素个数与容量的比值的达到这个值，table将扩容。
threshold表示阀值，它是容量与加载因子的乘积，即threshold=loadFactor*capacity。当键值对的个数size大于它时，table将扩容。
4.实现原理
构造方法
有一个无参构造方法，3个带参构造方法
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}无参构造方法”HashMap()“，使用默认的容量16、默认的加载因子0.75.
带参构造方法“HashMap(int , float )”，根据参考设写初始容量和加载因子。
带参构造方法“ HashMap(Map)”,将一个Map中的所有键值 对添加到新的HashMap中，并使用默认的加载因子。
1).保存键值对put(K,V)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}put(K,V)方法先使用hash(O)方法，算出k对应的hash值，然后调用putVal（）方法进行实际的键值对插入。
其实"java.util.HashMap#hash(Object)"方法主要逻辑很简单，就是将key.hashCode()的返回值和此返回值的无符号右移16位结果进行按位异或运算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 
根据位操作特点”（1或0）与0进行按位异或运算的结果是其本身“可看出，此处哈希算法的实质是，hashCode的高16位同样作为hash的高16位，将hashCode的高16位和其低16位的异或运算结果作为hash的低16位。
实际上putIfAbsent(K,V)也调用了putVal()方法，putVal是一个很重要也很复杂的一个方法。
putVal的核心逻辑：先根据hash确定当前键值应放入哈希表的哪个桶（这个桶是一个链表或红黑树），然后再此基础上再判断这个桶上是否存在当前键值对就存入的节点，若存在这样的节点，只需要将此节点的value属性更新为当前要添加的value.反之就要构建一个新的节点，并将此节点添加在这个桶上。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab表示哈希桶数组，p表示当前键值对应存入的链表或红黑树(桶)
// n表示table的长度，i表示数组tab的下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//table为空或没有元素时需要重新调整table的大小，否则无法容纳此时新添加的键值
n = (tab = resize()).length;
/**
* ”(n - 1) & hash“是当前键值对应该落入哈希桶的下标，这是个取余的表示式。
* 根据位运算的特点，只要n是2的幂次方，表达式"hash % n"与”(n - 1) & hash“等价
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//此下标对应的链表或红黑树为空，将它初始化
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;//e表示当前键值对应存入的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//若链表的头节点（若是红黑树结构就是根节点）的key与当前要添加的键值对key的equals和hash均相同，
//那么此链表的头节点就是当前键值要存入的节点
e = p;
else if (p instanceof TreeNode)
//若是红黑树结构就,调用单独的方法添加键值对
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//当前键值对应存入的节点在链表的非头节点位置，
//需要在链表上从头到尾进行遍历，检查此链表上是否已存在key对应的节点。
// 若存在这样的节点，将此节点的value替换成要添加的即可
//若不存在这样的节点，需要构建一个新节点，将此节点添加在链表的尾部
for (int binCount = 0; ; ++binCount) {//binCount表示当前单向链表上的节点个数。
//e表示p的后继节点，在这里可以理解为：p表示e的前驱节点（单向链表不存在前驱节点的说法）
if ((e = p.next) == null) {
//已经遍历到尾部了，链表上没有这样的节点，必须构建一个新节点放在链表尾部
p.next = newNode(hash, key, value, null);
// 这里需要TREEIFY_THRESHOLD，因为即将添加一个节点，在节点添加成功后，就会有TREEIFY_THRESHOLD个键值对
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//达到阀值了，需要将链表转化为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;//链表上存在key对应的的节点
p = e;
}
}
if (e != null) { // existing mapping for key
//链表上存在key对应的的节点
V oldValue = e.value;//保存原来的value,最后方法需要返回这个值
/**
* HashMap.putIfAbsent方法只有map中不存在key对应节点将才添加键值对,
* 调用当前putVal（）方法传入的onlyIfAbsent参数为true,
*
* 进入此处就表明map中已存在key对应的节点了（前面if条件中"e!=null"成立），
* 所以这里要在if条件中对onlyIfAbsent取反。
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//空方法，留给子类LinkedHashMap等实现，进而读取有序的功能
return oldValue;
}
}
//map中不存在key对应的节点，map会添加新节点，修改次数自增1
++modCount;
if (++size > threshold) //添加了新节点，键值对个数加1
//如果键值对个数超过阀值，需要重新调整table的容量。
resize();
afterNodeInsertion(evict);//空方法，留给子类LinkedHashMap等实现,进而实现添加（插入）有序的功能
return null;
}putVal（）逻辑详细分析：
1 .如果第1次添加键值对，table应该是null,resize()方法将对table分配内存扩容。
接下来分析下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) {
//原容量过大，不能再扩容了，将阀值设为int类型的最大值，返回原table
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//扩容（原容量的2倍）后小于MAXIMUM_CAPACITY 并且原容量大于默认初始化阀值，
//阀值设为原来的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//原容量为0且原阀值大于0，
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//阀值为0，容量为0，使用默认的容量，
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//loadFactor*capacity
}
if (newThr == 0) {
//新阀值为0时，需要重新调整阀值
float ft = (float)newCap * loadFactor; //loadFactor*capacity
//为了使阀值不超出限定范围
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) {
//将原数组oldTab的元素复制到新数组newTab中
for (int j = 0; j < oldCap; ++j) {//遍历原数组oldTab
Node<K,V> e;//e用来保存原数组中每元素
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//将原数组的元素引用赋null，加快垃圾回收
if (e.next == null)
//e的后继节点为null,e所表示的链表（或红黑树）上只有e这一个节点。
//可以直接算出此链表（或红黑树）e在新数组中应放置的下标，然后再将下标对应的元素赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//e是红黑树，单独处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// e是单向链表，且链表上有多个节点时
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//(e.hash & oldCap)=0构造一条链表,小索引链表
// 此链表放在新table的j索引位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;//loHead的引用只初始化一次，以后不再变化
else
loTail.next = e;
loTail = e;
}
//(e.hash & oldCap)!=0构造另一条链表，大索引链表
// 此链表放在新table的(j+oldCap)索引位置
else {
if (hiTail == null)
hiHead = e;//hiHead的引用只初始化一次，以后不再变化
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//后继节点为空，链表遍历已到尾
if (loTail != null) {
//尾节点的后继节点赋为null,同时将小索引链表放置在数组的指定索引处
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
//尾节点的后继节点赋为null,同时将大索引链表放置在数组的指定索引处
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}resize()方法扩容时，新的容量是原容量的2倍，且原容量就是2的幂次方，也就是说HashMap的容量始终是2的幂次方。这主要是为了快速取余。只要n是2的幂次方，表达式"hash % n"与”(n - 1) & hash“等价，而位运算显然速度更快。
在扩容过程中新旧哈希表间的元素（当哈希桶是链表结果，每个哈希表元素就是一个链表）需要复制，当链表上存在多个节点时对链表上节点的复制做了进一步的处理，根据条件语句“(e.hash & oldCap) == 0”的结果进入不同分支处理。如果链表的节点执行条件语句“(e.hash & oldCap) == 0”，其结果true、 false都有，resize方法就会构建两个链表，两个链表在数组table上索引相差oldCap。
(2) 如果根据表达式“ (n - 1) & hash”算出键值对当前键值对应该存入哈希桶的下标，如果此哈希桶为null,就用newNode()方法将其初始化。
newNode()只是简单地调用了Node的构造方法而已。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}(3)在找到哈希桶后，下一步就是确定当前键值对应该丰入哈希桶后的哪个节点位置。
此时有两种情况，一种是此桶上已经存这样的键了，另一种是此桶上不在这样的键的节点。若桶上存在这样的节点，就直接将该Node的value属性替换。若桶上不存在这样的节点，将构建一个新的Node节点，并添加在（此桶为链表结构时）链表的尾部。
是否存在这样的键的判断流程是“先判断hash是否相等，若hash不等再判断equals()是否为true”。这里为会把先判断hash呢？因为hash已经是一个整数了，整数的比较很快速，而equals()方法需要进一步计算才能得出结果。若hash不等，就不需要进行耗时的equals方法计算，这样可以提高算法的性能。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))2).根据键获取值get(Object)
get(Object)方法体内部，主要调用getNode(int,Object)方法找出key对应的Node节点，然后（这个node存在时）再取node节点的value属性
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}我们之前有过分析添加键值对的方法put(K,V)的基础 ，这里再看getNode(int,Object)方法的逻辑就很简单了。
先确定key对应的Node节点应该在的哈希桶，再在这个哈希桶上遍历链表或红黑树，找到满足条件的key对应节点。若没有这个节点就返回空。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//key对应的Node节点应在table的某个哈希桶。
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//key对应的节点是哈希桶的头（根）节点，可以直接返回这个节点。
return first;
if ((e = first.next) != null) {
//key对应的节点在桶上的非头（根）节点位置，需要遍历链表（红黑树）
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;
}3).移除键值对
”remove(Object)“与“remove(Object, Object)”方法均能将键值对（Entry节点）从哈希映射表中移除，且这两个方法都是委托”romveNode(int,Object,Object,boolean,boolean)“方法实现的，只不过后者“remove(Object, Object)”方法要在键与值均匹配的情况下才会移除键值对（Entry节点）。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}有了前面分析putVal方法的基础，阅读方法removeNode方法就比较轻车熟路了。
先是根据hash找到table的索引，再遍历此索引位置元素所代表的链表（或红黑树）。尝试找到这个键值对对应的节点，判断是否找到的规则，依然是先比较hash再比较equals. 若找到这个节点，则将此节点的前后节点通过next属性链接起来。
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//start 与putVal方法前半部分逻辑几乎一致
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// p表示e的前驱节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//end 与putVal方法前半部分逻辑几乎一致
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//存在这样的node节点，且未要求匹配value或在要求必须匹配value时value也刚好匹配
if (node instanceof TreeNode)
//红黑树单独处理
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
//要移除的node节点是链表的头节点时，将原头节点的后继节点设为新的头节点
tab[index] = node.next;
else
//要移除的node节点是非头节点时，使用next属性将node的前驱节点和后继节点直接链接在一起
p.next = node.next;
++modCount;//减少了一个节点，修改次数加1
--size;//键值对个数自减
afterNodeRemoval(node);//空方法，留给子类实现
return node;
}
}
return null;
}4).与之相关的HashSet
Set表示的是无重复元素且不保证顺序的集合接口。HashMap基本特性之一是Key必须保证唯一、不重复，否则无法根据Key来定位Value,正是基于这一点，HashSet实际上是利用HashMap实现的，它的大部分方法都是直接委托相应的HashMap方法完成功能。
HashMap中有键值对，而HashSet只利用了HashMap的键。HashSet添加元素e时，会在其HashMap类型的属性map中添加键是e值o为PRESENT的键值对 ,即每次添加键值对Entry时，其值始终是常量PRESENT，只有键会根据添加的元素e不同而变化。
5).与之相关的LinkedHashMap
LinkedHashMap是HashMap的子类，它们保证键值对先后顺序，并且（使用构造方法相应的参数）支持选择使用访问访问或添加顺序，默认使用添加顺序。
构造方法：
其构造方法的逻辑也主要是调用父类HashMap的构造方法
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}成员变量
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;LinkedHashMap比HashMap多一条双向链表，用此链表来记录相应的顺序。
双向链表的类类型LinkedHashMap.Entry也是继承于父类HashMap中的静态内部类HashMap.Node<K,V>，只不过添加了before、after这两个表示前驱、后继节点的成员变量，将父类的单向链表变成了双向链表而已。
5.总结
1）不论是添加键值对、删除键值对或获取键对应的值，其基本流程都是先确定算出Key的hash,再根据hash找到对应的table索引（即找到哈希桶），再确定节点应在哈希桶的哪个位置。
2）健的hash是随机的，这导致表达式“(n - 1) & hash”的结果是无规律可循的，因此HashMap的键值对是无序的。若要使用有序的HashMap，请使用其子类LinkedHashMap.
3) 哈希表table每次扩容后，键值对Entry所在的哈希桶的索引，可能不变，即就是原来的index ,也有可能变成（index+oldCap），且只有这两种可能的情况。
4）HashMap不是线程安全的，在并发场景建议使用ConcurrentHashMap。虽然Hashtable也是线程安全的，但它是直接在方法上使用synchronized，是利用阻塞式的锁保证线程安全的，其并发效率低。