Почему String hashCode не имеет ограничения по размеру? - PullRequest
Новая
       21

Почему String hashCode не имеет ограничения по размеру?

1 голос
/ 08 мая 2019

Меня это некоторое время беспокоит, но я пока не нашел убедительного ответа, так почему функция hashCode в Java String не имеет ограничений по размеру? Ниже приведена реализация, которую я нашел здесь : 

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

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

Прежде всего я понимаю использование временной переменной h, которая имеет смысл при использовании String в нескольких потоках. Во-вторых, мы все знаем, что приведенная выше реализация не может избежать коллизий хеш-функций (ни одна реализация hashCode не может), поэтому в основном мы должны рассматривать эту функцию только как «повышение производительности», что полезно для хеш-таблиц или аналогичных структур.

Если это так, то зачем разрешать ситуацию, когда мы имеем, например, 100 МБ String и мы вычисляем хеш на основе все это символы? Разве не имеет смысла добавлять какие-то ограничения? 32/128, может быть, даже 1024 символа, но не целое значение. Длина? Да, если бы у нас было две разные строки с одинаковым префиксом, равным нашему пределу, то мы бы имели коллизию хешей, но мы все равно не можем избежать коллизий , поэтому с точки зрения производительности я бы лично изменил цикл for к чему-то вроде: 

int limit = value.length > 32 ? 32 : value.length;
for (int i = 0; i < limit; i++) {
    h = 31 * h + val[i];
}

Что вы думаете?

1 Ответ

3 голосов
/ 08 мая 2019

На ум приходит несколько возможных причин:

  1. Обычно строки изменяются только в начале или в конце, например, все URL-адреса вопросов StackOverflow начинаются с "https://stackoverflow.com/questions/".. Ограничение хэш-кода только подмножеством символов приведет к ненужным коллизиям, а для некоторых наборов строк - к коллизиям. Ваш предложенный алгоритм заставит каждый URL-адрес стекового потока иметь тот же хэш-код!

  2. hashCode быстр и запоминается, не ясно, что ограничение hashCode до некоторой постоянной длины принесет заметные улучшения производительности, особенно потому, что ему всегда предшествует создание String (операция O (n)), и часто с последующим вызовом equals (также O (n)).

  3. Унаследованные причины. String.hashcode указан для использования определенного алгоритма. Существующие приложения полагаются на эту спецификацию. Даже если бы эта оптимизация была сочтена необходимой, ее нельзя было бы сделать без нарушения обратной совместимости.

...