HashMap(Java8以前)：数组+链表

HashMap(Java8及以后)：数组+链表+红黑树

 

 

如果存入的key是一个自定义的类，该怎么办呢？（重新equals和hashcode）

进入源码：

可以看到key是由Set来存的，就不能够有重复数据了

values用Collection来存，可以重复

内部存储结构是[是一个MapEntry的实现]

数组被分为一个个的bucket，通过hash值决定了键值对在这个数组的寻址，hash值相同的键值对则以链表的方式存储

 

如果链表的大小超过了一定数值，默认8，则会转化为红黑树

当链表的大小小于一定数值，默认6，则会由红黑树转换回链表

再看HashMap 的构造函数，可以发现它仅仅只是为一些相关的成员变量赋上了初始化值，所以可以大胆猜测：HashMap的加载是懒加载（lazy-load的模式）

接下来看它的put方法

调用putVal，点进去，发现最初几行调用resize()方法

然后回到putVal方法，继续分析，这一步是得到经过hash之后的值来确定位置，如果Node<K,V>[] tab这里面没有，就新建一个，放进去

如果发现在tab[i]中存在键值对，并且key和传进来的key相同，就直接替换数组中的元素

然后再判断是否是树化后的节点，如果是的话，就按照树的方式尝试存储键值对进行存储

如果都不是，那么就直接在链表后面新建一个，但是如果binCount超过了阈值，那么就进行树化

 

总结HashMap的put方法逻辑：

1.如果HashMap未被初始化过，则初始化（也就是进行resize（）操作）

2.对key进行一个hash操作，并且和数组长度减一后进行与操作，计算出下标

3.如果没有碰撞，就直接放入桶中

4.如果碰撞了，就以链表的方式链接到后面（拉链法）

5.如果链表长度超过阈值，就把链表转成红黑树

6.如果链表长度低于6，就把红黑树转回链表

7.如果节点已经存在，就替换旧值

8.如果桶满了（容量16*加载因子0.75），就需要resize（扩容2倍后重排）

 

HashMap如何有效减少碰撞？

扰动函数：促使位置分布均匀，减少碰撞几率

使用final对象，并且采用合适的equals()和hashCode()方法

 

HashMap中hash值的求法

先取到key的hashCode，再在其基础上进行移位，将高16位移动到低16位上面，再与原先的数据进行异或运算

这样做的好处是什么？

第二步能够综合高16位和低16位的数据情况，以此加大低位的随机性，而且低位也相当于变相保存了高位信息。主要是从速度、质量、功效来考虑的

第三步中，（n - 1）相当于是桶（或者数组）的长度【？】，这一步的运算就相当于是用hash值与长度取模，但是这个效率更加快。

[n–1的原因是:因为初始状态是2的n次方，如果减一个1的话，它的位数就正好表示n钟情况，比如16-1就15，15的话就是0000 1111，有4位，2的4次方，就是16钟情况了，刚好可以把他们放到16个桶里面去]

更快的原因是由于hashMap的长度是2的n次方，那为什么是2的n次方而不是传入的长度呢？

其实在传入初始化capacity（容量）值的时候，还额外调用了一个方法：tableSizeFor

它的作用其实就相当于是将传入的参数转换成离它最近的2的倍数的值

为了方便在进行hash运算定位桶的时候能实现用上述的与操作，代替取模，从而获得更好的效果.

这儿相当于一道非常漂亮的算法题：输入一个int类型的数，返回比某个2的倍数大且最接近的那个数

附： 

按位或后赋值   |=   

无符号右移     >>>

 

为什么不直接用获取到的key.hashCode()来访问数组呢？

因为hashCode()方法返回的是int类型，而其范围是-2147483648~+2147483647（即正负2的16次方），然而一个40亿长的数组，内存是不容易存储的，更何况默认的hashMap在扩容之前大小才16，所以直接拿散列值来用是不现实的

 

HashMap是如何扩容的？

首先了解一个变量DEFAULT_LOAD_FACTOR（默认负载因子），意思是当一个HashMap填满了75%的bucket时，就会自动扩容

threshold 阈值 

原理是通过创建原来HashMap大小x2的bucket数组，来重新调整map的大小

并将原来的对象放入到新的bucket数组中去（这个过程叫做rehashing，这个算法挺有意思的，挖个坑，有心情就来填）

 

HashMap扩容会存在哪些问题？

多线程环境下，调整大小会存在条件竞争，容易造成死锁

rehashing是一个比较耗时的过程

 

如何让HashMap转为线程安全？

可以通过

让hashMap线程安全。其原因是添加了一个互斥对象成员，对里面的public方法使用synchronized进行加锁

效果上和HashTable差不多

为什么HashMap线程不安全？

可能造成Bucket中链表形成环形链表，导致后续的Map.get操作可能会造成无限循环，导致CPU的100%占用。