面试官说又逮到一个不会hashmap的#yyds干货盘点# _HashMap

落花踏尽游何处，笑入胡姬酒肆中。这篇文章主要讲述面试官说又逮到一个不会hashmap的#yyds干货盘点#相关的知识，希望能为你提供帮助。

文章图片

一. 你知道哪些 map ？HashMap,TreeMap,ConcurrentHashMap,LinkedHashMap
二.HashMap 的特点是什么？

允许 Key 和Value 为 null ，不过只能有一条记录 Key 为 null
线程不安全
无序
数据结构是数组+链表/红黑树（JDK1.8）

三. JDK1.8 中 HashMap为什么要引入红黑树？链表查询时间复杂度 O(n) ，插入时间复杂度O(1)
红黑树查询和插入时间复杂度都是 O(lgn)
可以参考下美团技术团队的这篇文章 https://tech.meituan.com/2016/06/24/java-hashmap.html

文章图片

四. HashMap长度为什么只能是2的倍数

计算 Hash 值时采用位运算来代替取模，能更高效地计算出元素的位置。

文章图片

元素对应的 index 是通过下面代码赋值的，即

index = hash &
 hashmap的table长度-1

if ((p = tab[i = (n - 1) & hash]) == null)

扩容时能更快地计算出 key 的 index，提高扩容效率
比如 map 大小为 16 ，key 为 2 所在的 index 为 2， 18 所在的 index 也是 2
但是扩容之后变成 32 了，key 为 2 所在的 index 还是为 2，而18 所在的 index 就变为· 2+16=18 了。

这里 4ye就直接截取了 resize 中链表重新计算 index 的部分，红黑树 TreeNode 中也有类似的代码

文章图片

五. HashMap什么时候进行扩容【面试官说又逮到一个不会hashmap的#yyds干货盘点#】当（ hash 表的大小），> （ hash表的大小 * 负载因子）的值时，则进行扩容

文章图片

文章图片

六. 负载因子的大小负载因子大小决定着哈希表的扩容和哈希冲突，每次 put 新元素后都要检查，看看需不需要扩容，扩容默认是原来的两倍。
调高负载因子，会增加 hash 冲突的概率，同样会增加耗时，扩容本身也会耗时。
七. 怎么计算 hash 值计算 key 的 hashCode 值，然后将这个值与它的高十六位进行异或运算
这么做是为了减少hash冲突

//> > > 无符号位右移，即不管该数的正负，都在高位补0 //> > 表示右移，如果该数为正，则高位补0，若为负数，则高位补1 //< < 左移直接在低位补0，无正负之分

文章图片

验证下~

int hashCode = "java4ye".hashCode(); System.out.println((hashCode ^ (hashCode > > > 16))& 15); // 打印出 0 hashMap.put("Java4ye","1");

文章图片

八. hash 冲突的解决办法

开放定址法
链地址法（拉链法）HashMap采用的
再哈希法
公共溢出区域法

九. put 和 get 的实现put 时
先计算该 key 的 hash 值，并算出它所在的 bucket 的 index ，如果没有碰撞的话，直接放到数组中。
如果碰撞了，先判断，这个 key 是不是同一个key，是的话直接覆盖。
不是的话再去判断当前是链表还是红黑树，再依据不同的情况进行插入，如果 key 一样的话，会根据 onlyIfAbsent 的值或者原来的值是否为 null 进行替换或者保留原来的值。
如果是找到对应的key的话，会返回该旧值，不会继续往下执行
如果是增加新元素的话，最后会判断 hash 表的大小，如果该值大于 hash表的大小 * 负载因子，则进行扩容；最后返回null
大家可以看看 4ye 给出的这个源码，每一步都做了这个重要的注释了~ ，反正我自己看懂了哈哈哈哈哈