一、底层原理
HashMap底层实现是数组+链表，用来存储
二、HashMap结构
HashMap是我们非常常用的数据结构，由数组和链表组合构成的数据结构。
大概如下，数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node
因为他本身所有的位置都为null，在put插入的时候会根据key的hash去计算一个index值。
就比如put（”帅丙”，520），我插入了为”帅丙”的元素，这个时候我们会通过哈希函数计算出插入的位置，计算出来index是2那结果如下
hash（“帅丙”）= 2
我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是”帅丙”和”丙帅”我们都去hash有一定的概率会一样，就像上面的情况我再次哈希”丙帅”极端情况也会hash到一个值上，那就形成了链表
每一个节点都会保存自身的hash、key、value、以及下个节点，我看看Node的源码
三、扩容机制
数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。
什么时候resize呢？
有两个因素：
- Capacity：HashMap当前长度。
- LoadFactor：负载因子，默认值0.75f。
怎么理解呢，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的。
扩容？它是怎么扩容的呢？
分为两步
- 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
- ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
为什么要重新Hash呢，直接复制过去不香么？
是因为长度扩大以后，Hash的规则也随之改变。
Hash的公式（1.7）—-> index = HashCode（Key） % （Length - 1）
Hash的公式（1.8）—-> index = HashCode（Key） & （Length - 1）
原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。
扩容前：
扩容后： 
在JDK1.7的时候是先扩容后插入的，这样就会导致无论这一次插入是不是发生hash冲突都需要进行扩容，如果这次插入的并没有发生Hash冲突的话，那么就会造成一次无效扩容，但是在1.8的时候是先插入再扩容的，优点其实是因为为了减少这一次无效的扩容，原因就是如果这次插入没有发生Hash冲突的话，那么其实就不会造成扩容，但是在1.7的时候就会造成扩容
负载因子为啥是0.75
- 负载因子是1.0
当负载因子是1.0的时候，意味着会出现大量的Hash的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。
负载因子过大，虽然空间利用率上去了，但是时间效率降低了。
- 负载因子是0.5
后果：负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。
但是，此时空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。
总之，就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。
- 负载因子0.75
经过前面的分析，基本上为什么是0.75的答案也就出来了，这是时间和空间的权衡。当然这个答案不是我自己想出来的。答案就在源码上，我们可以看看：
As a general rule, the default load factor (.75) offers a good tradeoffbetween time and space costs. Higher values decrease the space overheadbut increase the lookup cost (reflected in most of the operations of theHashMap class, including get and put).
意思就是说：负载因子是0.75的时，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。
四、java8改成尾插入
java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。但是，在java8之后，都是所用尾部插入了。
举个例子，我们现在往一个容量大小为2的put两个值，负载因子是0.75是不是我们在put第二个的时候就会进行resize？
2*0.75 = 1 所以插入第二个就要resize了
现在我们要在容量为2的容器里面用不同线程插入A，B，C，假如我们在resize之前打个短点，那意味着数据都插入了但是还没resize那扩容前可能是这样的。
我们可以看到链表的指向A->B->CW
Tip：A的下一个指针是指向B的
因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
就可能出现下面的情况，大家发现问题没有？
B的下一个指针指向了A
一旦几个线程都调整完成，就可能出现环形链表
如果这个时候去取值，悲剧就出现了——Infinite Loop。
因为java8之后链表有红黑树的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。
使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
就是说原本是A->B，在扩容后那个链表还是A->B
Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
那是不是意味着Java8就可以把HashMap用在多线程中呢？
我认为即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
五、java8中对hash算法和寻址算法的优化
1、hash算法优化
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
如上，hash算法是对象key值的（hashCode）异或（hashCode右移16位），右移16位，为何要做这种优化，hash算法是hash & (n - 1)，由于（n-1）的二进制值的高16位大概率都是0(n是hashMap的大小，不太可能超过2的16次方)，为了让hash值的高16位参与运算，所以hash算法中将hash值的高16位和低16位进行了异或运算，使得高低16位都参与了hash计算，减少hash碰撞的概率。
2、寻址算法优化
java8中对寻址算法进行了优化，之前在对key进行hash(key)计算时，采用的是取模运算，而优化后采用的是寻址算法，即：(n-1) & hash 『n为数组长度』
为什么要使用寻址算法呢？首先 「hash & (n-1)」 效果跟 hash 对 n 取模的效果是一样的， 但是&与运算的性能要优于hash对n取模。
六、初始化大小
1、为啥是2的幂（实现均匀分布）
在JDK1.8的 236 行有1<<4就是16，为啥用位运算呢？
这样是为了位运算的方便，位与运算比算数计算的效率高了很多，之所以选择2的幂，是为了服务将Key映射到index的算法，实现均匀分布。
我前面说了所有的key我们都会拿到他的hash，但是我们怎么尽可能的得到一个均匀分布的hash呢？
是的我们通过Key的HashCode值去做位运算。
我打个比方，key为”帅丙“的十进制为766132那二进制就是 10111011000010110100
我们再看下index的计算公式：index = HashCode（Key） & （Length- 1）
15的的二进制是1111，那10111011000010110100 &1111 十进制就是4
之所以用位与运算效果与取模一样，性能也提高了不少！
因为在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。
只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。这是为了实现均匀分布。
2、自定义初始化大小
为了保证任何情况下Map的容量都是2的幂，HashMap在两个地方都做了限制。
首先是，如果用户制定了初始容量，那么HashMap会计算出比该数大的第一个2的幂作为初始容量。
例如：指定初始化大小是12，实际上map初始化的大小还是16，但是如果初始化的大小是8，那实际上map的大小就是8。
另外，在扩容的时候，也是进行成倍的扩容，即4变成8，8变成16。
七、重写hashCode方法
为啥我们重写equals方法的时候需要重写hashCode方法呢
因为在java中，所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。
在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样
- 对于值对象，==比较的是两个对象的值
- 对于引用对象，比较的是两个对象的地址
大家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。
我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？
equals 是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。
不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，这不是完犊子嘛。
八、线程安全
一般都会使用HashTable或者ConcurrentHashMap，但是因为前者的并发度的原因基本上没啥使用场景了，所以存在线程不安全的场景我们都使用的是ConcurrentHashMap。
HashTable我看过他的源码，很简单粗暴，直接在方法上锁，并发度很低，最多同时允许一个线程访问，ConcurrentHashMap就好很多了，1.7和1.8有较大的不同，不过并发度都比前者好太多了。
九、总结
HashMap常见面试题：
- HashMap的底层数据结构？
- HashMap的存取原理？
- Java7和Java8的区别？
- 为啥会线程不安全？
- 有什么线程安全的类代替么?
- 默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
- HashMap的扩容方式？负载因子是多少？为什是这么多？
- HashMap的主要参数都有哪些？
- HashMap是怎么处理hash碰撞的？
- hash的计算规则？
若有收获，就点个赞吧
0 人点赞
