Почему у String.hashCode () в Java много конфликтов? [закрыто]

В настоящее время этот вопрос не подходит для нашего формата вопросов и ответов. Мы ожидаем, что ответы будут подтверждены фактами, ссылками или опытом, но этот вопрос, скорее всего, повлечет за собой дебаты, аргументы, опросы или расширенное обсуждение. Если вы считаете, что этот вопрос можно улучшить и, возможно, снова открыть, посетите справочный центр , чтобы получить рекомендации.

Закрыт 6 лет назад .

Почему у 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

Легко сделать вывод, что (ac) * 31 = db Возьмем простой пример: сделать 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());        
}

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

даже хуже, предположим, что у нас 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;
}

задан Ragunath Jawahar 11 March 2013 в 12:26

0 ответов

Другие вопросы по тегам:

java string hashcode

Почему у String.hashCode () в Java много конфликтов? [закрыто]

0 ответов

Похожие вопросы: