技术标签: 算法 hashcode hashmap hash
本人当初刚接触java的时候一说到hash算法或者hashCode也是蛋蛋疼,两只都疼
后来花了整整一天时间来研究hash,搞懂后发现其实也不难理解,时隔一年突然想起来,写篇博客记录下;
以前我莫得选择,现在我想搞懂hash,搞懂算法,做大做强,再创辉煌!
本文会围绕以下几个点来讲:
什么是hashCode?
hashCode和equals的关系
剖析hashMap的hash算法(重点)
为什么会有hashCode
先抛一个结论
hashCode的设计初衷是提高哈希容器的性能
抛开hashCode,现在让你对比两个对象是否相等,你会怎么做?
thisObj == thatObj
thisObj.equals(thatObj)
我想不出第三种了,而且这两种其实没啥大的区别,object的equals()方法底层也是==,jdk1.8 Object类的第148行;
public boolean equals(Object obj) {
return (this == obj);
}
为什么有了equals还要有hashCode?上面说了,hashCode的设计初衷是提高哈希容器的性能,equals的效率是没有hashCode高的,不信的可以自己去试一下;
像我们常用的HashMap、HashTable等,某些场景理论上讲是可以不要hashCode的,但是会牺牲很多性能,这肯定不是我们想看到的;
什么是hashCode
知道hashCode存在的意义后,我们来研究下hashCode,看下长什么样
对象调用hashCode方法后,会返回一串int类型的数字码
Car car = new Car();
log.info("对象的hashcode:{}", car.hashCode());
log.info("1433223的hashcode:{}", "1433223".hashCode());
log.info("郭德纲的hashcode:{}", "郭德纲".hashCode());
log.info("小郭德纲的hashcode:{}", "小郭德纲".hashCode());
log.info("彭于晏的hashcode:{}", "彭于晏".hashCode());
log.info("唱跳rap篮球的hashcode:{}", "唱跳rap篮球".hashCode());
运行结果
对象的hashcode:357642
1433223的hashcode:2075391824
郭德纲的hashcode:36446088
小郭德纲的hashcode:738530585
彭于晏的hashcode:24125870
唱跳rap篮球的hashcode:-767899628 ##因为返回值是int类型,有负数很正常
可以看出,对象的hashcode值跟对象本身的值没啥联系,比如郭德纲和小郭德纲,虽然只差一个字,它们的hashCode值没半毛钱关系~
hashCode和equals的关系
java规定:
如果两个对象的hashCode()相等,那么他们的equals()不一定相等。
如果两个对象的equals()相等,那么他们的hashCode()必定相等。
还有一点,重写equals()方法时候一定要重写hashCode()方法,不要问为什么,无脑写就行了,会省很多事
前面都是铺垫,这才是今天的主题
我们以HashMap的hash算法来看,个人认为这是很值得搞懂的hash算法,设计超级超级巧妙
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这是hashMap的hash算法,我们一步一步来看
(h = key.hashCode()) ^ (h >>> 16)
hashCode就hashCode嘛,为啥还要>>>16,这个 ^ 又是啥,不着急一个一个来说
hashMap我们知道默认初始容量是16,也就是有16个桶,那hashmap是通过什么来计算出put对象的时候该放到哪个桶呢
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
上面是hashmap的getNode方法,对hashmap源码有兴趣的同学自行研究,我们今天主要看这一句:(n - 1) & hash
也就是说hashmap是通过数组长度-1&key的hash值来计算出数组下标的,这里的hash值就是上面(h = key.hashCode()) ^ (h >>> 16)计算出来的值
不要慌不要慌不要慌,看不懂没关系,我们现在总结下目前的疑问
为什么数组长度要 - 1,直接数组长度&key.hashCode不行吗
为什么要length-1 & key.hashCode计算下标,而不是用key.hashCode % length
为什么要^运算
为什么要>>>16
先说结论
数组长度-1、^运算、>>>16,这三个操作都是为了让key在hashmap的桶中尽可能分散
用&而不用%是为了提高计算性能
我们先看下如果数组长度不-1和不进行>>>16运算造成的结果,知道了结果我们后面才来说为什么,这样子更好理解
log.info("数组长度不-1:{}", 16 & "郭德纲".hashCode());
log.info("数组长度不-1:{}", 16 & "彭于晏".hashCode());
log.info("数组长度不-1:{}", 16 & "李小龙".hashCode());
log.info("数组长度不-1:{}", 16 & "蔡徐鸡".hashCode());
log.info("数组长度不-1:{}", 16 & "唱跳rap篮球鸡叫".hashCode());
log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "郭德纲".hashCode());
log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "彭于晏".hashCode());
log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "李小龙".hashCode());
log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "蔡徐鸡".hashCode());
log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "唱跳rap篮球鸡叫".hashCode());
log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));
log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));
log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("李小龙".hashCode()^("李小龙".hashCode()>>>16)));
log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));
log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));
数组长度不-1:0
数组长度不-1:0
数组长度不-1:16
数组长度不-1:16
数组长度不-1:16
数组长度-1但是不进行异或和>>>16运算:8
数组长度-1但是不进行异或和>>>16运算:14
数组长度-1但是不进行异或和>>>16运算:8
数组长度-1但是不进行异或和>>>16运算:2
数组长度-1但是不进行异或和>>>16运算:14
数组长度-1并且进行异或和>>>16运算:4
数组长度-1并且进行异或和>>>16运算:14
数组长度-1并且进行异或和>>>16运算:7
数组长度-1并且进行异或和>>>16运算:13
数组长度-1并且进行异或和>>>16运算:2
一下就看出区别了哇,第一组返回的下标就只有0和16,第二组也只有2、8、14,第三组的下标就很分散,这才是我们想要的
这结合hashMap来看,前两组造成的影响就是key几乎全部怼到同一个桶里,及其不分散,用行话讲就是有太多的hash冲突,这对hashMap的性能有很大影响,hash冲突造成的链表红黑树转换那些具体的原因这里就不展开说了
而且!!
而且!!
而且!!
如果数组长度不 - 1,刚上面也看到了,会返回16这个下标,数组总共长度才16,下标最大才15,16越界了呀
知道了结果,现在说说其中的玄学
1、为什么数组长度要 - 1,直接数组长度&key.hashCode不行吗?
我们先不考虑数组下标越界的问题,hashMap默认长度是16,看看16的二进制码是多少
log.info("16的二进制码:{}",Integer.toBinaryString(16));
//16的二进制码:10000,
再看看key.hashCode()的二进制码是多少,以郭德纲为例
log.info("key的二进制码:{}",Integer.toBinaryString("郭德纲".hashCode()));
//key的二进制码:10001011000001111110001000
length & key.hashCode() => 10000 & 10001011000001111110001000
位数不够,高位补0,即
0000 0000 0000 0000 0000 0001 0000
&
0010 0010 1100 0001 1111 1000 1000
&运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1,否则为0
所以结果为0000 0000 0000 0000 0000 0000 0000,即 0
冷静分析,问题就出在16的二进制码上,它码是10000,只有遇到hash值二进制码倒数第五位为1的key他们&运算的结果才不等于0,这句话好好理解下,看不懂就别强制看,去摸会儿鱼再回来看
再来看16-1的二进制码,它码是1111,同样用郭德纲这个key来举例
(length-1) & key.hashCode() => 1111 & 10001011000001111110001000
位数不够,高位补0,即
0000 0000 0000 0000 0000 0000 1111
&
0010 0010 1100 0001 1111 1000 1000
&运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1,否则为0
所以结果为0000 0000 0000 0000 0000 0000 1000,即 8
如果还看不出这其中的玄机,你就多搞几个key来试试,总之记住,限制它们&运算的结果就会有很多种可能性了,不再受到hash值二进制码倒数第五位为1才能为1的限制
2、为什么要length-1&key.hashCode计算下标,而不是用key.hashCode%length?
这个其实衍生出三个知识点
1、其实(length-1)&key.hashCode计算出来的值和key.hashCode%length是一样的
log.info("(length-1)&key.hashCode:{}",15&"郭德纲".hashCode());
log.info("key.hashCode%length:{}","郭德纲".hashCode()%16);
// (length-1)&key.hashCode:8
// key.hashCode%length:8
那你可能更蒙逼了,都一样的为啥不用%,这就要说到第二个知识点
2、只有当length为2的n次方时,(length-1)&key.hashCode才等于key.hashCode%length,比如当length为15时
log.info("(length-1)&key的hash值:{}",14&"郭德纲".hashCode());
log.info("key的hash值%length:{}","郭德纲".hashCode()%15);
// (length-1)&key.hashCode:8
// key.hashCode%length:3
可能又有小朋友会思考,我不管那我就想用%运算,要用魔法打败魔法,请看第三点
3、用&而不用%是为了提高计算性能,对于处理器来讲,&运算的效率是高于%运算的,就这么简单,除此之外,除法的效率也没&高
3、为什么要进行^运算,|运算、&运算不行吗?
这是异或运算符,第一个操作数的的第n位于第二个操作数的第n位相反才为1,否则为0
我们多算几个key的值出来对比
//不进行异或运算返回的数组下标
log.info("郭德纲:{}", Integer.toBinaryString("郭德纲".hashCode()));
log.info("彭于晏:{}", Integer.toBinaryString("彭于晏".hashCode()));
log.info("李小龙:{}", Integer.toBinaryString("李小龙".hashCode()));
log.info("蔡徐鸡:{}", Integer.toBinaryString("蔡徐鸡".hashCode()));
log.info("唱跳rap篮球鸡叫:{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()));
00001000101100000111111000 1000
00000101110000001000011010 1110
00000110001111100100010011 1000
00000111111111111100010111 0010
10111010111100100011001111 1110
进行&运算,看下它们返回的数组下标,length为16的话,只看后四位即可
8
14
8
2
14
//进行异或运算返回的数组下标
log.info("郭德纲:{}", Integer.toBinaryString("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));
log.info("彭于晏:{}", Integer.toBinaryString("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));
log.info("李小龙:{}", Integer.toBinaryString("李小龙".hashCode()^("李小龙".hashCode()>>>16)));
log.info("蔡徐鸡:{}", Integer.toBinaryString("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));
log.info("唱跳rap篮球鸡叫:{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));
0000001000101100000111011010 0100
0000000101110000001000001101 1110
0000000110001111100100001011 0111
0000000111111111111100001000 1101
0010111010111100101000100100 0010
进行&运算,看下它们返回的数组下标,length为16的话,只看后四位即可
4
14
7
13
2
很明显,做了^运算的数组下标更分散
如果还不死心,再来看几个例子
看下 ^、|、&这三个位运算的结果就知道了
log.info("^ 运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 16)));
log.info("^ 运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 16)));
log.info("^ 运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 16)));
log.info("^ 运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 16)));
//^ 运算:4
//^ 运算:14
//^ 运算:7
//^ 运算:13
log.info("| 运算:{}", 15 & ("郭德纲".hashCode() | ("郭德纲".hashCode() >>> 16)));
log.info("| 运算:{}", 15 & ("彭于晏".hashCode() | ("彭于晏".hashCode() >>> 16)));
log.info("| 运算:{}", 15 & ("李小龙".hashCode() | ("李小龙".hashCode() >>> 16)));
log.info("| 运算:{}", 15 & ("蔡徐鸡".hashCode() | ("蔡徐鸡".hashCode() >>> 16)));
//| 运算:12
//| 运算:14
//| 运算:15
//| 运算:15
log.info("& 运算:{}", 15 & ("郭德纲".hashCode() & ("郭德纲".hashCode() >>> 16)));
log.info("& 运算:{}", 15 & ("彭于晏".hashCode() & ("彭于晏".hashCode() >>> 16)));
log.info("& 运算:{}", 15 & ("李小龙".hashCode() & ("李小龙".hashCode() >>> 16)));
log.info("& 运算:{}", 15 & ("蔡徐鸡".hashCode() & ("蔡徐鸡".hashCode() >>> 16)));
//& 运算:8
//& 运算:0
//& 运算:8
//& 运算:2
现在看出来了吧,^ 运算的下标分散,具体原理在下文会说
4、为什么要>>>16,>>>15不行吗?
这是无符号右移16位,位数不够,高位补0
现在来说进行 ^ 运算中的玄学,其实>>>16和 ^ 运算是相辅相成的关系,这一套操作是为了保留hash值高16位和低16位的特征,因为数组长度(按默认的16来算)减1后的二进制码低16位永远是1111,我们肯定要尽可能的让1111和hash值产生联系,但是很显然,如果只是1111&hash值的话,1111只会与hash值的低四位产生联系,也就是说这种算法出来的值只保留了hash值低四位的特征,前面还有28位的特征全部丢失了;
因为&运算是都为1才为1,1111我们肯定是改变不了的,只有从hash值入手,所以hashMap作者采用了 key.hashCode() ^ (key.hashCode() >>> 16) 这个巧妙的扰动算法,key的hash值经过无符号右移16位,再与key原来的hash值进行 ^ 运算,就能很好的保留hash值的所有特征,这种离散效果才是我们最想要的。
上面这两段话就是理解>>>16和 ^ 运算的精髓所在,如果没看懂,建议你休息一会儿再回来看,总之记住,目的都是为了让数组下标更分散
再补充一点点,其实并不是非得右移16位,如下面得测试,右移8位右移12位都能起到很好的扰动效果,但是hash值的二进制码是32位,所以最理想的肯定是折半咯,雨露均沾
log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 16)));
log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 16)));
log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 16)));
log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 16)));
//>>>16运算:4
//>>>16运算:14
//>>>16运算:7
//>>>16运算:13
log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 8)));
log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 8)));
log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 8)));
log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 8)));
//>>>8运算:7
//>>>8运算:1
//>>>8运算:9
//>>>8运算:3
log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 12)));
log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 12)));
log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 12)));
log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 12)));
//>>>12运算:9
//>>>12运算:12
//>>>12运算:1
//>>>12运算:13
嘤嘤嘤~ 写了整整一天终于我写完了
嘤嘤嘤~ 好害羞
嘤嘤嘤~ 好紧张
文章浏览阅读3.5k次,点赞2次,收藏13次。为了从FTP服务器下载文件,需要要实现一个简单的FTP客户端。FTP(文件传输协议) 是 TCP/IP 协议组中的应用层协议。FTP协议使用字符串格式命令字,每条命令都是一行字符串,以“\r\n”结尾。客户端发送格式是:命令+空格+参数+"\r\n"的格式服务器返回格式是以:状态码+空格+提示字符串+"\r\n"的格式,代码只要解析状态码就可以了。读写文件需要登陆服务器,特殊用..._ftp 登录返回230
文章浏览阅读648次。前提:systemctl stop firewalld 关闭防火墙关闭selinux查看getenforce临时关闭setenforce 0永久关闭sed-i'/SELINUX/s/enforcing/disabled/'/etc/selinux/configselinux的三种模式enforcing:强制模式,SELinux 运作中,且已经正确的开始限制..._centos7 安装rabbitmq3.6.5
文章浏览阅读5.8k次。满意答案s55f2avsx2017.09.05采纳率:46%等级:12已帮助:5646人新版Android Studio/IntelliJ IDEA可以直接导入eclipse项目,不再推荐使用eclipse导出gradle的方式2启动Android Studio/IntelliJ IDEA,选择 import project3选择eclipse 项目4选择 create project f..._android studio 项目导入idea 看不懂安卓项目
文章浏览阅读860次,点赞2次,收藏6次。AI大模型技术已经在自然语言处理、计算机视觉、多模态交互等领域取得了显著的进展和成果,同时也引发了一系列新的挑战和问题,如数据质量、计算效率、知识可解释性、安全可靠性等。城市运维涉及到多个方面,如交通管理、环境监测、公共安全、社会治理等,它们需要处理和分析大量的多模态数据,如图像、视频、语音、文本等,并根据不同的场景和需求,提供合适的决策和响应。知识搜索有多种形式,如语义搜索、对话搜索、图像搜索、视频搜索等,它们可以根据用户的输入和意图,从海量的数据源中检索出最相关的信息,并以友好的方式呈现给用户。_ai大模型应用开发
文章浏览阅读8.2k次,点赞12次,收藏121次。为什么要测量阻抗呢?阻抗能代表什么?阻抗测量的注意事项... ...很多人可能会带着一系列的问题来阅读本文。不管是数字电路工程师还是射频工程师,都在关注各类器件的阻抗,本文非常值得一读。全文13000多字,认真读完大概需要2小时。一、阻抗测试基本概念阻抗定义:阻抗是元器件或电路对周期的交流信号的总的反作用。AC 交流测试信号 (幅度和频率)。包括实部和虚部。图1 阻抗的定义阻抗是评测电路、元件以及制作元件材料的重要参数。那么什么是阻抗呢?让我们先来看一下阻抗的定义。首先阻抗是一个矢量。通常,阻抗是_阻抗实部和虚部
文章浏览阅读955次。前面章节分享试用了pyzero,pygame但随着想增加更丰富的游戏内容,好多还要进行自己编写类,从今天开始解绍一个新的python游戏库arcade模块。通过此次的《连连看》游戏实现,让我对swing的相关知识有了进一步的了解,对java这门语言也有了比以前更深刻的认识。java的一些基本语法,比如数据类型、运算符、程序流程控制和数组等,理解更加透彻。java最核心的核心就是面向对象思想,对于这一个概念,终于悟到了一些。_arcade语言 like
文章浏览阅读1.1k次。源码简介与安装说明:2021增强版短视频去水印源码 去水印微信小程序源码网站 去水印软件源码安装环境(需要材料):备案域名–服务器安装宝塔-安装 Nginx 或者 Apachephp5.6 以上-安装 sg11 插件小程序已自带解析接口,支持全网主流短视频平台,搭建好了就能用注:接口是公益的,那么多人用解析慢是肯定的,前段和后端源码已经打包,上传服务器之后在配置文件修改数据库密码。然后输入自己的域名,进入后台,创建小程序,输入自己的小程序配置即可安装说明:上传源码,修改data/_去水印机要增强版
文章浏览阅读557次。1. 触发器是FPGA存储数据的基本单元2. 触发器作为时序逻辑的基本元件,官方提供了丰富的配置方式,以适应各种可能的应用场景。_fdre #(.init(1'b0) // initial value of register (1'b0 or 1'b1) ) fdce_osc (
文章浏览阅读560次。本该是不同编译器结果不同,但是尝试了g++ msvc都是先计算c,再计算b,最后得到a+b+c是经过赋值以后的b和c参与计算而不是6。由上表可知,将q复制到p数组可以表示为:*p++=*q++,*优先级高,先取到对应q数组的值,然后两个++都是在后面,该行运算完后执行++。在电脑端编译完后会分为text data bss三种,其中text为可执行程序,data为初始化过的ro+rw变量,bss为未初始化或初始化为0变量。_嵌入式面试笔试c语言知识点
文章浏览阅读2.3k次。57 Things I've Learned Founding 3 Tech CompaniesJason Goldberg, Betashop | Oct. 29, 2010, 1:29 PMI’ve been founding andhelping run techn_mature
文章浏览阅读1.9k次。问题:先讲下需求,有若干个文本文件(txt或者csv文件等),每行代表一条数据,现在希望能合并成 1 个文本文件,且需要去除重复行。分析:一向奉行简单原则,如无必要,绝不复杂。如果数据量不大,那么如下两条命令就可以搞定合并:cat a.txt >> new.txtcat b.txt >> new.txt……去重:cat new...._python 超大文本合并
文章浏览阅读489次。这个过渡页是第一次打开小程序展示的,点击某个小程序前把手机的开发者->network link conditioner->enable & very bad network 就会在停在此页。比如《支付宝运动》这个小程序先看这个类的.h可以看到它继承于DTViewController点击左上角返回的方法- (void)back;#import "DTViewController.h"#import "APBaseLoadingV..._类似支付宝页面过度加载页