1.HashMap概述
HashMap在java的java.util包下的属于基本数据容器类，以key-value的形式来作为基本的数据结构。特性为 key唯一且可为null，value值可重复可为null。
值得注意的是HashMap是线程不安全的，如果想要线程安全的map，可以使用Collections.synchronizedMap(hashmap)，或者使用ConcurrentMap<K,T>()接口下实现的map，尽量避免使用hashtable如果在多线程情况下，因为其是全局线程锁的，对性能消耗比较大。
继承的抽象类：AbstractMap<K,V>
实现的接口：Map<K,V>,Cloneable,Serializable
接口的实现说明，1.属于顶级Map父接口 2.可复制 3.可序列化
其中Cloneable接口很值得说一下，它是一个空接口，其是作为一个申明式接口，也是看源码学习到的一个编程思想，通过类所实现的接口来说明其类有什么功能。所以可以在项目中创建一些空接口语义具体来且普遍来供其它类来实现，说明实现类有哪些功能。
~哈哈，扯得有点远了，下面正式进入HashMap的源码与原理分析中。
2.HashMap实现原理
先用一张图来简单解释一下HashMap内部结构
HashMap内部是以一个散列表+链表的结构。而在JDK1.8之后多HashMap有所变化，是以散列表+链表（而当链表数量达到8后，会以红黑树的形式替代链表）
明白了内部实现之后，聪明的你一定想到了，java到底是如何将各种不同类型的key放入桶中的呢，还有为什么要用这么复杂的结构来存入数据结构，直接用数组不行吗？等等…这些疑问我会在源码中一一讲解。
3.HashMap源码分析
3.1关键字段
//常量声明
transient Node<K,V>[] table;//散列表，存放实体元素的数组
transient int size;//已存元素容量
transient int modCount;//修改的次数（用于fail-fast）
int threshold;//临界值，当 size>=threshold扩容， 临界值 = 加载因子 * 数组长度
final float loadFactor;//加载因子
| 默认参数 | 含义 | 作用 |
|---|---|---|
DEFAULT_INITIAL_CAPACITY = 1 << 4 |
初始数组的长度 | 确定数组的初始容量，必须是2的倍数后面会讲的主要是用于位运算确定hash桶时使用 |
MAXIMUM_CAPACITY = 1 << 30 |
数组的最大长度 | 超过了这个长度不再进行扩容（hash碰撞就碰撞吧） |
DEFAULT_LOAD_FACTOR = 0.75f |
碰撞因子 | 当map中的元素大于 其容量 * 碰撞因子时，进行扩容 |
TREEIFY_THRESHOLD = 8 |
桶中元素树化阈值 | 当桶中元素>=8个时，将其树化 |
UNTREEIFY_THRESHOLD = 6 |
树化结构还原链表结构阈值 | 当树形结构元素<=6个时，进行链表化 |
MIN_TREEIFY_CAPACITY = 64 |
最小树化阈值 | 当map中的元素个数>=64时，才将桶中元素>=8个的链表树化。主要作用是为了避免 数组的扩容与链表树化之间冲突。 |
3.2构造函数
HashMap一共有四个构造函数：
3.2.1构造函数一：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
//此无参构造函数是最常使用的一个，
//可以看出 all other fields defaulted,其他字段都是默认的，碰撞因子也是默认`0.75`
}
3.2.2构造函数二：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
//可以传入 map的初始容量，调用的是构造函数三，其中碰撞因子时默认的0.75
}
3.2.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);
}
构造函数三值得说一下：
这里的tableSizeFor(initialCapacity)函数源码如下
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;
}
看着这个算法开始我是懵逼的，这是个什么鬼？通过返回时的 三元表达式看出，其实在确定一个值，而这个值不能大于定义的map容量。通过实验得知tableSizeFor是返回一个传入值的 最近二次幂数（>=cap的最小二次幂），通过在网上资料jdk1.8hashmap hash与tableSizeFor源码解析可以大致明白。
最后的判断没有大于定义的最大容量便返回，n+1,因为此时此数二进制从原来第一个高位1位开始后面所有位都为1。 图中最后运算结果
n =
0000 0000 0000 0000 0000 0000 0000 1111 +
1(0000 0000 0000 0000 0000 0000 0000 0001)
便成了 0000 0000 0000 0000 0000 0000 0001 0000 结果返回为16.
有人认为这不是多此一举吗？也是我举得列子不好，如果传入的数不是一个 2 幂的数，那么从上述过程，便可以返回一个，大于这个数的最小2幂数。非常精妙的算法！感觉进入了0与1的世界。
但是这里还有一个疑问，因为tableSizeFor返回是赋值给threshold作为临界值的，可是为什么直接为其赋值了，而不是乘上一个loadFactor加载因子呢？也是百思不得其解，总觉得是哪里有问题，后来查阅资料发现，注意：前三个构造函数，其实都还么有将其散列表初始化，也就是说这时是的map是没有数据结构的。这时的threshold只是一个记载值的变量，当第一次put元素的时候，才会去初始化map中数据结构，那时threshold值就是数组的长度，这也是保证了数组的长度必须是2的幂数。
3.2.4构造函数四：
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
此构造函数，传入一个map，默认碰撞因子为0.75，会返回一个传入时map所有元素的HashMap.
3.3数据存储（原理实现）
3.3.1底层存储对象
在看map如何存入数据前先看一下，其底层是用什么来存储的
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
//元素的hash值
final int hash;
//传入的key
final K key;
//传入的value
V value;
//下一个元素
Node<K,V> next;
//...
}
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
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
//...
}
对外暴露put方法：
public V put(K key, V value) {
//调用方法putVal
return putVal(hash(key), key, value, false, true);
}
而通过之前的介绍知道，map的数据结构为散列表+链表结构，而链表是发生hash碰撞时才会添加，我们知道链表的长度越长（hash碰撞的次数越多），就会导致map获取的性能降低。为了确保map中的key可以均匀分布所以需要对hash值进行跟进一步的优化，以确保hash碰撞的次数最少，列表跟随机分散。
在Java8中hashmap源码看出，得到 key 确定桶的位置 一共经历的两步。
第一步：
static final int hash(Object key) {
int h;
//高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
源码可以看出hash中主要的操作是
(h = key.hashCode()) ^ (h >>> 16),而这一步是什么意思呢？表面上可以看出是将
key的hashcode值 ^(异或) 上 其无符号右移16位的数。这个算法的用途还需要结合第二步才能真正的去理解，我们通过之前的介绍知道了这两步的结合是为了更好的将key均匀散列到表中，
hashcode我们知道是一个int值，而int值的表示范围是-2^32 ~ 2^32 - 1这之间是有2^32的 两倍减一个数的，而我们的散列表呢，最长为2^30长度，粗略计算int的范围就是我们散列表的两倍，那么我们直接使用hashcode就会浪费很多位(bit)的特性，从而不能更好利用hashcode的不重复性.通过
(h = key.hashCode()) ^ (h >>> 16)这个小小的公式就能解决吗？答案是可以的。 我们看看这个公式它是如何解决的，h >>> 16这个是将hashcode值无符号右移16位，int是32位的，就是将它的高位（前16位）变成低位（后16位），这时在做一个异或的操作，因为我们知道^这个运算符，相同为1，不同为0。这样就把hashcode值给变成高位与低位进行了一个混合，将高位的数字特性也做了保留。讲了这么多~还是一张图再来说明一下吧。
第二步：
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;
//获取桶位置算法 i = (n - 1) & hash
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//...
//...
}
第二步从图中的注释位置，知道hashmap中是使用
i = (n - 1) & hash来确定到散列表的具体位置。 注意：这里就涉及到了为何hashmap中的初始长度要为2次幂的问题。当n为一个数的二次幂时，那么其二级制表达，就应该是只有一个1其他全是0，例如：2 -> 0000 0000 0000 0000 0000 0000 0000 0010、16 -> 0000 0000 0000 0000 0000 0000 0001 0000，那么这样的数减一后，就成了最高位的1为’0’,所有高位1,之后的位数都为1。这也是为什么hashmap的散列表长度必须是2的次幂原因。
而说了这么多其实 i = (n - 1) & hash 与 hash % n是等价的也就是说，(n - 1) & hash = hash % n 这个等式的成立必须是n是2的次幂。
这里使用(n - 1) & hash替代hash % n原因是：&运算的效率要比%运算的效率高很多。
深入源码是不是发现，各种小优化小算法让人赞叹不已！是的好的程序员算法是必须的！！接下来正式进入put方法，还有更多的小细节等着我们。
在解析hashmap的put源码前先看一下，put方法的流程桶：
注：引用于Java8系列之重新认识HashMap
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* key计算的hash值
* @param key the key
* key值
* @param value the value to put
* value值
* @param onlyIfAbsent if true, don't change existing value
* 如果为true（且key对应的元素不为null，若key对应的value为null时，即使此参数为true也会被覆盖，源码中会注释），则不覆盖value值。
* @param evict if false, the table is in creation mode.
* evict参数用于LinkedHashMap中的尾部操作，这里没有实际意义。
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//Node<K,V>[] tab：申明hashmap数据结构、
//Node<K,V> p: 申明对应此次添加元素
//int n: tab的长度
//i : 元素p对应桶的位置
Node<K,V>[] tab; Node<K,V> p; int n, i;
//将全局变量赋值给声明的tab，若为null，说明第一次put元素。
if ((tab = table) == null || (n = tab.length) == 0)
//resize() 初始化散列表，将其赋值给tab，长度赋值给n
n = (tab = resize()).length;
//取出key对应hash桶位置上的元素，若为null，说明没有碰撞
if ((p = tab[i = (n - 1) & hash]) == null)
//将key:value封装成对象，放入tab[i]桶中
tab[i] = newNode(hash, key, value, null);
else {
//以上都不满足条件说，出现hash碰撞。
//Node<K,V> e:声明一个map中元素
//K k:声明一个key;
Node<K,V> e; K k;
//判断key是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//若相同将 需要加入的key:value封装对象赋值给e
e = p;
//判断是否为 TreeNode类型（判断桶中链表是否已经为树形结构）
else if (p instanceof TreeNode)
//若是，调用添加putTreeVal方法（添加树形结构的方法）
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//以上条件都不满足。说明 tab[i]位置上为链表结构，且将元素最近进链表中
//for循环计数
for (int binCount = 0; ; ++binCount) {
//又上赋值过程可知，此时p元素为map的tab中第i个元素。
//p.next，找出p的下一个，直到找到为null的（即最后一个），然后将需要put的元素追加
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判断，此时链表是否超过了设定的链表长度阈值（从这里看出，当>8不包含8时就会变成树形结构）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//tab中hash对应桶位置的链表，转化为红黑树
treeifyBin(tab, hash);
//跳出循环
break;
}
//判断如果 找到链表中有与添加的key相同的值时，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//以上条件都不满足，将e赋值给p，遍历下一个链表元素
p = e;
}
}
//如果e!=null说明，map中有对应的key相同的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判断，是否覆盖，传入的参数中可以设置是否覆盖旧的value，参数onlyIfAbsent为true时，不覆盖旧的value
//但是当旧value为null，这个设置就没有用。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这个方法是linkedhashmap中的方法，在hashmap中是一个空方法
afterNodeAccess(e);
//返回很有意思，几乎很少有人注意到，put方法有返回值，其返回的是，被覆盖的value值。
return oldValue;
}
}
//修改次数++
++modCount;
//这个判断的可以理解为，size++ >= threshold .
//由于这里的put方法还没有走完，所以如此判断。
//在put之前map中所有元素的个数是否超过的阈值
if (++size > threshold)
//若超过了，重新resize()
resize();
//这里同afterNodeAccess方法一样是操作linkedhashmap的，是一个空方法
afterNodeInsertion(evict);
//返回null
return null;
}
其中还有几个函数，
resize:下一节中讲到
putTreeVal,treeifyBin：在下一小节java8红黑树优化哈系桶中讲到
newNode:
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
//返回一个新new的node，其中next为null
return new Node<>(hash, key, value, next);
}
3.3.2java8红黑树优化哈系桶
java8-hashmap 桶中链表元素多与一定数量后会变成红黑树结构，而红黑树又是一个比较复杂的类数据结构，另开一篇博客分析 红黑树篇。
3.4大小调整
resize方法，顾名思义，重新调整hashmap中的散列表大小。
大致逻辑为：
1.创建新的散列表，长度是原来的两倍
2.将原来散列表中的元素，key重新计算hash值确定新的桶位
3.将所有元素放入新散列表中
final Node<K,V>[] resize() {
//声明一个oldTab 将原hashmap中table赋值给其
Node<K,V>[] oldTab = table;
//oldCap 旧的桶位数量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr 旧的扩充阈值
int oldThr = threshold;
//声明 新桶位，与新阈值
int newCap, newThr = 0;
if (oldCap > 0) {
//如果就桶位大于等于最大桶位阈值
if (oldCap >= MAXIMUM_CAPACITY) {
//设置扩充阈值为int的最大数。
threshold = Integer.MAX_VALUE;
//返回当前散列表（已经是最大散列表长度，不能再扩充）
return oldTab;
}
//将桶位扩充两倍，若不小于最大桶位阈值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//将扩容阈值也扩大两倍
newThr = oldThr << 1; // double threshold
}
//oldCap > 0不满足时，说明是初始化hashmap中的散列表
else if (oldThr > 0) // initial capacity was placed in threshold
//当oldThr>0时（说明调用了上面讲过的 构造函数三或构造函数二）
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//如果为零，使用的无参构造函数，所有参数使用默认
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果 新的扩容阈值为0
if (newThr == 0) {
//计算扩容阈值。
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将变量newThr赋值给类字段threshold
threshold = newThr;
//创建新散列表
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新散列表赋值给类字段table
table = newTab;
//如果oldTab不为null，需要将oldTab里元素移植到newTab中
if (oldTab != null) {
//遍历旧hashmap中所有的元素
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
//如果桶位中是链表结构，进行链表复制
//在jdk1.8之前，时重新计算每一个key的hash值将其放入新的散列表中
//jdk1.8对此作了优化，就是下面一段
//原理是，在旧桶位中的元素通过全部计算发现，其中的元素要么是在原位，要么是在原位的2次幂位置
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//将原有桶位元素的next元素，赋值给变量next
next = e.next;
//这里使用 e.hash & oldCap 是否等于0来确实是否需要移动桶位
//这个设计思路与桶位必须是2次幂也是有关系
//举例：
//因为确定桶位是 e.hash & (oldCap-1)之前有将过，
//例如：
//oldCap 16 : 0001 0000
// 16-1=15 : 0000 1111
//因为 newCap = oldCap << 1
//newCap 32 : 0010 0000
// 32-1=31 : 0001 1111
//对比发现 31与15 二进制表达中只是 31 第5位是1，15第5位是0
//得出，当原来e.hash，因为15第5位是0，所以无论e.hash第五位是什么&过后得到的数字第五位都是0
//若 e.hash 第5位为1时，e.hash & (newCap - 1) 就会比 e.hash&(oldCap - 1) 大两倍。
//所以在移动到新散列表时，只需要确定第5位是否为1（上述列子）就可以确定e在新散列表的位置
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数据读取
public V get(Object key) {
Node<K,V> e;
//调用getNode函数，返回node，如果为null返回null，不为null，返回e.value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) {
//先判断对应桶位第一个元素是否是需要找的元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//上述不满足，寻找下一个元素
if ((e = first.next) != null) {
//如果桶位为树形结构，调用getTreeNode方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//遍历链表，找到key对应的node。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4.HashMap小细节
4.1HashMap-fail-fast（快速失败）
都知道hashmap是线程不安全的，所以引入了快速失败机制，用字段 modCount 记录，每一次对hashmap中元素进行变动时，都会++一次。当在迭代时，每一次的迭代取值都会判断，在此间是否对hashmap进行过操作，例如当下列代码：
HashMap<Integer, Integer> integerIntegerHashMap = new HashMap<>();
integerIntegerHashMap.put(1,1);
integerIntegerHashMap.put(2,2);
integerIntegerHashMap.put(3,3);
for (Integer integer : integerIntegerHashMap.keySet()) {
integerIntegerHashMap.remove(integer);
}
这样写是不容许的，会报错java.util.ConcurrentModificationException。这里就使用到了快速失败的技术。
下面是迭代keyset源码：
final class KeySet extends AbstractSet<K> {
//
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
//在进入循环时记录当前的modCount
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
//以后每一次循环都做判断只要不与成员变量相等就抛出异常。
//对应上面代码，在遍历中 对hashmap进行了删除操作，所以使得直接抛出异常
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
4.2transient关键字
transient关键字：意思是被修饰的字段，在对象被序列化时，是不会被序列化到磁盘上的。
4.3clone方法浅复制
clone是将hashmap对象浅复制一个版本，也就是说，其中复制的是元素（对象）的引用而不是新new出一个元素，故当原有的元素内部发生改变时，原hashmap中其元素会改变，clone出的版本也会改变。
5.有关hashmap的面试题
也是因为最近也在面试的缘故，有一个不错hashmap的面试题用来分享。
当已知存入的元素hash碰撞的概率会很高（比如说10%以上），如何去设置hashmap的参数？
首先这是一个开放式的题目，我从两个角度来分析，有得出不同的答案。
- 降低碰撞因子，增大初始长度。这个解决思路是从降低碰撞率来说的。 为什么可以降低碰撞率？ 我们上面分析的可以知道同一个桶位中，在resize时其中的元素会在原位，又可能在其原位+扩充长度位置。那么从开始的一直初始值长度，较高的设定，与较低的碰撞因子设定，保证了散列表中有大量的空闲桶位，可以相对于较小桶位时，相对的减少碰撞几率。
这个答案，是通过消耗大内存空间，而实现相对的hash碰撞减少，从而使得数据存取快捷。
这是我面试时的答案，但是想想可能是我理解错了问的意思。
问题的意思可能是这个碰撞几率是固定已知比较大的。
- 升高碰撞因子，设置与装入数量差不多的初始长度。 这个解决思路是： 在碰撞率固定(较高)的情况下，就可以更大限度的利用散列表的空间，不至于浪费内存空间，也减少了resize的次数。设置较大初始长度是单纯的从减少resize角度出发，这个方法不能让其元素更加的散列，但是可以更有效的利用内存空间。
这个答案是从内存空间考虑，更加有效的利用内存空间。
你看开放式的问题就会有开放式的答案。好的问题可以激发人的思考，做一个会提好问题的人吧~
