现在很多公司面试都喜欢问java的HashMap原理，特在此整理相关原理及实现，主要还是因为很多开发集合框架都不甚理解，更不要说各种其他数据结构了，所以造成面子造飞机，进去拧螺丝。
1.哈希表结构的优势？
哈希表作为一种优秀数据结构
本质上存储结构是一个数组，辅以链表和红黑树
数组结构在查询和插入删除复杂度方面分别为O(1)和O(n)
链表结构在查询和插入删除复杂度方面分别为O(n)和O(1)
二叉树做了平衡 两者都为O(lgn)
而哈希表两者都为O(1)
2.哈希表简介
哈希表本质是一种(key,value)结构
由此我们可以联想到，能不能把哈希表的key映射成数组的索引index呢？
如果这样做的话那么查询相当于直接查询索引，查询时间复杂度为O(1)
其实这也正是当key为int型时的做法 将key通过某种做法映射成index，从而转换成数组结构
3.数据结构实现步骤
1.使用hash算法计算key值对应的hash值h(默认用key对应的hashcode进行计算(hashcode默认为key在内存中的地址)),得到hash值
2.计算该(k,v)对应的索引值index
索引值的计算公式为 index = (h % length) length为数组长度
3.储存对应的(k,v)到数组中去，从而形成a[index] = node<k,v>,如果a[index]已经有了结点
即可能发生碰撞，那么需要通过开放寻址法或拉链法(Java默认实现）解决冲突
当然这只是一个简单的步骤，只实现了数组 实际实现会更复杂
hash表 数组类似下图
| --- | null | null | <10,node1> | <27,node2> | null | null | null | null |
| --- |
jdk 1.7以及之前的结构类似如下：
jdk 8中的结构如下：
两个重要概念
哈希算法
h 通过hash算法计算得到的的一个整型数值
h可以近似看做一个由key的hashcode生成的随机数，区别在于相同的hashcode生成的h必然相同
而不同的hashcode也可能生成相同h，这种情况叫做hash碰撞，好的hash算法应尽量避免hash碰撞
(ps:hash碰撞只能尽量避免，而无法杜绝,由于h是一个固定长度整型数据,原则上只要有足够多的输入，就一定会产生碰撞)
关于hash算法有很多种，这里不展开赘述，只需要记住h是一个由hashcode产生的伪随机数即可
同时需要满足key.hashcode -> h 分布尽量均匀(下文会解释为何需要分布均匀)
可以参考https://blog.csdn.net/tanggao1314/article/details/51457585
解决碰撞冲突
由上我们可以知道，不同的hashcode可能导致相应的h即发生碰撞
那么我们需要把相应的<k,v>放到hashmap的其他存储地址
解决方法1：Hash冲突的线性探测开放地址法
通过在数组以某种方式寻找数组中空余的结点放置
基本思想是：当关键字key的哈希地址p=H（key）出现冲突时
以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，
解决方法1：链地址法（JDK采用的哈希冲突解决方法及JDK7的源码，JDK8差异大）
通过引入链表 数组中每一个实体存储为链表结构，如果发生碰撞，则把旧结点指针指向新链表结点，此时查询碰撞结点只需要遍历该链表即可
在这种方法下，数据结构如下所示
int类型数据 hashcode 为自身值
在JAVA中几个细节点
1.为什么需要扩容？扩容因子大还是小好？
2.当从哈希表中查询数据时，如果key对应一条链表,遍历时如何判断是否应该覆盖？
这里提供一个范例
public class Student {
//学号
public int student_no;
//姓名
public String name;
@Override
public boolean equals(Object o) {
Student student = (Student) o;
return student_no == student.student_no;
}
}
通常情况下我们像上图一样期望通过判断两个Student的学号是否是否为同一学生
然而在使用map或set集合时产生出乎意料的结果
当我们重写hashcode()时
@Override
public int hashCode() {
return Objects.hash(student_no);
}
可以看到现在可以正常使用集合框架中的一些特性
3.为什么在HashMap中数组的长度length = 2^n（初始值为16），即2的n次 ?
4.HashMap的红黑树在哪里体现呢？
5.扩容是如何触发的?
在正常的Hash算法下，红黑树结构基本不可能被构造出来，根据概率论，理想状态下哈希表的每个箱子中，元素的数量遵守泊松分布，通俗易懂的解释泊松分布
（即除非hash算法有问题，否则单位时间内发生冲撞的概率是可以估算出来的）:
P(X=k) = (λ^k/k!)e^-λ,k=0,1,...
当负载因子为 0.75 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下:(参考https://blog.csdn.net/Philm_iOS/article/details/81200601)，下述分布来自源码文档
> * Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million最后和JDK 7不同的是，JDK1.8中新增了一个实现了Entry接口的内部类Node<K,V>，即哈希节点。
参考：
JDK 8中hashmap的实现解析：https://blog.csdn.net/lch_2016/article/details/81045480
相关HashMap相关的面试问题：https://blog.csdn.net/suifeng629/article/details/82179996