HashMap中put与get的实现原理

HashMap中put与get的实现原理

hashMap底层是hash表（散列表的）的数据结构
hash表是一个数组与链表的结合体。
hash表将数组查询快与链表增删快的优势结合到了一起。

通过查看hashMap的源代码我们可以看出，hashMap底层是一个名字叫table的Node数组。

table数组中存放的是Node节点。
那么Node节点中存放了什么呢？（看下图）

看图可以知道，Node节点中存放了四个东西：
1、int hash :hash值，哈希值是key的hashcode()方法的执行结果。
哈希值通过哈希函数可以转换成table数组的下标。
2、key : 存入map的键
3、value :存入map的值
4、Node<k,v> : 下一节点的内存地址。

具体结构如下图所示：

map.put(Key,value)的实现原理（存）

1、先将key和value封装到Node节点中

2、底层会调用key的hashcode()方法，通过hash函数将hash值转换为数组下标，下标位置上如果没有任何元素，就把该Node添加到该位置上（该下标处）

如果该下标处对应的位置上已经存在元素或链表（多于一个元素变成链表），那么就会拿着新节点的key与链表上的每一个人节点中的key进行equals。
1、 如果所有对比（equals)都返回false,那么这个新节点将会被添加到链表的尾部。
2、 如果其中有一个对比（equals)返回true，那么这个节点上的value将会被新节点的value覆盖。

注：在JDK8之前是将新节点添加到头部（头插法）

以上就是hashMap存的原理。

map.get(Key)的实现原理（取）

1、底层会调用key的hashcode()方法，通过hash函数将hash值转换为数组下标，通过数组下标快速定位到数组的指定位置上，如果这个位置上没有任何元素，那么返回null。

2、如果这个位置上有单向链表（该位置上有元素），那么会拿着我们get(key)中的key和单向链表中的每个节点的key进行equals，如果说所有的equals都返回false，那么这个get方法返回false。

3、只要其中有一个节点的key和参数key的equals对比的结果返回true,那么这个节点的value就是我们想要找的value，get方法返回这个value.

以上就是hashMap取的原理。

为什么Hash表的增删效率和查询效率都很高呢？

看了上面的图大家应该就知道了，因为hash表结合了数组与链表两个结构的优势，通过数组可以快速定位到指定的位置，在利用链表的特点进行节点的增删，这样就使得hashMap的查询与增删都具有很高的效率。

但是hash表并没有将查询与增删的效率发挥到极致！！！
hash表相比于单纯的数组来说，并没有数组的查询效率高。
hash表相比于单纯的链表来说，并没有链表的增删效率高。

为什么放在HashMap集合中的元素要重写equals方法？

1、因为如果不重写equals的话，比较的是两个对象的内存地址，但是我们要比较的是内容，而不是内存地址，所以需要重写equals方法。

HashMap集合key的存储特点是：无序，不可重复。

1、为什么无序？
因为不一定放到table数组的哪个下标处（key通过hashcode()运算得到的hash值经过hash函数的运算得出的下标值不确定！）
2、不可重复是怎么保证的？
equals方法来保证hashMap中的key不可重复,如果key重复了，相应的value值将会被覆盖！！

注意：t同一个单向链表中的hash值是相同的。

注意：t同一个单向链表中的key与key的单项链表中equals方法返回的是false

HashMap使用不当时无法发挥其性能

假设所有的hashcode方法返回值为固定的某个值，那么就会导致hash表变成纯单向链表，这种情况就是散列分布不均匀！

那么假设将hashcode方法返回值都设成不一样的值可以吗？会出现什么问题？
那这样就会变成一维数组了，没有链表的概念了，也是散列分布不均匀！！

想要使得散列分布均匀，需要在重写hashcode时使用一定的技巧。