hashCode等于Integer.MIN_VALUE的Java字串-有解無憂

是否存在 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() is defined as:

Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1)   s[1]*31^(n-2)   ...   s[n-1]
using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

Now you just need to solve for -2147483648 (perhaps with the restriction of only printable ASCII chars: 32–127) :)

Or you brute-force (this will take a while):

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);
        }
    }
}

But allocating all those strings and string builders is expensive. Brute-forcing becomes feasible when we calculate the hash code manually from a char array:

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;
    }
}

In fact, there are lots of strings with a hash code identical to Integer.MIN_VALUE.

Length 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!

Length 7 (all of the strings below end with a space character); not all shown:

p4*|{e 
oS*|{e 
nr*|{e 
p3I|{e 
oRI|{e 
nqI|{e 
p2h|{e 
oQh|{e 
nph|{e

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/534832.html

標籤：爪哇测试哈希码

上一篇：ZSH：如何測驗一組檔案是否存在？

下一篇：Appium的免費測驗自動化替代品