hashMap问题答案

￡神魔★判官ぃ 2022-09-10 10:29 139阅读 0赞

##### 1.说说你对hash算法的理解 #####

是把任意长度的输入（又叫做预映射pre-image）通过hash算法变换成固定长度的输出，该输出就是散列值。

追问：hash算法任意长度的输入 转化为了 固定长度的输出，会不会有问题呢？  
会产生hash冲突的问题，在程序中两个值经过hash算法之后得到同样的hash值就会产生hash冲突  
追问：hash冲突能避免么？  
理论上是不可避免的，举个例子吧，抽屉原理，9个抽屉 10个苹果，最终肯定会有一个抽屉的苹果数量大于一的。所以hash冲突无法避免，只能尽量避免。

##### 2.你认为好的hash算法，应该考虑点有哪些呢？ #####

正向快速：给定关键字和散列函数，有限时间和资源内能计算出散列（hash）值  
逆向困难：只给定hash值，你很难逆向算出关键字。  
输入敏感：原始输入信息修改一点点，产生的hash值也能有较大的不同。  
冲突避免：你很难找到两个不同的关键字算出的散列值是相同的（发生冲突）

##### 3.HashMap中存储数据的结构是什么样的呢？ #####

jdk8版本，hashmap是 数组+链表+红黑树构成的，每个数据单元都是Node结构，node结构中有key value next hash字段，next字段是在产生hash冲突的时候当前桶中的node 与冲突的node连成一个链表用的字段

##### 4.创建HashMap时，不指定散列表数组长度，初始长度是多少呢？ #####

散列表数组的长度默认初始值16  
追问：散列表是new HashMap() 时创建的么？  
不是，散列表是懒加载机制，只有在第一次put的时候才创建

##### 5.默认负载因子是多少呢，并且这个负载因子有什么作用？ #####

默认的负载因子是0.75，负载因子是计算扩容阈值用的，比如创建的hashmap对象，默认情况下扩容阈值是16 \*0.75也就是12

##### 6.链表转化为红黑树，需要达到什么条件呢？ #####

链表转红黑树主要是有两个指标，其中一个就是链表的长度达到8，另一个是当前散列数组的长度>=64

##### 7.Node对象内部的hash字段，这个hash值是key对象的hashcode()返回值么？ #####

这个不是的，这个是经过二次计算得到的  
追问：这个hash值是怎么得到呢？  
key的hashcode值经过二次加工得到的，这个hash值是散列数组的地址，咱们都知道，散列数组的长度必须是2的次方，二次计算hash值的算法是，hash值高低位异或后 对散列数组长度进行取余，但是取余操作效率太低，不如计算机指令效率高，所以代码中 hash&(table.length-1) 来进行按位与计算，所以在散列数组是 二的次方的时候 hash&(table.length-1)==hash%table.length  
table.length 例如默认值16 转换为二进制是10000 32转换为二进制是100000，是有规律的，2的次方装换为2进制都是高位是1 低位全是0的，而这种2的次方数减一的二进制都变成了111…，所以在进行按位与&，按位与& 运算，两个当且仅当都为1的时候结果才为1，  
追问：hash字段为什么采用高低位异或？  
主要是优化hash算法，如代码 (h = key.hashCode()) ^ (h >>> 16)，当数组的长度很短时，只有低位数的hashcode值能参与运算(按位与运算)。而让高16位参与运算可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。

##### 8.HashMap put 写数据的具体流程，尽可能的详细点！ #####

put数据的时候，把key的hashcode值进行高低位^异或，和按位与（hash&(table.length-1)）进行寻址操作得到下标，会遇到4中情况,1、slot == null 得到的下标没有数据，2、slot !=null 并且node还没有链华3、node已经链化了 4、冲突严重、已经转换为红黑树了  
分析情况：  
1、如果当前位置的节点为null，说明当前位置未曾放置对象，可直接创建节点对象，并放入数组  
2、当前位置节点不为空，对比node对象的key和put对象的key是否完全相等，如果相等的话就是替换操作，把node节点的值替换为新put的值，，如果不相等就是hash冲突了，将当前待存放的数据存入尾结点的next属性  
3、node已经链化了之后，遍历链表对比key是否相等，直到找到链表最后一个元素，将当前待存放的数据存入尾结点的next属性，然后检查当前链表有没有达到阈值，如果达到就调用树化方法  
4、当前位置已存的节点如果是树节点，执行向树中添加节点

##### 9.红黑树的写入操作，是怎么找到父节点的，找父节点流程？ #####

##### 10.TreeNode数据结构，简单说下。 #####

treeNode结构继承了node结构加了几个字段，分别是指向父节点的parent,左节点的left,右节点的right,还有表示上一个节点的prev，还有判断颜色的red字段。这就是treeNode的基本结构

##### 11.红黑树的原则有哪些呢？ #####

##### 12.JDK8 hashmap为什么引入红黑树？解决什么问题？ #####

追问：为什么hash冲突后性能变低了？【送分题】

##### 13.hashmap 什么情况下会触发扩容呢？ #####

追问：触发扩容后，会扩容多大呢？算法是什么？
    追问：为什么采用位移运算，不是直接*2？

##### 14.hashmap扩容后，老表的数据怎么迁移到扩容后的表的呢？ #####

##### 15.hashmap扩容后，迁移数据发现该slot是颗红黑树，怎么处理呢？ #####

--------------------

hashMap

数组加链表  
数组：采用一段连续的存储单元来存储数据  
特点：查询0(1) 删除插入0(N) 总结查询快，插入慢

链表：链表是一种物理存储 单元上非连续、非顺序的存储结构  
特点：插入、删除时间复杂度0(1) 查询遍历时间复杂度0(N),总结：插入快 查找慢

hashmap put值的时候（n是集合的容量） (n - 1) & hash 计算该元素在entry\[\]数组中的位置

为了提高取余操作的效率，用了按位与&  
当需要对2的次幂进行求余时，可以是使用&运算符来代替，效率会提高很多。

--------------------

hashmap 底层是数组+链表 jdk1.8又加了红黑树，数组是采用一段连续的存储单元来存储数据的，  
日常中我们经常用到HashMap并且面试题也有很多针对它的,这次就说说他的长度~  
默认为16我们都知道,默认的扩容负载因子是0.75f,每次扩容后容量都保持为2的幂;

Hashmap中put元素时，首先根据key的hashcode进行取余运算(n - 1) & hash ( 按位于&），得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数中该位置没有元素,就直接将该元素放到数组的该位置上。

扩容的时候是左移<<一位 16<<1 == 16\*2

是0.75的答案也就出来了，这是时间和空间的权衡

--------------------