HashMap
本文讲解的HashMap以及源代码都是基于JDK1.8
背景引入
数组
优：读取修改快 劣：增加删除慢
原因：数组可以根据下标直接定位到指定位置的数据进行读取和修改，但增加和删除需要开辟一个新数组并移动增加和删除后的数据到新数组并返回。
链表
优：增加删除快 劣：读取修改慢
原因：链表增加和删除只需断开指定位置的两端节点，但读取的时候只能从头/尾开始往另一方向读取。
拓展知识点：
数组和链表迭代的方式不同 ArrayList实现了RandomAccess接口 这是一个标记接口，标注是否可以随机访问 ArrayList使用数组实现，可以随机访问 经过测试 使用for循环遍历ArrayList更快 而LinkedList没有实现这个RandomAccess接口 不支持随机访问，使用迭代器遍历更快 RandomAccess接口的作用。
正是数组和链表各有各的优势，所以引入了散列表，结合了两者的优势尽可能的降低劣势带来的影响。
简介
Hash
哈希：英文是Hash，也称为散列 基本原理就是把任意长度输入，转化为固定长度输出 这个映射的规则就是Hash算法，而原始数据映射的二进制串就是Hash值
Hash特点：
-
从Hash值不可以反向推导出原始数据 （因为异或的缘故无法反推）
-
输入数据的微小变化会得到完全不同的Hash值相同的数据一定可以得到相同的值
-
哈希算法的执行效率要高效，长的文本也能快速计算Hash值
-
Hash算法的冲突概率要小
HashMap
HashMap ，是一种散列表，用于存储 key-value 键值对的数据结构，每一个键值对也叫做Entry，一般翻译为“哈希表”，提供平均时间复杂度为 O(1) 的、基于 key 级别的 get/put 等操作。
类图
双列集合定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap
下面针对各个实现类的特点做一些说明：
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
存储结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的
改变链表结构的默认条件：1. 单链表中的元素个数大于8时 2. 桶数组中的元素个数大于64时 【二者满足其一即可】
table数组是一个Node [] table的数组，存放node节点（Node是HashMap的一个内部类）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //当前节点经过hash扰动函数和路由算法后的值（存放位置的下标）
final K key;
V value;
Node<K,V> next; //下一个node节点
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
Hash存储过程
比较简单的描述，详细的可以看put方法流程图
以存储该键值对为例
map.put("侦探","conan");
① 系统将调用”侦探”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），
② 然后再通过Hash算法的后两步运算（高位运算 (扰动函数) 和取模运算 (路由算法) ）来定位该键值对的存储位置
Hash冲突
由来：不同的数据经过hash扰动函数hash( )、路由算法 ( hash(x) & (n-1) ) 后得到的值可能相同，此时就会存到同一个桶位，这就叫hash冲突。
解决hash冲突方法：
-
开放寻址法
-
链表法（JDK1.8使用链表+红黑树）
当不同的数据经过hash算法后到达同一个桶位，该桶内的数据就会链化。拉链法的链子就会很长，那么就会降低查找速度。
此时桶数组小了容易发生hash冲突，hash算法要是区分数据不明显也会导致hash冲突，所以仅仅时靠链表法来缓解hash冲突是不够的，也需要号的hash算法以及扩容机制来预防hash冲突。
Hash算法
hash算法包括hash扰动函数以及路由算法。Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
Hash扰动函数
作用：分散hashcode，使相似的数据有着截然不同的hash值
//hash扰动函数：加入了对高16位的特征，更见分散hash值
//(h = key.hashCode()) ^ (h >>> 16)：拿自己本身和本身右进制16位后的数组做异或运算，得到的数字就带有高16位的特征
//疑问：为什么不直接使用整个hash而是要得到前16位为0的数字？（整合hash就包括本身的高低16位数的特征）
//答案：因为hashcode的数据类型是int，有符号位所以int在正数范围内是16位。所以需要hash得到一个16的数字
static final int hash(Object key) {
int h; //key对于的hashcode值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
代码中的h>>>16就是jdk1.8新引入的高位运算算法，作用：使hashcode的高位数字特征也能一并体现再hashcode中，更加分散hash值。通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
n为table长度
路由算法
jdk1.8没有封装成方法，而是直接使用以下公式
h & (table.length-1); //h是前面hash扰动得到的值
HashMap扩容
注意点：JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置 （具体可以看下文的Resize方法讲解）
先了解几个源码变量：
//当前hash表中实际存在的元素个数
transient int size;
//当前hash表的结构修改次数（注意：改查不算结构修改，增删才算结构修改）
transient int modCount;
//扩容阈值：当hash表中的元素超过该值时，触发扩容【通过赋值因子计算得来：threshold=loadFactor * capacity】 capacity是桶数组长度
int threshold;
//负载因子【默认0.75】
final float loadFactor;
Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。
threshold扩容阈值就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择。（一般情况不修改，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1）
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)（如何保证为2的n次方下面构造方法有讲），这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。
必须为2的n次方的HashMap非常规设计目的：为了在取模 (路由算法) 和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了 (扰动函数) 高位参与运算的过程。
路由算法优化：因为要提升性能 &比%快，所以只有当容量n为2的n次方时，(n - 1) & hash == hash % (n - 1) 才成立！
扩容优化：扩容的时候方便数据迁移。（具体如何方便后文有讲）
Hash源码
构造函数
小结：扩容是一个特别耗性能的操作，所以在创建hashmap的时候尽量估算capacity容量
先认识以下变量（和前面扩容认识的变量一样）
//桶数组
transient Node<K,V>[] table;
//键值对对象
transient Set<Entry<K,V>> entrySet;
//当前hash表中实际存在的元素个数
transient int size;
//当前hash表的结构修改次数（改查不算结构修改，增删才算结构修改）
transient int modCount;
//扩容阈值：当hash表中的元素超过该值时，触发扩容【通过赋值因子计算得来：threshold=loadFactor * capacity】 capacity是桶数组长度
int threshold;
//负载因子
final float loadFactor;
四种构造方法
//指定容量和负载因子构造
public HashMap(int initialCapacity, float loadFactor) {
//1. 做校验：
//1.1 容量合法 容量要在0~最大值内
//1.2 负载因子必须大于0
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);
//2. 处理输入的capacity，保证最后的capacity为2的n次方
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); //转为capacity为2的n次方
}
//指定容量构造
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参构造
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//传map参数构造
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
保证capacity为2的n次方的算法：
//将capacity转化为大于capacity的最小的2的n次方
//原理：进来16结果是16 进来15结果是16
//0001 1101 1100 => 0001 1111 1111 => 0010 0000 0000
//解释：
// 1. 先将进来的数字-1（保证边缘不出错，如：边缘的16出去也是16）
// 2. 如何通过或运算，将最高位以下的0都转成1
// 3. 最后再+1，就可以得到capacity最小的2的n次方
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 数组的初始化，只对静态变量capacity、loadFactor赋值了，因为它是延迟初始化。只有在插入第一条数据的时候才会初始化（后面put方法中有体现）
PUT方法
put过程图
putVal代码逻辑图：
put代码：put调用putVal
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab:引用当前hashMap的散列表
//p：表示当前散列表的元素
//n：表示散列表数组的长度
//i：表示路由寻址结果
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.前面创建时延迟初始化，节约内存。在第一次插入数据调用putVal的时候才初始化hashmap中最消耗内存的散列表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.该桶位为空时直接插入：通过路由算法（tab.length-1）& hash 得到桶位并插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//3.该桶位有元素时（链表/红黑树）：
else {
//e：不为null的话，找到了一个与当前要插入的A元素的key一致的B元素（B元素是桶内的）
//k：表示临时的一个key
Node<K,V> e; K k;
//3.1 要插入的元素的key与桶内元素的key一致，则进行替换修改操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//3.2 遇到该桶位已经是红黑树的情况
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.3 遇到该桶位为链表的情况
else {
//3.3.1循环遍历链表，比对key（要插入的key和桶内链表的all key）是修改数据还是插到尾部
for (int binCount = 0; ; ++binCount) {
//① 到了末尾都没找到相同的key就插入到尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//② 添加数据后，链长度是否触发数化操作。
//binCount >= TREEIFY_THRESHOLD - 1：当binCount=7时就是第九个元素，因为从0开始并且该桶已经有元素在了
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//③ 遇到相同的key就替换修改数据
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//3.4 替换数据；当e！=null说明有需要替换的数据，就替换数据
if (e != null) { // existing mapping for key
V oldValue = e.value;
//参数允许替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//4. 如果是增加操作，就增加修改结构的次数(如果是修改操作前面会return的）
++modCount;
//5. 插入新元素长度加一，判断是否触发扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Resize方法
扩容方法resize ( )
代码：
final Node<K,V>[] resize() {
//oldTab：引用扩容前的哈希表
Node<K,V>[] oldTab = table;
//oldCap：表示扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr：表示扩容之前的扩容阈值，触发本次扩容的阈值
int oldThr = threshold;
//newCap:扩容之后table数组的大小
//newThr：扩容之后，下次再次触发扩容的条件
int newCap, newThr = 0;
//条件成立，说明hashMap中的散列表已经初始化过了，是一次正常的扩容
if (oldCap > 0) {
//如果当前容量已经大于最大容量则不能扩容，并且修改扩容条件为int最大值，防止下次触发扩容条件
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//正常扩容*2；条件是旧的容量大于16，并且扩容后的容量(*2后的)小于最大容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// oldCap == 0 && oldThr > 0 说明散列函数未初始化，但创建的时候有指定容量
// 1.new HashMap(initCap,loadFactor)
// 2.new HashMap(intiCap)
// 3.new HashMap(map) 并且Map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//oldCap == 0，散列表未初始化过，且创建的时候没指定容量。此时就需要设置默认值
// 1.new HashMap();
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0的时候，通过newCap和loadFactor计算出一个newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值为计算出来的 newThr
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建一个很大的数组（如果是默认初始化就是16，是扩容就是*2，是指定初始化就是大于capacity最小的2的n次方）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//更新table的引用
table = newTab;
//原数组中有值，需要做数据迁移
if (oldTab != null) {
//遍历原数组中的元素
for (int j = 0; j < oldCap; ++j) {
//e：暂存当前的node节点
Node<K,V> e;
//当前桶位有节点：单个数据、链表数据、红黑树数据
if ((e = oldTab[j]) != null) {
//前面e已经记录了当前节点，所以当前节点置为null便于 GC回收
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;
//低高位链表例子：x可能为0 1
//x1111在原数组的15，根据路由算法到新数组中要么在15要么在31，因为x只有0 1变化
//存放当前链表的一个元素
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倍)，所以元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置（看下图可以明白这句话的意思）n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。下图以16扩容为32的resize示意图：
GET方法
代码：
//根据传入的key，得到其hash然后去查是否有该值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
// tab：引用当前hashMap的散列表
// first：桶位中的头元素
// e：临时node元素
// n：table数组元素
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//有数据可查的时候：桶hash存在并且hash路由算法得到的桶不为空
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) {
//桶位里是红黑树，查找红黑树O(LogN)
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;
}
Remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//逻辑：先查到然后标记，再删除标记的元素
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// tab：引用当前hashMap的散列表
// p：当前node元素
// n：表示散列表数组长度
// index：表示寻址结果
Node<K,V>[] tab; Node<K,V> p; int n, index;
//查找：
//有数据时：判断hash桶是否为空，并且根据hash路由到的桶位是否存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node：查找到的结果
// e：当前Node的下一个元素
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;
//桶位节点数据有多个，可能是红黑树or链表
else if ((e = p.next) != null) {
//红黑树查找
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)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<K,V>)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;
}
Replace方法
//根据 k 和 v 替换
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
//根据 k oldValue newValue 替换
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}