Почему String.hashcode () имеет так много конфликтов?

Я читаю String.hashCode () в jdk1.6, ниже коды

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Это выглядит довольно запутанным для меня, потому что в нем столько конфликтов; хотя не обязательно быть уникальным (мы все еще можем полагаться на equals ()), но меньшее количество конфликтов означает лучшую производительность без посещения записей в связанном списке.

Предположим, у нас есть два символа, тогда, пока мы можем найти две строки, соответствующие приведенному ниже уравнению, тогда у нас будет тот же хэш-код ()

a * 31 +b = c * 31 +d

Будет легко сделать вывод, что(a-c) * 31 = d-b Возьмем простой пример: make a-c = 1 и d-b = 31; поэтому я написал ниже коды для простого теста

public void testHash() {
    System.out.println("A:" + (int)'A');
    System.out.println("B:" + (int)'B');
    System.out.println("a:" + (int)'a');

    System.out.println("Aa".hashCode() + "," + "BB".hashCode());
    System.out.println("Ba".hashCode() + "," + "CB".hashCode());
    System.out.println("Ca".hashCode() + "," + "DB".hashCode());
    System.out.println("Da".hashCode() + "," + "EB".hashCode());        
}

он выведет результаты ниже, что означает, что все строки имеют одинаковый хэш-код (), и это легко сделать в цикле.

A:65 
B:66
a:97
2112,2112
2143,2143
2174,2174
2205,2205

еще хуже, предположим, что у нас в строке 4 символа, в соответствии с алгоритмом, предположим, что первые 2 символа производят a2, вторые 2 символа производят b2; хеш-код все еще будетa2 * 31^2 + b2 таким образом, если a2 и b2 равны между двумя строками, мы получим больше строк с конфликтом hashcode (). такими примерами являются «AaAa», «BBBB» и т. д .; тогда у нас будет 6 символов, 8 символов ......

предположим, что большую часть времени мы используем символы в таблице ascii в строке, которая будет использоваться в хэш-карте или хеш-таблице, тогда выбранное простое число 31 здесь определенно слишком мало;

Одно простое решение - использовать большее простое число (к счастью, 257 - простое число), что позволяет избежать этого конфликта. конечно, выбор слишком большого числа приведет к переполнению возвращаемого значения int, если строка очень длинная, но я предполагаю, что большую часть времени строка, используемая в качестве ключа, не такая большая? Конечно, он все еще может вернуть длинное значение, чтобы избежать этого.

ниже моя модифицированная версия betterhash (), которая может легко разрешить такие конфликты, запустив коды, которые будут напечатаны ниже значений, что эффективно для решения этой проблемы.

16802,17028
17059,17285
17316,17542
17573,17799

но почему jdk это не исправляет? Спасибо.

@Test
public void testBetterhash() {
    System.out.println(betterHash("Aa") + "," + betterHash("BB"));      
    System.out.println(betterHash("Ba") + "," + betterHash("CB"));
    System.out.println(betterHash("Ca") + "," + betterHash("DB"));
    System.out.println(betterHash("Da") + "," + betterHash("EB"));
}

public static int betterHash(String s) {
    int h = 0;
    int len = s.length();

    for (int i = 0; i < len; i++) {
        h = 257*h + s.charAt(i);
    }
    return h;
}