这是我参与新手入门的第3篇文章

往期回顾

上一期我们讲了Hash是什么，以及遇到Hash冲突的解决方法有哪些，而HashMap又是用的什么方法解决冲突。不了解的小伙伴可以走这两个链接跳转

1. juejin.cn/post/698253… 中篇章
2. juejin.cn/post/698172… 上篇章

再述

HashMap的实现原理

首先有一个数组，它的每一个元素存储的都是一个链表

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。

当添加一个元素（key-value）时，首先计算key的hash值，然后把key插入到数组中，如果存在同一hash值，那么将存在这个桶下

约定前面的数组结构的每一个格格称为桶

==hashcode相同，值不一定相同，两个对象equals相等，那么这两个对象的HashCode一定也相同==

先用hashcode比较得出数组的位置，然后用equals来比较是否相等，也就是用equals筛选

hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表中8个位置会有很多数字了，1中可能有20个数字，存101个数字时，他先查hashcode值对应的位置，假设为1，那么就有20个数字和他的hashcode相同，他只需要跟这20个数字相比较(equals)，如果每一个相同，那么就放在1这个位置，这样比较的次数就少了很多，实际上hash表中有很多位置，这里只是举例只有8个，所以比较的次数会让你觉得也挺多的，实际上，如果hash表很大，那么比较的次数就很少很少了。

用个例子说明：上面说的hash表中的8个位置，就好比8个桶，每个桶里能装很多的对象，对象A通过hash函数算法得到将它放到1号桶中，当然肯定有别的对象也会放到1号桶中，如果对象B也通过算法分到了1号桶，那么它如何识别桶中其他对象是否和它一样呢，这时候就需要equals方法来进行筛选了。

为什么equals方法重写的话，建议也一起重写hashcode方法？

有个A类重写了equals方法，但是没有重写hashCode方法，看输出结果，对象a1和对象a2使用equals方法相等，按照上面的hashcode的用法，那么他们两个的hashcode肯定相等，但是这里由于没重写hashcode方法，他们两个hashcode并不一样，所以，我们在重写了equals方法后，尽量也重写了hashcode方法，通过一定的算法，使他们在equals相等时，也会有相同的hashcode值。

HashMap的底层结构图

由下图可知，链表长度达到8时，或者hash表中所有元素个数是64个之后，链表结构升级为红黑树

这里我重点讲一下HashMap的Put过程

HashMap的Put过程

1. map.put（“key”，“value”）

2. 把key经过hash计算得出hash值

3. hash值进行一个扰动函数，使它更加散列，目的是为了减少hash冲突（为什么减少hash冲突看上面）

4. (构造出)存放在Node节点中

5. 经过一个路由寻址

   ==路由寻址公式：（capacity.length-1）& node.hash值== ， 意思就是数组的容量 – 1是因为数组是从0开始，并且数组容量一般都是2的次方数，因为它转换成2进制 15 是1111 、32是11111，然后 与 上一个node节点的hash值

   eg：如果hash是1122， capacity 是 16，0000 0000 1111 & 0100 0110 0010 =>得出 0000 0000 0010 =》得出转为十进制 得出是2，所以存在数组下标为2的地方

   这里的与运算其实就是对大小取余，可以转换成 16是size，1122是key经过计算的hash值， 1122 % 16  = 2 

   底层用的是 >>> 异或运算没有用取余，是因为 异或比取余快

总结

1. 其实有很多还没有讲到，并且源码没有深入，后面争取在出一篇专门针对源码的理解
2. HashMap的数据结构很经典，很适合新手入门学习
3. 数组与链表是需要掌握精通的，在工作上是频繁用到
4. HashMap扩容展开来说会非常大，这个也挖一个坑，后期过来填