背景

最近忙着面试，把学习的东西，通过博客沉淀下来，一方面加深自己的理解，另方面方便以后自己再次复习。HashMap 是面试喜欢问的问题，那么HashMap的原理是什么呢？

---

HashMap原理

HashMap的数据结构是 数组+链表。

数组默认大小等于16，这个数组也称Hash桶。
链表是存放Hash冲突的entry对象的。这里该提到数据结构的hash冲突的几种解决方法，hashMap采用的是链地址法。

hash冲突解决的常见办法：

1.开放定址法
2.再哈希法
3.链地址法
4.建立公共溢出区

怎么处理hash冲突

当我们向HashMap put一个KV时候，先对KEY做hashCode,为了减少hash冲撞的机会，还经过了扰动函数计算，让hash的更均匀。jdk7在这里扰动了4次而JDK8，做了简化。

计算出来的hashcode与数组的容量进行与运算代替模运算， 因为hash桶只有16个，因此出现hash冲撞的可能性会增大。通过位运算后的值即为key-value存放的位置。当出现hash冲撞的时候，hashmap会将新进来的值塞进链表的尾部，当hash冲撞的机会高的时候，链表的长度也会增大，我们知道链表的查询的时间复杂度是N，jdk8在这里做了改进，具体为当链表长度大于8的时候，会转为红黑树，红黑树的特点是平衡二叉树，查询的时间复杂度是logn.

怎么扩容呢？

当hashMap的数组容量超过自己的0.75的时候，也就是默认容量16*0.75=12个的时候，则会进行一次扩容，这里的0.75就是加载因子，12就是阈值。
扩容的复杂度很高，先扩容，再移动旧的数组的值到新的数组去，性能会很低,所以我们要减少hashmap的扩容次数，初始化的时候，尽量设置初始容量。接下来，我们看看扩容的过程，先复制一个原来2倍容量的数组，然后重新计算key
的hash值，将旧数据搬到新的数组中去，这时候如果有新的数据进来也会插入尾部，会出现争抢位置的并发问题，而HashMap是线程不安全的。

hashMap线程安全的实现方式

线程安全的hashMap，使用concurrentHashMap,这个类是基于分段锁。实现HashMap线程安全还有另外一种方法，Collections.synchronized(new HashMap()),但是这种是全部方法加锁的，跟hashtable一样，锁粒度大，效率不好。