关注△mikechen的互联网架构△，10年+BAT架构经验倾囊相授
大家好，我是 mikechen | 陈睿 。
一线资深java工程师明确了需要精通集合容器，尤其是今天我谈到的HashMap。
HashMap在Java集合的重要性不亚于Volatile在并发编程的重要性(可见性与有序性)。
我会重点讲解以下9点：
首先我们从数据结构的角度来看：HashMap是:数组+链表+红黑树（JDK1.8增加了红黑树部分）的数据结构，如下所示:
这里需要搞明白两个问题：
问题一：数据底层具体存储的是什么？
问题二：这样的存储方式有什么优点呢？
1.核心成员
讯享网
2.Node数组
从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。
讯享网
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
1.哈希表来存储
HashMap采用哈希表来存储数据。
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构，只要输入待查找的值即key，即可查找到其对应的值。
哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
2.哈希函数
哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。
3.核心问题
建立一个哈希表之前需要解决两个主要问题：
1)构造一个合适的哈希函数,均匀性 H（key）的值均匀分布在哈希表中
2)冲突的处理
冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。
4.哈希冲突：链式哈希表
哈希表为解决冲突，可以采用地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
链地址法，简单来说，就是数组加链表的结合,如下图所示：
//计算数组槽位
(n - 1) & hash
对key进行了hashCode运算，得到一个32位的int值h,然后用h 异或 h>>>16位。在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)。
这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。
等于说计算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，减少了hash碰撞。
备注：
- ^异或：不同为1，相同为0
-
讯享网<blockquote> <p>：无符号右移：右边补0</p> </blockquote>
h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方。
1.为了让哈希后的结果更加均匀
假如槽位数不是16，而是17，则槽位计算公式变成：(17 – 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难。2.等价于length取模
当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算。
最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率。
分析HashMap的put方法：
HashMap的put方法执行过程整体如下：
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
HashMap底层结构？
基于Map接口的实现，数组+链表的结构，JDK 1.8后加入了红黑树，链表长度>8变红黑树,<6变链表。
两个对象的hashcode相同会发生什么?
Hash冲突，HashMap通过链表来解决hash冲突。
HashMap 中 equals() 和 hashCode() 有什么作用？HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点
HashMap 何时扩容？put的元素达到容量乘负载因子的时候，默认16*0.75 hash 的实现吗？
h = key.hashCode()) ^ (h >>> 16)， hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值，由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。
HashMap线程安全吗？
HashMap读写效率较高，但是因为其是非同步的，即读写等操作都是没有锁保护的，所以在多线程场景下是不安全的，容易出现数据不一致的问题，在单线程场景下非常推荐使用。
以上，是 HashMap 详细解析，欢迎评论区留言交流或拓展。
我是 mikechen | 陈睿 ，关注【mikechen的互联网架构】，10年+BAT架构技术倾囊相授。
本文已同步我的技术博客 www.mikechen.cc，更新至我原创的《30W+字大厂架构技术合集》中。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/170956.html