乐趣区

关于java:快来我悄悄的给你说几个HashCode的破事

这是 why 技术的第 72 篇原创文章

Hash 抵触是怎么回事

在这个文章正式开始之前,先几句话把这个问题说分明了: 咱们常说的 Hash 抵触到底是怎么回事?

间接上个图片:

你说你看到这个图片的时候想到了什么货色?

有没有想到 HashMap 的数组加链表的构造?

对咯,我这里就是以 HashMap 为切入点,给大家讲一下 Hash 抵触。

接着咱们看上面这张图:

假如当初咱们有个值为 [why 技术] 的 key,通过 Hash 算法后,计算出值为 1,那么含意就是这个值应该放到数组下标为 1 的中央。

然而如图所示,下标为 1 的中央曾经挂了一个 eat 的值了。这个坑位曾经被人占着了。

那么此时此刻, 咱们就把这种景象叫为 Hash 抵触。

HashMap 是怎么解决 Hash 抵触的呢?

链地址法,也叫做拉链法。

数组中呈现 Hash 抵触了,这个时候链表的数据结构就派上用场了。

链表怎么用的呢?看图:

这样问题就被咱们解决了。

其实 hash 抵触也就是这么一回事: 不同的对象通过同一个 Hash 算法后失去了一样的 HashCode。

那么写到这里的时候我忽然想到了一个面试题:

请问我下面的图是基于 JDK 什么版本的 HashMap 画的图?

为什么想到了这个面试题呢?

因为我画图的时候犹豫了大略 0.3 秒,往链表上挂的时候,我到底是应用头插法还是尾插法呢?

家喻户晓,JDK 7 中的 HashMap 是采纳头插法的,即 [why 技术] 在 [eat] 之前,JDK 8 中的 HashMap 采纳的是尾插法。

这面试题怎么说呢,真的无聊。然而能怎么办呢,八股文该背还是得背。

面试嘛,背一背,不寒碜。

构建 HashCode 一样的 String

后面咱们晓得了,Hash 抵触的根本原因是不同的对象通过同一个 Hash 算法后失去了一样的 HashCode。

这句话乍一听:嗯,很有情理,就是这么一回事,没有问题。

比方咱们罕用的 HashMap,绝大部分状况 key 都是 String 类型的。要呈现 Hash 抵触,起码须要两个 HashCode 一样的 String 类。

那么我问你: 怎么能力疾速弄两个 HashCode 一样的 String 呢?

怎么样,有点懵逼了吧?

从很有情理,到有点懵逼只须要一个问题。

来,我带你剖析一波。

我先问你:长度为 1 的两个不一样的 String,比方上面这样的代码,会不会有一样的 HashCode?

`String a = “a”;
String b = “b”;
`

必定是不会的,对吧。

如果你不晓得的话,倡议你去 ASCII 码外面找答案。

咱们接着往下梳理,看看长度为 2 的 String 会不会呈现一样的 HashCode?

要答复这个问题,咱们要先看看 String 的 hashCode 计算方法,我这里以 JDK 8 为例:

咱们假如这两个长度为 2 的 String,别离是 xy 和 ab 吧。

留神这里的 xy 和 ab 都是占位符,不是字符串。

相似于小学课本中一元二次方程中的未知数 x 和 y,咱们须要带入到下面的 hashCode 办法中去计算。

hashCode 算法,最次要的就是其中的这个 for 循环。

for 循环外面的有三个咱们不晓得是啥的货色:h,value.length 和 val[i]。咱们 debug 看一下:

h 初始状况下等于 0。

String 类型的底层构造是 char 数组,这个应该晓得吧。

所以,value.length 是字符串的长度。val[] 就是这个 char 数组。

把 xy 带入到 for 循环中,这个 for 循环会循环 2 次。

第一次循环:h=0,val[0]=x,所以 h=31*0+x,即 h=x。

第二次循环:h=x,val[1]=y,所以 h=31*x+y。

所以,通过计算后,xy 的 hashCode 为 31*x+y。

同理可得,ab 的 hashCode 为 31*a+b。

因为咱们想要构建 hashCode 一样的字符串,所以能够失去等式:

31_x+y=31_a+b

那么问题就来了:请问 x,y,a,b 别离是多少?

你算的进去吗?

你算的进去个锤子!黑板上的排列组合你不是舍不得解开,你就是解不开。

然而我能够解开,带大家看看这个题怎么搞。

数学课开始了。留神,我要变形了。

31_x+y=31_a+b 能够变形为:

31_x-31_a=b-y。

即,31(x-a)=b-y。

这个时候就清晰很多了,很显著,下面的等式有一个非凡解:

x-a=1,b-y=31。

因为,由上可得: 对于任意两个字符串 xy 和 ab,如果它们满足 x-a=1,即第一个字符的 ASCII 码值相差为 1,同时满足 b-y=31,即第二个字符的 ASCII 码值相差为 -31。那么这两个字符的 hashCode 肯定相等。

都曾经说的这么分明了,这样的组合对照着 ASCII 码表来找,不是一抓一大把吗?

Aa 和 BB,对不对?

Ab 和 BC,是不是?

Ac 和 BD,有没有?

好的。当初,咱们能够生成两个 HashCode 一样的字符串了。

咱们在略微加深一点点难度。假如我要构建 2 个以上 HashCode 一样的字符串该怎么办?

咱们先剖析一下。

Aa 和 BB 的 HashCode 是一样的。咱们把它两一排列组合,那不还是一样的吗?

比方这样的:AaBB,BBAa。

再比方我之前《震惊!ConcurrentHashMap 外面也有死循环?》这篇文章中呈现过的例子,AaAa,BBBB:

你看,神奇的事件就呈现了。

咱们有了 4 个 hashCode 一样的字符串了。

有了这 4 个字符串,咱们再去和 Aa,BB 进行组合,比方 AaBBAa,BBAaBB……

4*2=8 种组合形式,咱们又能失去 8 个 hashCode 一样的字符串了。

等等,我如同发现了什么法则似的。

如果咱们以 Aa,BB 为种子数据,通过屡次排列组合,能够失去任意个数的 hashCode 一样的字符串。字符串的长度随着个数减少而减少。

文字我还说不太分明,间接 show you code 吧,如下:

`public class CreateHashCodeSomeUtil {
    /**
     * 种子数据:两个长度为 2 的 hashCode 一样的字符串
     */
    private static String[] SEED = new String[]{“Aa”, “BB”};
    
    /**
     * 生成 2 的 n 次方个 HashCode 一样的字符串的汇合
     */
    public static List<String> hashCodeSomeList(int n) {
        List<String> initList = new ArrayList<String>(Arrays.asList(SEED));
        for (int i = 1; i < n; i++) {
            initList = createByList(initList);
        }
        return initList;
    }
    public static List<String> createByList(List<String> list) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < SEED.length; ++i) {
            for (String str : list) {
                result.add(SEED[i] + str);
            }
        }
        return result;
    }
}
`

通过下面的代码,咱们就能够生成任意多个 hashCode 一样的字符串了。

就像这样:

所以,别再问出这样的问题了:

有了这些 hashCode 一样的字符串,咱们把这些字符串都放到 HashMap 中,代码如下:

`public class HashMapTest {
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put(“Aa”, “Aa”);
        hashMap.put(“BB”, “BB”);
        hashMap.put(“AaAa”, “AaAa”);
        hashMap.put(“AaBB”, “AaBB”);
        hashMap.put(“BBAa”, “BBAa”);
        hashMap.put(“BBBB”, “BBBB”);
        hashMap.put(“AaAaAa”, “AaAaAa”);
        hashMap.put(“AaAaBB”, “AaAaBB”);
        hashMap.put(“AaBBAa”, “AaBBAa”);
        hashMap.put(“AaBBBB”, “AaBBBB”);
        hashMap.put(“BBAaAa”, “BBAaAa”);
        hashMap.put(“BBAaBB”, “BBAaBB”);
        hashMap.put(“BBBBAa”, “BBBBAa”);
        hashMap.put(“BBBBBB”, “BBBBBB”);
    }
}
`

最初这个 HashMap 的长度会通过两次扩容。扩容之后数组长度为 64:

然而外面只被占用了三个地位,别离是下标为 0,31,32 的中央:

画图如下:

看到了吧,刺不刺激,长度为 64 的数组,存 14 个数据,只占用了 3 个地位。

这空间利用率,也太低了吧。

所以,这样就算是 hack 了 HashMap。 祝贺你,把握了一项黑客攻击技术:hash 抵触 Dos。

如果你想理解的更多。能够看看石头哥的这篇文章:《没想到 Hash 抵触还能这么玩,你的服务中招了吗?》。

看到下面的图,不晓得大家有没有感觉有什么不对劲的中央?

如果没有,那么我再给你提醒一下: 数组下标为 32 的地位下,挂了一个长度为 8 的链表。

是不是,豁然开朗了。在 JDK 8 中,链表转树的阈值是多少?

所以,在以后的案例中,数组下标为 32 的地位下挂的不应该是一个链表,而是一颗红黑树。

对不对?

对个锤子对!有的同学,上课不认真,稍不留神就被带偏了。

这是不对的。 链表转红黑树的阈值是节点大于 8 个,而不是等于 8 的时候。

也就是说须要再来一个通过 hash 计算后,下标为 32 的、且 value 和之前的 value 都不一样的 key 的时候,才会触发树化操作。

不信,我给你看看当初是一个什么节点:

没有骗你吧?从下面的图片能够分明的看到,第 8 个节点还是一个一般的 node。

而如果是树化节点,它应该是长这样的:

不信,咱们再多搞一个 hash 抵触进来,带你亲眼看一下,代码是不会骗人的。

那么怎么多搞一个抵触进去呢?

最简略的,这样写:

这样抵触不就多一个了吗?我真是一个蠢才,不由自主的给本人鼓起掌来。

好了,咱们看一下当初的节点状态是怎么样的:

怎么样,是不是变成了 TreeNode,没有骗你吧?

另外,我还想多说一句,对于一个 HashMap 的面试题的一个坑。

面试官问:JDK 8 的 HashMap 链表转红黑树的条件是什么?

绝大部分背过面试八股文的敌人必定能答上来: 当链表长度大于 8 的时候。

这个答复正确吗?

是正确的,然而只正确了一半。

还有一个条件是数组长度大于 64 的时候才会转红黑树。

源码外面写的很分明,数组长度小于 64,间接扩容,而不是转红黑树:

感觉很多人都疏忽了“数组长度大于 64”这个条件。

背八股文,还是得背全了。

比方上面这种测试用例:

它们都会落到数组下标为 0 的地位上。

当第 9 个元素 BBBBAa 落进来的时候,会走到 treeifyBin 办法中去,然而不会触发树化操作,只会进行扩容操作。

因为以后长度为默认长度,即 16。不满足转红黑树条件。

所以,从上面的截图,咱们能够看到,标号为 ① 的中央,数组长度变成了 32,链表长度变成了 9,然而节点还是一般 node:

怎么样,有点意思吧,我感觉这样学 HashMap 乏味多了。

实体类当做 key

下面的示例中,咱们用的是 String 类型当做 HashMap 中的 key。

这个场景能笼罩咱们开发场景中的百分之 95 了。

然而偶然会有那么几次,可能会把实体类当做 key 放到 HashMap 中去。

留神啊,面试题又来了: 在 HashMap 中能够用实体类当对象吗?

那必须的是能够的啊。然而有坑,留神别踩进去了。

我拿前段时间看到的一个新闻给大家举个例子吧:

假如我要收集学生的家庭信息,用 HashMap 存起来。

那么我的 key 是学生对象,value 是学生家庭信息对象。

他们别离是这样的:

`public class HomeInfo {
    private String homeAddr;
    private String carName;
     // 省略革新办法和 toString 办法
}
public class Student {
    private String name;
    private Integer age;
     // 省略革新办法和 toString 办法
}
`

而后咱们的测试用例如下:

`public class HashMapTest {
    private static Map<Student, HomeInfo> hashMap = new HashMap<Student, HomeInfo>();
    static {
        Student student = new Student(“why”, 7);
        HomeInfo homeInfo = new HomeInfo(“ 大南街 ”, “ 自行车 ”);
        hashMap.put(student, homeInfo);
    }
    public static void main(String[] args) {
        updateInfo(“why”, 7, “ 滨江路 ”, “ 摩托 ”);
        for (Map.Entry<Student, HomeInfo> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey()+”-“+entry.getValue());
        }
    }
    private static void updateInfo(String name, Integer age, String homeAddr, String carName) {
        Student student = new Student(name, age);
        HomeInfo homeInfo = hashMap.get(student);
        if (homeInfo == null) {
            hashMap.put(student, new HomeInfo(homeAddr, carName));
        }
    }
}
`

初始状态下,HashMap 中曾经有一个名叫 why 的 7 岁小朋友了,他家住大南街,家里的交通工具是自行车。

而后,有一天他通知老师,他搬家了,搬到了滨江路去,而且家里的自行车换成了摩托车。

于是老师就通过页面,批改了 why 小朋友的家庭信息。

最初调用到了 updateInfo 办法。

嘿,你猜怎么着?

我带你看一下输入:

更新完了之后,他们班上呈现了两个叫 why 的 7 岁小朋友了,一个住在大南街,一个住在滨江路。

更新变新增了,你说神奇不神奇?

景象进去了,那么依据景象定位问题代码不是手到擒来的事儿?

很显著,问题就出在这个中央:

这里取出来的 homeInfo 为空了,所以才会新放一个数据进去。

那么咱们看看为啥这里为空。

跟着 hashMap.get() 源码进去瞅一眼:

标号为 ① 的中央是计算 key,也就是 student 对象的 hashCode。而咱们 student 对象并没有重写 hashCode,所以调用的是默认的 hashCode 办法。

这里的 student 是 new 进去的:

所以,这个 student 的 hashCode 势必和之前在 HashMap 外面的 student 不是一样的。

因而,标号为 ③ 的中央,通过 hash 计算后得出的 tab 数组下标,对应的地位为 null。不会进入 if 判断,这里返回为 null。

那么解决方案也就跃然纸上了: 重写对象的 hashCode 办法即可。

是吗?

等等,你回来,别拿着半截就跑。我话还没说完呢。

接着看源码:

HashMap put 办法执行的时候,用的是 equals 办法判断以后 key 是否与表中存在的 key 雷同。

咱们这里没有重写 equals 办法,因而这里返回了 false。

所以,如果咱们 hashCode 和 equals 办法都没有重写,那么就会呈现上面示意图的状况:

如果,咱们重写了 hashCode,没有重写 equals 办法,那么就会呈现上面示意图的状况:

总之一句话: 在 HashMap 中,如果用对象做 key,那么肯定要重写对象的 hashCode 办法和 equals 办法。否则,不仅不能达到预期的成果,而且有可能导致内存溢出。

比方下面的示例,咱们放到循环中去,启动参数咱们加上 -Xmx10m,运行后果如下:

因为每一次都是 new 进去的 student 对象,hashCode 都不尽相同,所以会不停的触发扩容的操作,最终在 resize 的办法抛出了 OOM 异样。

奇怪的常识又减少了

写这篇文章的时候我翻了一下《Java 编程思维 (第 4 版)》一书。

奇怪的常识又减少了两个。

第一个是在这本书外面,对于 HashMap 外面放对象的示例是这样的:

Groundhog:土拨鼠、旱獭。

Prediction:预言、预测、预报。

思考一个天气预报零碎,将土拨鼠和预报分割起来。

这 TM 是个什么读不懂的神仙需要?

幸好 why 哥学识渊博,闭上眼睛,去我的常识仓库外面搜寻了一番。

原来是这么一回事。

在美国的宾西法尼亚州,每年的 2 月 2 日,是土拨鼠日。

依据民间的说法,如果土拨鼠在 2 月 2 号出洞时见到本人的影子,而后这个小东西就会回到洞里持续蛰伏,示意春天还要六个星期才会到来。如果见不到影子,它就会进去觅食或者求偶,示意寒冬行将完结。

这就响应上了,通过判断土拨鼠出洞的时候是否能看到影子,从而判断冬天是否完结。

这样,需要就说的通了。

第二个奇怪的常识是这样的。

对于 HashCode 办法,《Java 编程思维 (第 4 版)》外面是这样写的:

我一眼就发现了不对劲的中央:result=37*result+c。

后面咱们才说了,基数应该是 31 才对呀?

作者说这个公式是从《Effective Java(第 1 版)》的书外面拿过去的。

这两本书都是 java 圣经啊,倡议大家把梦幻联动打在留言区上。

《Effective Java(第 1 版)》太长远了,我这里只有第 2 版和第 3 版的实体书。

于是我在网上找了一圈第 1 版的电子书,终于找到了对应形容的中央:

能够看到,书里给出的公式的确是基于 37 去计算的。

翻了一下第三版,一样的中央,给出的公式是这样的:

而且,你去网上搜:String 的 hashCode 的计算方法。

都是在争执为什么是 31。很少有人提到 37 这个数。

其实,我猜想,在晚期的 JDK 版本中 String 的 hashCode 办法应该用的是 37,起初改为了 31。

我想去下载最早的 JDK 版本去验证一下的,然而网上翻了个底朝天,没有找到适合的。

书外面为什么从 37 改到 31 呢?

作者是这样解释的,下面是第 1 版,上面是第 2 版:

用方框框起来的局部想要表白的货色是截然不同的,只是对象从 37 变成了 31。

而为什么从 37 变成 31,作者在第二版外面解释了,也就是我用下划线标注的局部。

31 有个很好的特许,即用位移和减法来代替乘法,能够失去更好的性能:

31*i==(i<<5)-1。古代的虚拟机能够主动实现这种优化。

从 37 变成 31,一个简略的数字变动,就能带来性能的晋升。

个中神秘,很有意思,有趣味的能够去查阅一下相干材料。

真是神奇的计算机世界。

好了,这次的文章就到这里啦。

满腹经纶,难免会有纰漏,如果你发现了谬误的中央,能够在留言区提出来,我对其加以批改。

感谢您的浏览,我保持原创,非常欢送并感谢您的关注。

我是 why 哥,一个被代码耽搁的文学创作者,不是大佬,然而喜爱分享,是一个又暖又有料的四川好男人。

欢送关注我呀。

退出移动版