是否存在 hashCode 完全等于 Integer.MIN_VALUE 的已知 Java 字串？這將有助于為哈希表撰寫測驗，以幫助避免在執行余數操作之前在哈希碼上運行 Math.Abs?? 的常見錯誤。
理想情況下，該字串只包含 ASCII 字符，但我不確定它是否可行。
uj5u.com熱心網友回復：
基于哈希碼的公式（來自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)，這決定了字串的長度。接下來它回圈并找出每個字符并進行一些特殊處理以避免字符小于 ' '。
最后，將最后一個字符遞增 1MAX_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注意：如果更改哈希碼演算法，最后的代碼肯定會失敗！前兩個可能會失敗，這取決于哈希計算如何更改。
uj5u.com熱心網友回復：
String#hashCode()定義為：
回傳此字串的哈希碼。String 物件的哈希碼計算如下
s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]使用 int 演算法，其中 s[i] 是字串的第 i 個字符，n 是字串的長度，^ 表示求冪。（空字串的哈希值為零。）
現在你只需要解決-2147483648（可能只有可列印的 ASCII 字符的限制：32-127）:)
或者你蠻力（這需要一段時間）：
public class HashFinder {
private static final int SIZE = 7;
private static long hashesCalculated = 0L;
public static void main(String[] args) {
hashesCalculated = 0L;
final long start = System.nanoTime();
findHash(SIZE);
final long duration = System.nanoTime() - start;
System.err.println("Checked strings of size " SIZE);
System.err.println(hashesCalculated " hashes in " TimeUnit.NANOSECONDS.toSeconds(duration) "s");
}
public static void findHash(final int size) {
findHash("", size);
}
public static void findHash(final String prefix, final int size) {
if (size <= 0) {
return;
}
final StringBuilder sb = new StringBuilder(prefix).append(' ');
for (char c = ' '; c < '~'; c) {
sb.setCharAt(prefix.length(), c);
final String s = sb.toString();
hashesCalculated;
if (s.hashCode() == Integer.MIN_VALUE) {
System.out.printf("Found string with min hashCode! '%s'%n", s);
}
findHash(s, size - 1);
}
}
}
但是分配所有這些字串和字串構建器是昂貴的。當我們從 char 陣列手動計算哈希碼時，暴力破解變得可行：
public class HashFinderBytes {
public static void main(String[] args) {
final char start = ' ', end = '~';
for (int size = 1; size <= 9; size ) {
char[] chars = new char[size];
Arrays.fill(chars, start);
final long startNano = System.nanoTime();
final long combinations = BigInteger.valueOf(end - start).pow(size).longValue();
System.err.println("Checking " combinations " strings of size " size);
for (long i = 0; i < combinations; i) {
if (hashCode(chars) == Integer.MIN_VALUE) {
System.out.printf("Found string with min hashCode! \"%s\"%n", new String(chars));
System.out.println("Sanity check: " (new String(chars).hashCode() == Integer.MIN_VALUE));
}
for (int j = 0; j < chars.length; j) {
chars[j];
if (chars[j] <= end) {
break;
}
chars[j] = (byte) start;
}
}
final long duration = System.nanoTime() - startNano;
final long millis = TimeUnit.NANOSECONDS.toMillis(duration);
System.err.println("in " millis "ms (" (combinations / millis) " ops/ms)");
}
}
public static int hashCode(char[] value) {
int h = 0;
for (char v : value) {
h = 31 * h (v & 0xff);
}
return h;
}
}
事實上，有很多字串的哈希碼與Integer.MIN_VALUE.
長度 6：
I='<*!
H\'<*!
G{'<*!
I<F<*!
H[F<*!
GzF<*!
I;e<*!
HZe<*!
Gye<*!
I=&[*!
H\&[*!
G{&[*!
I<E[*!
H[E[*!
GzE[*!
I;d[*!
HZd[*!
Gyd[*!
I=%z*!
H\%z*!
G{%z*!
I<Dz*!
H[Dz*!
GzDz*!
I;cz*!
HZcz*!
Gycz*!
I=';I!
H\';I!
G{';I!
I<F;I!
H[F;I!
GzF;I!
I;e;I!
HZe;I!
Gye;I!
I=&ZI!
H\&ZI!
G{&ZI!
I<EZI!
H[EZI!
GzEZI!
I;dZI!
HZdZI!
GydZI!
I=%yI!
H\%yI!
G{%yI!
I<DyI!
H[DyI!
GzDyI!
I;cyI!
HZcyI!
GycyI!
I=':h!
H\':h!
G{':h!
I<F:h!
H[F:h!
GzF:h!
I;e:h!
HZe:h!
Gye:h!
I=&Yh!
H\&Yh!
G{&Yh!
I<EYh!
H[EYh!
GzEYh!
I;dYh!
HZdYh!
GydYh!
I=%xh!
H\%xh!
G{%xh!
I<Dxh!
H[Dxh!
GzDxh!
I;cxh!
HZcxh!
Gycxh!
長度 7（以下所有字串均以空格字符結尾）；未全部顯示：
p4*|{e
oS*|{e
nr*|{e
p3I|{e
oRI|{e
nqI|{e
p2h|{e
oQh|{e
nph|{e
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/535630.html
標籤：爪哇测试哈希码