hashCode 等于 Integer.MIN_VALUE 的 Java 字符串

Question

是否存在 hashCode 完全等于 Integer.MIN_VALUE 的已知 Java 字符串？为哈希表编写测试有助于避免在执行余数运算之前在哈希码上运行 Math.Abs​​ 的常见错误。

理想情况下，该字符串仅包含 ASCII 字符，但我不确定它是否可行。

Answer 1

基于哈希码的公式（来自StringLatin1）：

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

它与字符线性相关，字符串越长、字符越大，哈希码就越大，直到溢出。另请注意，第一个字符对生成的哈希码（通常乘以 31）有更大的影响。

前两个算法的基本思想是从最左边的字符开始递增字符，直到哈希码变为负数，因为它具有更大的权重。搜索的字符串必须包含导致其在除最后一个位置之外的每个位置上溢出的字符之前的字符。

该代码开始测试字符串，"A", "AA", "AAA", ...直到开始返回负值 - 前一个字符串用作起始值。
现在，它开始递增第一个字符Z，直到找到具有负散列的字符串。对每个下一个角色执行相同的操作。由于此类字符串的哈希码尚未达到Integer.MIN_VALUE，因此需要进行一次额外的传递，以测试小写字符。这应该已经集成在上一个循环中...
现在最后一个字符被调整为精确地达到Integer.MIN_VALUE- 简单，因为最后一个字符只是被添加，没有乘法来计算哈希码。

这里是代码：

var string = "A";
while ((string+"A").hashCode() > 0) {
    string += "A";
}

var array = string.toCharArray();
var i = 0;
while (i < array.length) {
    array[i] += 1;
    if (array[i] > 'z' || new String(array).hashCode() < 0) {
        array[i] -= 1;
        i += 1;
        continue;
    }
}

i = 1;
while (i < array.length) {
    if (array[i] == 'Z') {
        array[i] = 'a';
    }else {
        array[i] += 1;
    }
    if (array[i] > 'Z' || new String(array).hashCode() < 0) {
        if (array[i] == 'a')
            array[i] = 'Z';
        else
            array[i] -= 1;
        i += 1;
        continue;
    }
}
int hash = new String(array).hashCode();
if (hash > 0) {
    array[array.length-1] += Integer.MAX_VALUE - hash + 1; 
}
System.out.printf("%s = %d%n", new String(array), new String(array).hashCode());

这导致：

HZcxf_ = -2147483648

合并前面代码的两个递增循环，我们有：

var string = "A";
while ((string+"A").hashCode() > 0) {
    string += "A";
}

var array = string.toCharArray();
var i = 0;
while (i < array.length) {
    var prev = array[i];
    if (prev == 'Z') {
        array[i] = 'a';
    } else {
        array[i] += 1;
    }
    if (array[i] > 'z' || new String(array).hashCode() < 0) {
        array[i] = prev;
        i += 1;
        continue;
    }
}
int hash = new String(array).hashCode();
if (hash > 0) {
    array[array.length-1] += Integer.MAX_VALUE - hash + 1; 
}
System.out.printf("%s = %d%n", new String(array), new String(array).hashCode());

结果（与之前略有不同）：

HZdZG_ = -2147483648

另一种方法将更强烈地基于哈希计算，基本上撤销它。
由于我不想使用负数，因此它以 开头Integer.MAX_VALUE，它比 少一Integer.MIN_VALUE（考虑上溢/下溢）。
首先，它找出必须除以多少次，31直到结果小于 128 (ASCII)，从而确定字符串长度。接下来，它循环并通过一些特殊处理找出每个字符，以避免小于“”的字符。
最后，最后一个字符加一，通过溢出将哈希码从 移动MAX_VALUE到MIN_VALUE。

var string = "";
var remain = Integer.MAX_VALUE;
var i = 0;
var multiplier = 1;
while (remain > 127) {
    remain /= 31;
    multiplier *= 31;
    i += 1;
}
remain = Integer.MAX_VALUE;
while (i >= 0) {
    var ch = (char)(remain / multiplier);
    remain -= ch * multiplier;
    multiplier /= 31;
    if (i > 0) {
        // correct if next ch will be less than ' '
        var correct = (' ' - (remain / multiplier) + 30) / 31;  // old fashion rounding
        if (correct > 0) {
            ch -= correct;
            remain += correct * 31 * multiplier;
        }
    } else {
        ch += 1;
    }
    string += ch;
    i -= 1;
}
System.out.printf("%s = %d%n", string, string.hashCode());

及其结果：

I='<*! = -2147483648

String注意：如果改变哈希码算法，最后的代码肯定会失败！前两个可能会失败，具体取决于哈希计算的更改方式。