基于哈希码的公式(来自StringLatin1
):
public static int hashCode(byte[] value) {
int h = 0;
for (byte v : value) {
h = 31 * h + (v & 0xff);
}
return h;
}
它与字符线性相关,字符串越长、字符越大,哈希码就越大,直到溢出。另请注意,第一个字符具有更大的impact生成的哈希码(通常乘以 31)。
前两个算法的基本思想是从最左边的字符开始递增字符,直到哈希码变为负数,因为它具有更大的权重。搜索的字符串必须包含导致其在除最后一个位置之外的每个位置上溢出的字符之前的字符。
代码开始测试字符串"A", "AA", "AAA", ...
直到开始返回负值 - 前一个字符串用作起始值。
现在它开始将第一个字符增加到Z
或者直到找到具有负散列的字符串。对每个下一个角色执行相同的操作。
由于此类字符串的哈希码尚未达到Integer.MIN_VALUE
,完成了一次额外的传递,以测试小写字符。这应该已经集成到之前的循环中......
现在最后一个字符是adjusted准确地到达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
to 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
改变了!前两个可能会失败,具体取决于哈希计算的更改方式。