如何生成任意多个 HashCode 相同的字符串

摘要：本文基于 JDK9 深入分析了 String 的 hashcode 方法，并介绍了一种构造 hash 冲突的方法。

String 的 hashcode 方法

String 的 hashcode 的计算方法实际上是把 String 转化为 char 数组，每个 char 实际上就是一个整型，我们假设 char 的总数为 $n$，我们用 $S$ 表示 char 数组，hashcode 则可以使用以下数学公式计算，

$$HashCode(S) = S[0]*31^{n-1}+S[1]*31^{n-2}+...+S[n-2]*31+S[n-1]$$ $$HashCode(S) = \sum_{i=0}^{n-1}S[i]*31^{n-1-i}$$

有了数学基础我们可以再回顾一下源码，这里参考了 JDK9 的源码：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

重点在第二个函数，我们可以看到使用了一个循环遍历所有的 char，然后每次都将上一次的 h 乘以 31 在加上当前的 char。另外这里注意对弈 char 值使用了一个 v & 0xff，该语句的目的是只保留最后的 8 个 bit，由于 byte 在 Java 就是 8 个 bit，对于 8 位的 byte：v = v & 0xff。这里可能是预防有些 char 超过了 8 位做一个容错处理（具体意图还是需要研究）。

另外我写了一个测试函数，打印了计算过程

public static int hashCode(byte[] value) {
    System.out.println(Arrays.toString(value));
    int h = 0;
    System.out.println("h: " + h);
    StringBuilder hDisplay = new StringBuilder("0");
    int index = 0;
    for (byte v : value) {
        System.out.println(v + " binary: " + Integer.toBinaryString(Byte.toUnsignedInt(v)));
        System.out.println((v & 0xff) + " v & 0xff: " + Integer.toBinaryString(v & 0xff));
        // why use the v&0xff, just keep the last 8 bit of the byte, see this blog
        // https://oscarliang.com/what-s-the-use-of-and-0xff-in-programming-c-plus-p/
        if (index == 0)
            hDisplay = new StringBuilder("31 * " + hDisplay + " + " + v);
        else
            hDisplay = new StringBuilder("31 * (" + hDisplay + ") + " + v);

        h = 31 * h + (v & 0xff);
        System.out.println("h: " + h);
        System.out.println(hDisplay);
        index++;
    }
    int number = 31 * (31 * (31 * (31 * (31 * 66 + 66) + 66) + 66) + 66) + 66;
    System.out.println("test " + number);
    return h;
}

构造相同 hashcode 字符串的数学基础

我们再次回顾 hashcode 的数学公式：

$$HashCode(S) = S[0]*31^{n-1}+S[1]*31^{n-2}+...+s[n-2]*31+S[n-1]$$ $$HashCode(S) = \sum_{i=0}^{n-1}S[i]*31^{n-1-i}$$

我们先用两个 char 的数组举例来说明

假设有两个字符串 $S_a$ 和 $S_b$，其中 $S_a$ 为 [a2,a1]，$S_b$ 为 [b2,b1], 那么这两个字符串的 hashcode 分别为：

$$HashCode(S_a) = S_a[0]*31^1+S_a[1] = a2+a1*31 HashCode(S_b) = S_b[0]*31^1+S_b[1] = b2+b1*31$$

所以只要满足一下公式，两个字符串的 hashcode 将会一样

$$S_a[0]*31^1+S_a[1] = a2+a1*31 = S_b[0]*31^1+S_b[1] = b2+b1*31 a2+a1*31 = b2+b1*31 a2+a1*31 - b2 - b1*31 = 0 a2-b2 + (a1-b1)*31 = 0 (a1-b1)*31 = b2-a2$$

如果 a1-b1 = 1， 那么 b2-a2 = 31，上面的公式就可以成立。也就是说两个字符串后一位的 ASCII 值小1，那么前一位就要多 31 来弥补。

比如A:65，B:66，a:97，那么我们就可以构造字符串

Sa = "aA"
hashcode(Sa) = 'A'*31 + 'a' = 65*31+97 = 65*31+31+66 = (65+1)*31+66
Sb = "BB"
hashcode(Sb) = 'B'*31 + 'B' = 66*31+66

这样我就成功构造处理两个字符串的 hashcode 值一致了：“aA” 和 “BB”。逻辑上在 ASCII 字符表（256个字符）中只要能找到3个字符 a，b，c，这三个字符满足关系 b-a=1 && c-b=31，我们都可以通过这三个字符构造hashcode 相同的字符串

构造更长的随机字符串

上一节我们构造了两个字符的字符串，这样的字符串很少，难以满足我们需求，那么有什么办法可以构造更多的字符串有相同的 hashcode？

我们可以通过组合短的字符串来构造更多的长字符串

下面假设已经存在两组字符串，这两组字符串的 hashcode 是一致的

$$S_a S_b S_a' S_b'$$ $$HashCode(S_a) = \sum_{i=0}^{n-1}S_a[i]*31^{n-1-i}$$ $$HashCode(S_b) = \sum_{i=0}^{n-1}S_b[i]*31^{n-1-i}$$ $$HashCode(S_a') = \sum_{i=0}^{n-1}S_a'[i]*31^{n-1-i}$$ $$HashCode(S_b') = \sum_{i=0}^{n-1}S_b'[i]*31^{n-1-i}$$

假设 $S_1 = S_a + S_b$ 且 $S_2 = S_a’ + S_b’$ 那么我们来证明

那么我们来证明 S1 和 S2 的 hashcode 也是相同的。

要证明这个，我们只需要构造一个数学公式，来证明整个字符串的 hashcode 可以通过字符串的两步的 hashcode 来计算。

我们假设 char 的总数为 $n$，我们用 $S$ 表示 char 数组， $S$ 由两个字符串构成，$S_p$ 和 $S_k$，其长度分别为 $p$ 和 $k$ ，这样$p+k=n$。假设 $S_p$ 在前面，而$S_k$在后面，那么我来进一步推导 hashcode 计算的数学公式

$$HashCode(S) = S[0]*31^{n-1}+S[1]*31^{n-2}+...+S[n-2]*31+S[n-1]$$

我们用 p 和 k 来代替 n，n=p+k
通过分析我们可以知道，整个字符串的 hashcode，应该就是后半个字符串的 hashcode，加上前半个 hashcode 乘以 31的 后半个字符串长度次方

$$HashCode(S) = HashCode(P)*31^k + HashCode(K)$$ $$HashCode(S) = \sum_{i=0}^{n-1}S[i]*31^{n-1-i}$$

总结

综合上面的介绍，我们就可以开始构造相同 hashcode 的字符串了，首先有个种子，然后在根据需求构造字符串。

以下为一个样例代码

public class HashCUtil {

    private static String[] base = new String[] {"Aa", "BB"};

    public static List<String> generateN(int n)
    {
        if(n <= 0)
        {
            return null;
        }

        List<String> list = generateOne(null);
        for(int i = 1; i < n; ++i)
        {
            list = generateOne(list);
        }

        return list;
    }


    public static List<String> generateOne(List<String> strList)
    {   
        if((null == strList) || (0 == strList.size()))
        {
            strList = new ArrayList<String>();
            for(int i = 0; i < base.length; ++i)
            {
                strList.add(base[i]);
            }

            return strList;
        }

        List<String> result = new ArrayList<String>();

        for(int i = 0; i < base.length; ++i)
        {
            for(String str: strList)
            {   
                result.add(base[i]  + str);
            }
        }

        return result;      
    }
}