HashMap的源码，实现原理，底层结构？

参考解答

java中HashMap的内部组成是数组+链表的数据结构，数组的默认大小是16：
当调用map.put(k, v) 时：

1. 首先会计算k的hashCode值，综合其高位，形成hash值
2. 再将hash值换算为数组的下标（取值从0-15）
3. 遍历数组该下标的Entry链，检查是否有旧key.equals(新key)的Entry 存在
4. 如果存在，用新值覆盖旧值，返回旧值
5. 如果不存在，创建新的Entry(hash,k,v,next) 其中next指向原Entry链中第一个Entry，如果没有旧Entry，next为null
6. 将新的Entry存入数组该下标中
7. HashMap有一个阈值，默认为0.75也就是说当它的初始大小是16时，这个阈值为12，当发生hash碰撞时（数组下标已有Entry），HashMap会检查当前存储的元素个数是否超过了阈值，如果是，需要对集合内所有元素重新计算hash，让它们重新分布

HashMap这样设计的目的是让集合中的数据查询效率得到极大提高：比如，List.contains(Object o)时间复杂度是O(n)，而HashMap.containsKey(Object k)时间复杂度只有O(1)

注意，以上是用JDK 7.0 为例进行分析，JDK 8.0中实现又做了变化