本篇文章针对JDK1.8来说一下HashMap的底层实现。
目录
一、哈希表与哈希冲突
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。
- 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以就产生了冲突,也称哈希冲突.
- 处理哈希冲突，在本文中Hashmap就会产生冲突，解决办法就是数组加链表 ,看下文~。
二、HashMap的实现原理
HashMap 基于 哈希算法实现的，底层是由数组+链表/红黑树构成的。当添加一个元素（key,value）时，首先计算元素key对应的hash值，利用该哈希值计算出在数组中的位置，但是可能存在该数组下标已经存放过元素了，这时就产生了哈希冲突，解决这个问题的方法就是，形成具有相同hash值的链表，挂在该数组下标下。而当链表长度大于8时，链表就转换为红黑树，这样做的目的是增加查找效率，红黑树的转换在了解之后再专门写一下～。
jdk1.8底层的数组是：Node<k,v> 实现了 Map.Entry<k,v>接口源码如下：
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;
}
}
以上源码中有链表结点的定义，获取对应key以及values值同时还有设置values值。以及获取key的hashCode值，equals方法为true的条件是两个key-values键值对的key分别相等值分别相等。
三、hash的计算以及所在数组下标的计算
1.hashCode的计算
源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先就得计算出key的hashCode值,不同的类型的对象hashCode的值的计算也不一样如下：
Integer的计算
源码如下：
@Override
public int hashCode() {
return Integer.hashCode(value);
}
可见Integer重写了hashCode方法，所以该类型返回的是数值本身。
String的计算
源码如下：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
浮点数的计算
浮点数在内存中的存放：
规定float类型有一个符号位（S），有8个指数位（E），和23个有效数字位（M）
double类型有一个符号位（S），有11个指数位（E），和52个有效数字位（M）
浮点数的表示形式为 1.M*2^E,其中1和2是固定的，所以就存M和E
举例将17.625换算成 float型。
首先，将17.625换算成二进制位：10001.101 再将 10001.101 向右移，直到小数点前只剩一位 成了 1.0001101 x 2的4次方（因为右移了4位）。此时 我们的底数M和指数E就出来了：
底数部分M，所以此处底数为 0001101 。指数部分E，实际为4，但须加上127，固为131，即二进制数 10000011
符号部分S，由于是正数，所以S为0.
综上所述，17.625的 float 存储格式就是：
0 10000011 00011010000000000000000
再来转成整型计算就可以
源码如下：
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
Long的计算
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
因为hsah值必须是int型所以对于浮点数和Long就得进行在进行移位运算
String对象的hashCode的计算是根据每一个字符的Ascall值来计算
假设字符串“abc”则对应的hashCode的值为
31*(31*(31*0+97)+98)+99=96354
思考：为什莫要选择31作为优质乘子呢？
1. 数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i，现代的 Java 虚拟机可以自动的完成这个优化。
（32-1) * i =32 * i - i = (i<<5) -i;
2. 选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。
3. 如果选择的较小，这里分析一下质数2。假设 n = 6，然后把质数2和 n 带入上面的计算公式。并且计算公式中次数最高的那一项，结果是2^5 = 32，是不是很小。所以可以说，当字符串长度不是很长时，用质数2做为乘子算出的哈希值，数值不会很大。也就是说，哈希值会分布在一个较小的数值区间内，分布性不佳，最终可能会导致冲突率上升。
那莫选择一个较大的数比如做为乘子会产生什么样的结果呢？我想大家应该可以猜出结果了。就是不用再担心哈希值会分布在一个小的区间内了，因为101^5 = 10,510,100,501。但是要注意的是，这个计算结果太大了。如果用 int 类型表示哈希值，结果会溢出，最终导致数值信息丢失，那么大于101的数我们也就没有必要考虑了。最后，我们再来看看质数31的计算结果：31^5 = 28629151，结果值相对于2和101来说。是不是很合适，不大不小。
笔者是从该篇文章学到的，有兴趣的童鞋可以再去了解哈。
哈希算法之 hashCode 为什么选择数字31作为优质乘子？
2.hash算法
源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
思考：为什么hash的计算不直接传递hashCode值，而是要和右移 16 位的hashCode做异或运算，又为什么要使用 ^ 位异或？
首先看一下get()方法里面的一段代码：
first = tab[(n - 1) & hash]
该代码中的(n-1)&hash就是来获取数组下标的。
假设有一种情况，对象 A 的 hashCode 为 11110111111110001011110001000000 ，对象 B 的 hashCode为0111011100111000101000000100000
假设数组长度（n）是32，也就是 31 和这两个数作&运算 ， 你会发现结果都是0，这样就会产生很多冲突，这肯定不是我们最想要的，很明显也不是一个好的算法。但是如果我们将 hashCode 值右移 16 位，刚好将所有的二进制数对半切开。利用它的前16位和后16位作异或运算，将这个数的全部二进制都用上，这样的话，就能避免我们上面的情况的发生，为什莫不使用与做运算，你想与运算只有1 和 1 才为1，其他的三种条件都是0 也会增加冲突的概率，同样或运算也是如此，明显异或的概率冲突就少一点。
3.对应数组下标的计算
计算出key的哈希值后，由于哈希值比较大，不能作为直接作为数组下标，对哈希值进行(高位运算或者取模运算）然后设为数组中的下标位置）HashMap采用的是高位运算，因为高位运算要比取模运算效率高很多，计算机中会更容易识别位运算，但是对于数组的长度也有要求。如下：
数组下标：hash&(map.size-1) = hash%(map.size)
使用高位运算来求数组下标那么数组的长度必须为2的n次幂。
该处使用的url网络请求的数据。
四 HashMap的大小为什么是2的幂次
如果map长度为2的幂次，那莫map.size - 1的二进制一定为11111…这种形式，进行与运算就看元素的hashcode值的后n位了，但是如果map的长度不是2的幂次，比如为15，那size - 1就是14，二进制为1110，无论与谁和最后一位做&运算一定是0，0001，0011，0101，1001，1011，0111，1101这几个位置就永远都不能存放元素了，空间浪费也就大了。也增加了哈希冲突的发生。减慢了查询效率。所以Hashmap的大小是2的幂次。
五 get()和put()方法
首先看一下get()方法源码：
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) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//取得对应的hash值的第一个Node并且判断是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断第一个Node是不是要找的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//接着判断first后面的的结点是不是要找的
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//遍历后面的链表，找到key值和hash值都相同的Node
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
解释：get一个元素的过程就是，先计算出key的hash找到数组中对应的下标，这个时间复杂度为O(1)，然后通过对该数组下标位置中存放的链表结点进行比较，找到与之相等的key,来获取对应的value，这个的时间复杂度为O(m)，m为该链表的长度。
再者看一下put()方法源码：
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果该数组下标对应的值是空，就新建一个节点插入在该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//下面可能存在哈希冲突
else {
Node<K,V> e; K k;
//判断第一个结点的key是不是与之相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//是否链表已经转为红黑树了，看是否插进红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//循环遍历链表上的所有结点
for (int binCount = 0; ; ++binCount) {
//如果next域为空则生成新的结点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，
//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行resize，扩容table
//如果达到64，那么将冲突的存储结构为红黑树
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;
}
}
//处理具有相等key的结点，新值覆盖旧值
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
/*如果当前大小大于最大限度时，限度原本是size*0.75(在下面解释)*/
if (++size > threshold)
resize();//进行扩容
afterNodeInsertion(evict);
return null;
}
解释：put一个元素的过程就是:
1 判断键值对数组tab[]是否为空或为null，为空则以默认大小进行resize().
2 然后根据键值key计算hash值得到插入的数组下标i，如果tab[i]==null，直接新建节点添加，否则进行3
3 查找该链表上是否有和key相等的结点，没有则直接插入，有则跳出循环，最后用新的values值覆盖旧的values值。在查找的过程中也会分别讨论查找的是红黑树还是链表，当查找的是链表时，会有转换为红黑树的问题，在上面源码可以看见什么时候转换。
六 扩容机制
1 capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
2 loadFactor：负载因子，默认为 0.75。
3 threshold：扩容的阈值，等于 capacity * loadFactor
构造HashMap时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（capacity * loadFactor)，重新调整HashMap大小 变为原来2倍大小。
以下为扩容的代码：
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
//旧表长度为0，表示第一次初始化表
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;
//开始重新hash了
@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;
//原来的hash值新增的那个bit还是0，是0的话存储的索引不变
if ((e.hash & oldCap) == 0) {
//表示新table当前还没有元素
if (loTail == null)
//设置为头节点
loHead = e;
else
//添加到后面
loTail.next = e;
//更新尾节点
loTail = e;
}
//原来的hash值新增的那个bit不为0，存储的索引位置为 j+OldCap
//同上
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//新增bit为 0,该链不为空，将该链的头节点挂在j下标上的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//同上，将新增bit位为1挂在j+oldcap的位置上。
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
解释重新哈希的下标的计算:因为map的长度有要求必须是2的n次幂，所以当扩容为原来的2倍时，有一个简便的计算下标的办法，下标的计算是由hash&长度-1得来的，现在长度变为原来的2倍，意味着2的n次幂就会比原来多一位1，hash值不变，原来做与运算的那几位也不变，所以就看hash向左在多取的那一位，若为1则结果就是原数组下标+原数组的长度（因为2倍了），为0,则就是原来的数组下标，也就是上面源码最后存头节点的位置的地方.