HashMap的常见问题

Entry中的hash属性为什么不直接使用key的hashCode()返回值呢?

不管是JDK1.7还是JDK1.8中,都不是直接用key的hashCode值直接与table.length-1计算求下标的,而是先对key的hashCode值进行了一个运算,JDK1.7和JDK1.8关于hash()的实现代码不一样,但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果,尽量的均匀分布。

在这里插入图片描述

JDK1.7:

    final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

JDK1.8:

	static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

虽然算法不同,但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或,然高位二进制参与到index的计算中。

为什么要hashCode值的二进制的高位参与到index计算呢?

因为一个HashMap的table数组一般不会特别大,至少在不断扩容之前,那么table.length-1的大部分高位都是0,直接用hashCode和table.length-1进行&运算的话,就会导致总是只有最低的几位是有效的,那么就算你的hashCode()实现的再好也难以避免发生碰撞,这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征,显著减少了碰撞冲突的发生。

HashMap是如何决定某个key-value存在哪个桶的呢?

因为hash值是一个整数,而数组的长度也是一个整数,有两种思路:

①hash 值 % table.length会得到一个[0,table.length-1]范围的值,正好是下标范围,但是用%运算效率没有位运算符&高。

②hash 值 & (table.length-1),任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围。

在这里插入图片描述

JDK1.7:

static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1); //此处h就是hash
}

JDK1.8:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)  // i = (n - 1) & hashtab[i] = newNode(hash, key, value, null);//....省略大量代码
}
为什么要保持table数组一直是2的n次幂呢?

因为如果数组的长度为2的n次幂,那么table.length-1的二进制就是一个高位全是0,低位全是1的数字,这样才能保证每一个下标位置都有机会被用到。

举例1:

hashCode值是   ?
table.length是10
table.length-19????????
9	 00001001
&_____________00000000	[0]00000001	[1]00001000	[8]00001001	[9]一定[0]~[9]

举例2:

hashCode值是   ?
table.length是16
table.length-115????????
15	 00001111
&_____________00000000	[0]00000001	[1]00000010	[2]00000011	[3]...00001111    [15]范围是[0,15],一定在[0,table.length-1]范围内
解决[index]冲突问题

虽然从设计hashCode()到上面HashMap的hash()函数,都尽量减少冲突,但是仍然存在两个不同的对象返回的hashCode值相同,或者hashCode值就算不同,通过hash()函数计算后,得到的index也会存在大量的相同,因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办?

JDK1.8之间使用:数组+链表的结构。

在这里插入图片描述

JDK1.8之后使用:数组+链表/红黑树的结构。

在这里插入图片描述

即hash相同或hash&(table.lengt-1)的值相同,那么就存入同一个“桶”table[index]中,使用链表或红黑树连接起来。

为什么JDK1.8会出现红黑树和链表共存呢?

因为当冲突比较严重时,table[index]下面的链表就会很长,那么会导致查找效率大大降低,而如果此时选用二叉树可以大大提高查询效率。

但是二叉树的结构又过于复杂,占用内存也较多,如果结点个数比较少的时候,那么选择链表反而更简单。所以会出现红黑树和链表共存。

加载因子的值大小有什么关系?

如果太大,threshold就会很大,那么如果冲突比较严重的话,就会导致table[index]下面的结点个数很多,影响效率。

如果太小,threshold就会很小,那么数组扩容的频率就会提高,数组的使用率也会降低,那么会造成空间的浪费。

什么时候树化?什么时候反树化?
static final int TREEIFY_THRESHOLD = 8;//树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量
  • 当某table[index]下的链表的结点个数达到8,并且table.length>=64,那么如果新Entry对象还添加到该table[index]中,那么就会将table[index]的链表进行树化。

  • 当某table[index]下的红黑树结点个数少于6个,此时,

    • 当继续删除table[index]下的树结点,最后这个根结点的左右结点有null,或根结点的左结点的左结点为null,会反树化
    • 当重新添加新的映射关系到map中,导致了map重新扩容了,这个时候如果table[index]下面还是小于等于6的个数,那么会反树化
package com.atguigu.map;public class MyKey{int num;public MyKey(int num) {super();this.num = num;}@Overridepublic int hashCode() {if(num<=20){return 1;}else{final int prime = 31;int result = 1;result = prime * result + num;return result;}}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;MyKey other = (MyKey) obj;if (num != other.num)return false;return true;}}
package com.atguigu.map;import org.junit.Test;import java.util.HashMap;public class TestHashMapMyKey {@Testpublic void test1(){//这里为了演示的效果,我们造一个特殊的类,这个类的hashCode()方法返回固定值1//因为这样就可以造成冲突问题,使得它们都存到table[1]中HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);//树化演示}}@Testpublic void test2(){HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 1; i <=11; i++) {map.remove(new MyKey(i));//反树化演示}}@Testpublic void test3(){HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 1; i <=5; i++) {map.remove(new MyKey(i));}//table[1]下剩余6个结点for (int i = 21; i <= 100; i++) {map.put(new MyKey(i), "value"+i);//添加到扩容时,反树化}}
}
key-value中的key是否可以修改?

key-value存储到HashMap中会存储key的hash值,这样就不用在每次查找时重新计算每一个Entry或Node(TreeNode)的hash值了,因此如果已经put到Map中的key-value,再修改key的属性,而这个属性又参与hashcode值的计算,那么会导致匹配不上。 HUANGANHE

这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。

JDK1.7中HashMap的循环链表是怎么回事?如何解决?

在这里插入图片描述

避免HashMap发生死循环的常用解决方案:

  • 多线程环境下,使用线程安全的ConcurrentHashMap替代HashMap,推荐
  • 多线程环境下,使用synchronized或Lock加锁,但会影响性能,不推荐
  • 多线程环境下,使用线程安全的Hashtable替代,性能低,不推荐

HashMap死循环只会发生在JDK1.7版本中,主要原因:头插法+链表+多线程并发+扩容。

在JDK1.8中,HashMap改用尾插法,解决了链表死循环的问题。

补:

  1. JDK7当插入数据达到容量*负载因子时,会对底层数组进行扩容,然后再通过头插法进行数据插入,在多线程的情况下,会出现循环链表的情况;
  2. JDK8则是在通过尾插法进行数据插入之后,再对底层数组进行扩容,在多线程的情况下,也能避免链表死循环的问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/306565.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

学习数通HCIE选择誉天有什么优势?

誉天数通课程亮点 课程内容详实&#xff0c;千万级实训环境 涵盖数通技术全场景热门技术&#xff0c;涉及传统园区网&#xff0c;虚拟化园区网&#xff0c;广域互联技术&#xff0c;数据中心网络&#xff0c;网络自动化运维 专业机房环境&#xff0c;全真机教学演示&#xf…

【JavaEE初阶系列】——网络编程 TCP客户端/服务器 程序实现

目录 &#x1f6a9;TCP流套接字编程 &#x1f36d;ServerSocket API &#x1f36d;Socket API &#x1f36d;TCP服务器 &#x1f36d;TCP客户端 &#x1f6a9;TCP流套接字编程 俩个关键的类 ServerSocket (给服务器使用的类&#xff0c;使用这个类来绑定端口号&#xff0…

2024接口自动化测试入门基础知识【建议收藏】

接口自动化测试是指通过编写测试脚本和使用相关工具&#xff0c;对软件系统的接口进行自动化测试的过程。 今天本文从4个方面来介绍接口自动化测试入门基础知识 一、接口自动化测试是什么&#xff1f; 二、接口自动化测试流程&#xff1f; 三、接口自动化测试核心知识点有那些…

MySQL一些特殊功能的索引(6/16)

特殊功能性索引 B-Tree索引&#xff1a; InnoDB的默认索引类型&#xff0c;适用于多种查询操作。 可以用于等值查询、范围查询和索引列的组合查询。 创建B-Tree索引的示例&#xff1a; CREATE INDEX index_name ON table_name (column1, column2);全文索引&#xff08;FULLTEX…

力扣207.课程表

你这个学期必须选修 numCourses 门课程&#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出&#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如…

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…

事务,MySQL函数和索引详解

文章目录 事务简介提交方式手动提交事务 事务执行流程修改事务的默认提交方式 事务原理四大特性隔离级别 MySQL函数常见的日期函数判断函数case when字符串函数数字函数 MySQL性能(了解)索引概念分类MySQL索引语法数据结构(了解)BTreeBTree好处 优缺点优势劣势 创建原则 事务简…

python中time库的time.time()函数的作用是什么?

python中time库的time.time()函数的作用是什么&#xff1f; 作用&#xff1a;Python time time() 返回当前时间的时间戳&#xff08;1970纪元后经过的浮点秒数&#xff09;。 time()方法语法&#xff1a;time.time() #!/usr/bin/python # Write Python 3 code in this onlin…

【LeetCode】动态规划类题目详解

所有题目均来自于LeetCode&#xff0c;刷题代码使用的Python3版本 动态规划 问题分类 如果某一个问题有重叠的子问题&#xff0c;则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的&#xff0c;这一点区别于贪心算法 动态规划五部曲 确…

【JMeter】JMeter控制RPS

一、前言 ​ RPS (Request Per Second)一般用来衡量服务端的吞吐量&#xff0c;相比于并发模式&#xff0c;更适合用来摸底服务端的性能。我们可以通过使用 JMeter 的常数吞吐量定时器来限制每个线程的RPS。对于RPS&#xff0c;我们可以把他理解为我们的TPS&#xff0c;我们就不…

初识SpringMVC

一、什么是MVC MVC是一种软件架构模式&#xff08;是一种软件架构设计思想&#xff0c;不止Java开发中用到&#xff0c;其它语言也需要用到&#xff09;&#xff0c;它将应用分为三块&#xff1a; M&#xff1a;Model&#xff08;模型&#xff09;V&#xff1a;View&#xff08…

Centos7 K8S 集群 - kubeadm搭建方式

机器准备 搭建环境是centos7, 四核心4G内存四台机器 一个master节点&#xff0c;一个etcd&#xff0c;两台node 机器名称IP 地址master192.168.1.127node1192.168.1.129node2192.168.1.130node3192.168.1.131 机器时间同步 各节点时间要求精确同步&#xff0c;可以直接联网…

游标的定义和类型

Oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 游标的基本概念 游标从字面上理解为游动的光标&#xff0c;可以使用 Excel 表格来想象游标的作用&#xff0c;游标指向每一行&#xff0c;通过游标访问每行数据。 在 Orac…

6.3Python之字典的内置方法

1、创建字典 dict.fromkeys() &#xff1a;可将列表、元组、集合转为字典 knowledgeL [语文, 数学, 英语] scoresD1 dict.fromkeys(knowledgeL, 60) print(scoresD1) knowledgeT (Chinese, Math, English) scoresD2 dict.fromkeys(knowledgeT, 60) print(scoresD2) knowl…

【Web】CTFSHOW-ThinkPHP5-6反序列化刷题记录(全)

目录 web611 web612 web613-622 web623 web624-626 纯记录exp&#xff0c;链子不作赘述 web611 具体分析&#xff1a; ThinkPHP-Vuln/ThinkPHP5/ThinkPHP5.1.X反序列化利用链.md at master Mochazz/ThinkPHP-Vuln GitHub 题目直接给了反序列化入口 exp: <?ph…

Web中使用Weblogic用户

WebLogic用户&#xff0c;组设置 1. 登录weblogic console, domain结构中选择Security Realms&#xff0c;显示安装时默认创建的Realm &#xff1a; myrealm 2. 点击myrealm, 选择 users and Group&#xff0c; 追加用户和组 选择既存的权限组追加到新规的组中&#xff0c;赋予…

面试:如何设计一个注册中心?

大家好&#xff0c;我是田哥 上周&#xff0c;一位群里的朋友反馈面试情况&#xff1a; 今天&#xff0c;给大家分享如何设计一个注册中心。其实这个问题&#xff0c;我之前在知识星球里分享过&#xff0c;可能是因为时间比较久了&#xff0c;加上这位朋友加入不久&#xff0c;…

力扣HOT100 - 160. 相交链表

解题思路&#xff1a; /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if…

雨云:不一样的服务器体验

引言 在当今数字化时代&#xff0c;服务器已经成为了许多企业和个人不可或缺的一部分。无论是建立网站、存储数据还是运行应用程序&#xff0c;都需要一个稳定可靠的服务器来支持。然而&#xff0c;在众多的服务器提供商中&#xff0c;选择一个适合自己需求的并不容易。今天我要…

spispi

数据手册里面有这么一段解释&#xff0c;就是说如果我们开启了看门狗&#xff0c;那么LSI就会跟随强制打开&#xff0c;等待LSI稳定之后就可以自动为独立看门狗提供时钟了。所以这里的第一步开启时钟不需要我们写代码来执行 2.写入预分频器和重装寄存器 在写入这两个寄存器之前…