引言
唉！
金九银十转眼已过，
面试现场不知所措；
不懂原理是我过错，
今日弥补只为求过。
======================================================
小学弟呀，小学弟！
平时不努力，
全来学押韵；
近来找工作，
处处不如意；
闲来送你一篇原理文，
让你对HashMap不再愁。
=======================================================
话不多说，就让我们开始HashMap的原理讲解吧。
正文
Hash表
HashMap其实就是用Hash表这种数据结构来实现的；如果你对Hash表了如指掌，我相信，对于HashMap你已经成功一半了。那我们就先来说说什么是Hash表吧。
先来举个例子：
在上学时我们都排过队，当老师没有做要求的时候，大家都会随便站，关系好的站在一起等等没有统一规则，甚至还有插班的行为。当一个老师从这个长长的队列时找人时，往往都是从第一个开始找，直到找到他想找的人为止。这种方式就可以看做链表或者数组，每次都需要逐个遍历筛选。
这时候教导主任来了，说这样排队太乱了，于是制定了排队规则，必须按照年级+班级+自己的序号顺序站队并记住这个序号。当老师再次找一个陌生的同学时，只要对教导主任说我要找二年级五班006同学，教导主任通过信息就可以直接找到张三同学站的位置，并不需要遍历了。这种方式就是Hash表的方式进行添加或者查找的。
我们来解释一下上面的例子：
例子中所提到的二年级五班006就是Hash值：根据key值（例子中的某个学生）计算得出一个固定长度的目标值，而这个目标值就叫做Hash值；
教导主任所制定的排队规则就是所制定的一个Hash函数：用key怎么计算Hash值的呢？就是通过Hash函数的计算；在项目中每一个hash函数的实现都是不一样的，而大部分hash函数的具体实现是非公开的，因为可能会造成安全问题。
简单的来说，哈希表是一种表结构，我们可以直接根据给定的key值计算出目标位置。在工程中这一表结构实现通常采用数组。
那么一个好的Hash函数具备什么样的特性呢？
1，同一性：也可以叫做散列性，即每一个Hash值都要尽可能的均匀；因为存储在数组时要尽可能的均匀存储。（也可以说每个数组下标的命中率尽可能相同。）
2，遵循雪崩效应：当有微小的key值输入时，Hash值要发生巨大的变化；有些Hash函数是为了进行加密使用的（如https协议）遵循这条可以保证更高的安全性。
3，尽量避免Hash冲突：当我们要把十个苹果放到九个抽屉里的时候，总会有至少两个苹果放到同一个抽屉里（抽屉原理），存在两个苹果的抽屉，我们就可以叫它Hash冲突，或者Hash碰撞；同样因为我们Hash值的长度是固定的，而key可以是任意值，所以总会造成两个key值的hash值相同，这种情况叫做Hash冲突，Hash冲突是不可避免的，但我们要尽可能的减少冲突。
现在看看我们例子中教导主任制定的Hash函数是不是可以被我们吐槽一番呢。
所以，Hash表他的查询速度快，一个良好的Hash表时间复杂度可以达到o(1)，对于庞大的海量数据，这种查找速度还是非常惊人的。
HashMap原理
JDK1.7
了解了Hash表，我们再来看HashMap，我们先来分析JDK1.7中的HashMap的实现：
JDK1.7中的HashMap采用的是数组加链表的形式进行存储的，数组每个下标所对应的位置我们都可以叫做一个hash桶。
put过程：
public V put(K key, V value) {
if(key == null) //1
returnputForNullKey(value);
inthash=hash(key); //2
int i = indexFor(hash, table.length); //3
for(Entry e = table[i]; e != null; e = e.next) {//4
Object k;if(e.hash ==hash&& ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; e.value = value; e.recordAccess(this);returnoldValue;
} } modCount++; addEntry(hash, key, value, i); //5
returnnull;
}
1，key不能为空：
在存储元素前，HashMap将判断元素的key是够为空，如果为空，直接返回。
2，计算Hash值：
finalinthash(Object k){
inth =0;
if(useAltHashing) {
if(kinstanceofString) {//2.1
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// 2.2
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
通过hash源码我们看到：
2.1，这里JDK1.7对String类型的元素进行了重新hash的过程，为什么String要重新hash呢？
要从一篇邮件开始说起...在JDK1.7出现后，Tomcat发布了一篇邮件，里边写到了JDK1.7中HashMap的一个潜在安全漏洞。
mail-archives.apache.org/mod_mbox/to…4EFB9800.5010106@apache.org
这篇邮件中，因为Tomcat使用了Hashtable存储了HTTP请求参数，由于String的hash算法是公开的，可能会导致一些专业人员可以获取到无数个hashcode都相同的key值，当这些请求参数同时请求后，就会使hash表退化成链表，使cpu存在大量的链表，由于链表查找的时间复杂度O(n)，查找速度会受到很大的影响，所以会遭受DDos攻击。
当然Tomcat也给出了解决方案，而随后在JDK1.7的版本后也修复了这个bug。
2.2，我们看在2.2处进行了一堆的>>>和^操作，原因就是为了要增加它的同一性，让命中每个数组下标的概率相同。
3，获得数组下标：
staticintindexFor(inth,intlength){
returnh & (length-1);
}
在步骤2中，我们得到了Hash值，那么怎么通过hash值来决定存在哪个桶里呢？
可能有些人我们会想到取余操作，但是取余操作有两个缺点：1，相比于java的&运算速度相对慢一点；2，负数取余还是负数，数组下标（桶的位置）不能为负数。
所以Java采用的是按位与，这样就可以根据数组长度和Hash值计算出该元素桶的具体位置。
采用这种方式计算数组下标也是有损失的，如果length不为2的次幂，那么每次按位与时，为零的那一位永远为零，导致有些下标永远无法得到，如下图。
HashMap为了解决这个问题，如果你的值不为2的幂，那么在构造函数中HashMap将找到大于等于我们赋给HashMap的初始容量的最小2的幂。所以为了减少这次转换，我们初始化HashMap的容量时一定要为2的幂。
4，我们接着向下看注释4的地方：这里就是做了一个循环链表，去插入元素这么一个操作。
5，我们能看到这里调用了一个addEntry()函数，这个函数是干什么的呢，我们点击去：
voidaddEntry(inthash, K key, Vvalue,intbucketIndex){
if((size >= threshold) && (null!= table[bucketIndex])) {
resize(2* table.length);
hash = (null!= key) ? hash(key) :0;
bucketIndex = indexFor(hash, table.length); } createEntry(hash, key,value, bucketIndex);
}
我们大致能了解到，这个其实就是扩容机制，知道这些就可以了，接着我们讲讲具体是怎么扩容的。
threshold：即阔值，当数组的使用大小大于等于这个值时，则将数组扩容。threshold = capacity（数组容量）* load_factor（负载因子）
load_factor（负载因子）：默认为0.75，官方解释说：在时间和空间成本之间做了权衡后，得出的0.75这个值。
进入到if后，执行了resize()这个函数，这个函数可以说是一切根源的罪魁祸首。
我们点resize()进去看看
voidresize(intnewCapacity){
Entry[] oldTable = table;intoldCapacity = oldTable.length;
if(oldCapacity == MAXIMUM_CAPACITY) {//MAXIMUM_CAPACITY默认是2的30次幂，所以基本不会到达这一容量
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
voidtransfer(Entry[] newTable,booleanrehash){
intnewCapacity = newTable.length;
for(Entry e : table) {
while(null!= e) {
Entry next = e.next;if(rehash) {
e.hash =null== e.key ?0: hash(e.key);
}inti = indexFor(e.hash, newCapacity);
e.next = newTable[i]; newTable[i] = e; e = next; } } }
这两个方法主要是rehash操作，然后将数组中的链表使用头插法重新插入到了新的数组中，其实这在单线程中是没有问题的，但是如果多个线程同时操作的时候，将会出现循环链表的情况。当再次访问这个循环链表时，就会出现死循环，cpu100%的情况，虽然HashMap中明确表示它并不是线程安全的，但还是有人会用到它，造成这样的问题。
这里给大家分享一篇文章，里边明确说明了为什么会产生循环链表：coolshell.cn/articles/96…
这就是JDK1.7中的HashMap的put过程，接下来我们简单说一说get过程：
publicVget(Object key) {
if(key ==null)
returngetForNullKey();
Entry entry = getEntry(key);returnnull== entry ?null: entry.getValue();
}
这是JDK1.7的get方法，当key为空时返回null，否则调用getEntry()函数：
final EntrygetEntry(Object key){
inthash = (key ==null) ?0: hash(key);
for(Entry e = table[indexFor(hash, table.length)];
e !=null;
e = e.next) { Object k;if(e.hash == hash &&
((k = e.key) == key || (key !=null&& key.equals(k))))
returne;
}returnnull;
}
就是计算key的hash值，然后循环该桶下的链表，查找数据。
JDK1.8
上面我们说到，JDK1.7的HashMap存在着安全隐患，如多线程下会可能出现循环链表（这完全是用户自己的锅，因为Java团队明确表示HashMap不是线程安全的）。
所以JDK1.8的HashMap在结构上使用了数组加链表加红黑树的数据结构，防止当链表过长时导致搜索时间退化到o(n)。
当链表的元素达到了8的时候，将会使用红黑树代替链表，选择8的原因是因为Java团队解释说：
大致上说，他们采用了泊松分布的原理（大学数学我们应该都学过），当链表达到8时只有0.00000006的概率。
在hash()函数上也做了改进：
staticfinalinthash(Object key){
inth;
return(key ==null) ?0: (h = key.hashCode()) ^ (h >>>16);
}
另外一个比较明显的改进是在resize()这个函数中从之前的头插法改为了尾插法，这样在多线程的情况下就不会存在循环链表，进而导致死循环的情况了。但是值得注意的是，HashMap任然不是线程安全的，这在HashMap注释中就已经明确说明了。
结束
这就是HashMap的比较重要的部分，也是面试过程中在问到HashMap时比较常见的问题。如果还有什么没有提到的，大家可以在评论中告诉我，我会尽量补充的。
作者：张子江
链接：https://juejin.im/post/6880712401143595021
来源：掘金
网友评论