摘要：当哈希表中的键值对的数量超过当前容量与负载因子的乘积时，哈希表将会进行操作，使哈希表的桶数增加一倍左右。只有散列值相同且相同才是所要找的节点。
HashMap容器
1. 简介
HashMap基于散列表实现了Map接口，提供了Map的所有可选操作，HashMap与Hashtable大致相同，区别在于HashMap不支持同步而且HashMap中存储的键值都可以为null。HashMap中不保证散列表的顺序。
当散列函数将元素正确地分散到各个桶之中的时候，HashMap中存取操作的时间复杂度都是O(1)。当HashMap实例的容量（capacity）为M，存储的键值对的数量（size）为N时，遍历HashMap的时间复杂度为O(M+N)。
影响一个HashMap实例的性能的两个参数分别是：initial capacity（初始容量）和 load factor（负载因子）。容量表示哈希表中桶的个数，初始容量就是HashMap实例在构造化时初始化的容量；负载因子则控制哈希表在多满的时候需要自动扩容。当哈希表中的键值对（entry）的数量超过当前容量与负载因子的乘积时，哈希表将会进行rehash操作，使哈希表的桶数增加一倍左右。
一般默认的负载因子取0.75，可以较好地平衡时间与空间花费。过高的负载因子虽然节省空间，但是增加了访问哈希表的时间消耗。在设置初始容量时需要考虑散列表中期望存放的键值对数量以及负载因子，减少rehash的次数。
2. 方法
2.1 构造方法
HashMap的构造方法共有四种重载形式，可以在构造时指定HashMap的初始容量、负载因子或者使用已有的HashMap来初始化新的HashMap。
HashMap map1 = new HashMap<>(); // 创建空的HashMap，默认容量16，默认负载因子0.75
System.out.println(map1); // {}
int cap = 50;
HashMap map2 = new HashMap<>(cap); // 创建空的HashMap，初始化容量为cap，默认负载因子0.75
System.out.println(map2); // {}
float lf = 0.5f;
HashMap map3 = new HashMap<>(cap, lf); // 创建空的HashMap，初始化容量为cap，默认负载因子lf
System.out.println(map3); // {}
HashMap map4 = new HashMap<>(map3); // 使用另一个HashMap来创建一个新的HashMap
System.out.println(map4); // {}
System.out.println("map4 == map3? "+(map4 == map3)); // 不是同一个HashMap对象
System.out.println("map4.equals(map3)? "+(map4.equals(map3))); // HashMap中的内容相等
2.2 添加元素
HashMap提供put(K key, V value) 、putAll(Map m)
以及putIfAbsent(K key, V value)方法向HashMap添加单个键值对或添加指定HashMap中的所有键值对。
map1.put("a", 100); // 添加{k:v}记录
System.out.println("map1:"+map1); // map1:{a=100}
map2.putAll(map1); // 复制另一个HashMap的所有键值对
System.out.println("map2:"+map2); // map2:{a=100}
int ret1 = map1.putIfAbsent("a", 200); // 尝试添加记录{k:v}，若k已存在且指向非null，返回当前HashMap的k所指对象
System.out.println("map1:"+map1+" return:"+ret1); // map1:{a=100} return:100
Object ret2 = map1.putIfAbsent("b", 200); // 若k不存在或指向null，添加{k:v}记录，返回null
System.out.println("map1:"+map1+" return:"+ret2); // map1:{a=100, b=200} return:null
2.3 删除元素
HashMap提供重载的remove()方法删除HashMap中的键值对。
int ret3 = map1.remove("a"); // 根据指定的键删除一个键值对
System.out.println("map1:"+map1+" return:"+ret3); // map1:{b=200} return:100
boolean ret4 = map1.remove("b", 300); // 删除指定的键值对，若k不指向v，则不删除，返回是否成功删除
System.out.println("map1:"+map1+" return:"+ret4); // map1:{b=200} return:false
boolean ret5 = map1.remove("b", 200);
System.out.println("map1:"+map1+" return:"+ret5); // map1:{} return:true
2.4 访问元素
HashMap提供get(Object key)和getOrDefault(Object key, V defaultValue)获取指定键对应的值，若HashMap中无该键的记录，前者返回null后者返回默认值。
int val1 = map2.get("a"); // 获取指定键的值，若无记录返回null
System.out.println("map2:"+map2+" a:"+val1); // map2:{a=100} a:100
int val2 = map2.getOrDefault("b", 200); // 获取指定键的值，若无记录则返回指定值
System.out.println("map2:"+map2+" b:"+val2); // map2:{a=100} b:200
2.5 元素变更
HashMap提供重载的replace()方法，用于更新HashMap中指定的键值对。
int ret6 = map2.replace("a", 300); // 更新HashMap中存在的某个键对应的值，返回更新前的值
System.out.println("map2:"+map2+" return:"+ret6); // map2:{a=300} return:100
Object ret7 = map2.replace("c", 300); // 更新HashMap中某个键的值，若无该键的记录，直接返回null
System.out.println("map2:"+map2+" return:"+ret7); // map2:{a=300} return:null
boolean ret8 = map2.replace("a", 300, 400); // 更新HashMap中存在的指定键值对，返回操作是否成功
System.out.println("map2:"+map2+" return:"+ret8); // map2:{a=400} return:true
boolean ret9 = map2.replace("a", 100, 200); // 指定的键值对不对应
System.out.println("map2:"+map2+" return:"+ret9); // map2:{a=400} return:false
boolean ret10 = map2.replace("b", 100, 200); // 无指定的键
System.out.println("map2:"+map2+" return:"+ret10); // map2:{a=400} return:false
// void replaceAll(BiFunction function)
2.6 HashMap操作
clear()方法用于删除所有元素；
isEmpty()方法检查HashMap是否为空；
size()方法返回HashMap中键值对的数量；
containsKey(Object key)方法检查HashMap中是否有指定的键的记录；
containsKey(Object value)方法检查HashMap中是否有指定的值的记录；
boolean ret11 = map1.containsKey("a"); // 检查HashMap中是否有指定的键的记录
System.out.println("map1:"+map1+" return:"+ret11); // map1:{a=100, b=200, c=100} return:true
boolean ret12 = map1.containsKey("d");
System.out.println("map1:"+map1+" return:"+ret12); // map1:{a=100, b=200, c=100} return:false
boolean ret13 = map1.containsValue(100); // 检查HashMap中是否有指定的值的记录
System.out.println("map1:"+map1+" return:"+ret13); // map1:{a=100, b=200, c=100} return:true
boolean ret14 = map1.containsValue(500);
System.out.println("map1:"+map1+" return:"+ret14); // map1:{a=100, b=200, c=100} return:false
entrySet()方法以Set的形式返回HashMap中的每个键值对（Entry）；
Set ret15 = map1.entrySet(); // 以Set的形式返回HashMap中的每个键值对（Entry）
System.out.println("map1:"+map1+"
Set:"+ret15);
// map1:{a=100, b=200, c=100}
// Set:[a=100, b=200, c=100]
keySet()方法以Set的形式返回HashMap中的每个键；
Set ret17 = map1.keySet(); // 以Set的形式返回HashMap中的每个键
System.out.println("map1:"+map1+"
Set:"+ret17);
// map1:{a=100, b=200, c=100}
// Set:[a, b, c]
values()方法以Collection的形式返回HashMap中的值。
Collection ret19 = map1.values(); // 以Collection的形式返回HashMap中的值
System.out.println("map1:"+map1+"
Collection:"+ret19);
// map1:{a=100, b=200, c=100}
// Collection:[100, 200, 100]
3. 源码分析
版本：jdk 1.8
3.1 存储结构
HashMap中使用一个数组存储键值对（Node），数组的大小默认为16，且只能为2的整数次幂。
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
每个Node中记录四个字段，
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
...
}
3.2 put()方法
put(K key, V value)方法向HashMap中添加一个键值对，
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
* ...
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其会对输入的key调用hash()方法，再调用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法实现，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
/*判断是否需要扩容，若需要则扩容，最后得到HashMap的当前容量*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*计算新添加条目在散列表的位置，若hash值没发生冲突，直接添加新条目*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/*hash值冲突*/
else {
Node e; K k;
/*若新添加的条目的key与已有的key相同，则覆盖*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/*若该桶中已经是树结构，添加条目到该树中*/
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
/*新条目与旧条目hash值相同，key不同的情况（采用拉链法）*/
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 新条目插在链表末端
/*若链表长度大于等于8时，转换为树结构*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*若新添加的条目的key与链表中已有的key相同，则覆盖*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
/*记录操作次数*/
++modCount;
/*添加条目后再检查是否需要resize*/
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
在插入新条目的时候，首先根据key计算出散列值，然后根据散列值确定条目存放的桶的下标，
i = (n - 1) & hash // i为桶的索引,n为桶的数量
如果该位置为空，则直接存放新条目；如果不为空，则在该位置使用链表记录这些相同散列值的条目，当一个桶记录的条目大于8时，改用红黑树记录该桶中的元素。
3.3 get()方法
get(Object key)方法根据指定的key返回一个value，
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
调用了getNode(int hash, Object key)方法，获取指定key的节点（Entry），
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
/*在红黑树结构中搜索节点*/
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
/*在链表中搜索节点*/
do {
/*分别比较散列值和key是否相同*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
在寻找指定key的节点时，会先比较散列值是否相同，再比较key的值是否相同。只有key散列值相同且key相同才是所要找的节点。
3.4 remove()方法
remove()方法，
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
调用removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)方法，
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
/*找到待删除的节点，并用node指向它*/
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)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
/**/
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
/*在红黑树中删除该节点*/
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
/*该桶只有一个节点*/
else if (node == p)
tab[index] = node.next;
/*在链表中删除该节点*/
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
3.5 计算桶下标
在诸如插入或者删除的操作中都涉及到桶下标的计算
i = (n - 1) & hash // n-1做hash的掩码
其中的n表示桶的个数（2的整数次幂），hash由hash(Object key)方法计算，
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
举个例子：
以在一个容量为16（1000B）的HashMap中，计算key为字符串"hello"时，应该存放的桶下标。
第一步，计算字符串"hello"的hashCode，
"hello".hashCode() = 0000 0101 1110 1001 0001 1000 1101 0010
第二步，在hash(Object key)中，将hashCode的高位（16位）与低位（16位）异或，
h = 0000 0101 1110 1001 0001 1000 1101 0010 // hashCode
h >>> 16 = 0000 0000 0000 0000 0000 0101 1110 1001 // hashCode无符号右移16位
XOR = 0000 0101 1110 1001 0001 1101 0011 1011 // 用于计算桶下标的散列值
第三步，将异或的结果作为计算桶下标的hash值，
hash = 0000 0101 1110 1001 0001 1101 0011 1011 // 散列值
n - 1 = 0000 0000 0000 0000 0000 0000 0000 1111 (15) // 桶数-1
index = 0000 0000 0000 0000 0000 0000 0000 1011 (11) // 桶下标
其中要注意的是，在第三步计算桶下标的时候，没有直接使用hash%n这样取余的方式，因为取余的方式复杂度较位运算要高。由于hash算法均匀分布的原则，作为掩码的二进制位全为1，可以使得求得的桶下标也是均匀的，因此规定table的容量应该是2的整数次幂。
而在第二步计算hash的时候将hashCode的高位与低位求异或，则是因为使用了掩码的方式求下标，导致大部分情况下只利用了hash值中低位的信息，容易产生hash冲突，因此将hashCode的高位信息通过这种形式引入到hash值中。
3.6 扩容
当HashMap中的节点数量达到临界值时，会调用resize()方法对HashMap进行扩容，该方法也用于初始化HashMap中的table数组，
final Node[] resize() {
Node[] 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;
}
/*新容量为旧容量的2倍(<<1)*/
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[] newTab = (Node[])new Node[newCap]; // 构造新的table
table = newTab;
/*将旧table中的节点保存到新table*/
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
/*桶中只有一个节点，直接放入新table*/
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
/*桶中是红黑树结构，拆分放入新table*/
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
/*桶中是链表结构，放入新table时保留链表中的顺序*/
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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;
}
在进行扩容时，首先计算新table的容量，然后将遍历旧table中的节点放到新table中，十分费时。其中涉及对节点在新table中的桶下标的计算，HashMap采取一个机制，降低重新计算桶下标的复杂度，
oldTable[index] --> newTable[index+oldCap]
举个例子，
假设原数组容量oldCap为 16，扩容之后newCap为 32：
hash = 110110 (54) // 散列值
oldIndex = 000110 (6) // 旧下标
oldCap = 010000 (16) // 旧table容量
newCap = 100000 (32) // 新table容量
按照求异或的算法，算出新下标为
hash = 110110 (54) // 散列值
newCap-1 = 011111 (32) // 新table容量-1
newIndex = 010110 (22) // 新下标
根据公式算得新的下标为
oldIndex + oldCap = 6 + 16 = 22 // 新下标
