题目

Java 中，对每个非 null 的字符串都可以调用 hashCode() 方法，hashCode() 方法的返回值是 int 类型的(这个返回值被称为hashCode)，所以理论上字符串的 hashCode 最多有 2^32 种取值，既然字符串有无穷多个，那么一定存在 hashCode 相等的字符串，请找到两个这样的字符串。

思路

String 对象的 hashCode 是如何计算的

先看一下 jdk 里面 java.lang.String 中 hashCode() 的实现。具体如下图

hashCode() in java.lang.String
简单的解释如下

public int hashCode() {
         // 起到缓存的效果, 防止反复计算 hashCode
        int h = hash;
        // 如果 h != 0, 说明已经计算过 hashCode 了, 直接返回缓存值即可
        if (h == 0 && value.length > 0) {
            char val[] = value;

            // 计算的核心步骤是这个 for 循环
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

看了源码后，就知道 String 的 hashCode 的计算过程了。例如 "ab" 的 hashCode 为

hashCode = 31 * 97 + 98;// 'a' 对应的整数是 97, 'b' 对应的整数是 98

如果字符串 s 的长度为 1, 那么它只包含一个 char, 这个 char 对应的 int 值就是 s 的 hashCode。
例如 "A", "B", "a", "b" 这四个String 的 hashCode 分别为 65, 66, 97(97=65+32), 98(98=66+32) 。
所以对两个长度为 1 的 String 而言，如果它们包含的 char 不同的话，其 hashCode 必然不等。

我们可以从长度为 2 的 String 入手。
如果字符串 s 长度为 2，则它的 hashCode 为

hashCode = s[0] * 31 + s[1]

如果 s[0]='A'，则

hashCode = 97 * 31 + s[1]

如果 s[0]='B'，则

hashCode = (97 + 1) * 31 + s[1]
// 也就是
hashCode = 97 * 31 + s[1] + 31

所以可以想到 "Aa" 和 "BB" 刚好满足要求。

"Aa".hashCode() == "BB".hashCode()

用到的程序如下

package com.naive.wow;

public class HashCode {
    public static void main(String[] args) {
        // 两者的 hashCode 都是 2112  
        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());
    }
}

简单的推广

假设字符串 s, t 长度都是 2。
则 s 的 hashCode 计算如下

s[0] * 31 + s[1]

t 的 hashCode 计算如下

t[0] * 31 + t[1]

如果二者的 hashCode 相等，那么就有

s[0] * 31 + s[1] == t[0] * 31 + t[1]

即

(s[0] - t[0]) * 31 == t[1] - s[1]

有了这样的结论后，就可以前往 https://codepoints.net/ 找到一些汉字来拼凑出满足要求的字符串了。

下图中展示了“三、个、上、下” 这四个汉字对应的 unicode

“三、个、上、下” 这四个汉字对应的 unicode

不难得到“三个”和“上下”这两个 String 的 hashCode 是相等的

运行结果

用到的程序如下

public class HashCode {
    public static void main(String[] args) {
        // 两者的 hashCode 都是 639297
        System.out.println("三个".hashCode());
        System.out.println("上下".hashCode());
    }
}