Java String hashCode 简单场景下的碰撞

前言

之前在研究 HashMap 的时候，想调试一下代码，看下两个string hash值一样的时候，代码逻辑是怎么样的
于是去研究了一下 String 的 hashCode 方法，总结了一点点结论
在这里贴出来，分享给大家

源码

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

hash 值默认为0

我们首先来分析一下源码，以三个字母 ABC 来分析一下
第一次循环完成 h=A (因为hash默认为0)
第二次循环完成 h= 31*h+B= 31*A+B
第三次循环完成 h= 31*h+C=31(31*A+B)+C
逻辑就是 31倍上一次计算的值，加上这次的ascii值

简单场景下的碰撞

分析完了代码，我们来探索一下简单场景下的碰撞
为什么说简单场景呢？因为我给这次的研究加了非常多的限制，避免研究不出来个啥

首先，第一个对象，限定字母个数为2， 在这里以 xy 代替，可以是 ab aa av mv等
第二个对象，限定字母个数为2 (位数一样，方便研究)，在这里以 jk 代替
目前变量还是有点多，我再限定一下，第二个对象为 (x+1)z
也就是第二个对象的第一个字母，在第一个对象第一个字母的基础上加1
我们在以上限定条件下探索一下 y 和 z 之间的关系，
如果能得到关系，那么就能在以上限定条件下，手动写出必定hash碰撞的字符串了

探索过程

首先看下第一个对象的 hashCode
xy= 31x+y

再看下第二个对象
(x+1)z = 31(x+1)+z=31x+31+z

我们希望 xy=(x+1)z，也就得到了
y=31+z => z=y-31

ASCII

ascii
观察一下 ascii 码，可以发现 大小写字母之间相差 32
所以结论也可以写为 z=y-32+1
也就是当 y为小写字母时，把这个字母转成大写，并递增一位

我们现在假定 第一个对象为 Ab
那么根据上面的限定条件，第二个对象的首字母为 B
第二个字母是 首先是 b 的大写 B，然后递增一位是 C，所以第二个对象为 BC

来验证一下我们的结论对不对
Ab BC
Bb CC
Ad BE