Почему не делает хэш-кода Строки () кэш 0?
Я заметил в исходном коде Java 6 для Строки, что хэш-код только кэши оценивает кроме 0. Разница в производительности показана следующим отрывком:
public class Main{
static void test(String s) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
s.hashCode();
}
System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
}
public static void main(String[] args) {
String z = "Allocator redistricts; strict allocator redistricts strictly.";
test(z);
test(z.toUpperCase());
}
}
Выполнение этого в ideone.com дает следующий вывод:
Took 1470 ms.
Took 58 ms.
Таким образом, мои вопросы:
- Почему не делает хэш-кода Строки () кэш 0?
- Какова вероятность, что строка Java хеширует к 0?
- Что лучший способ состоит в том, чтобы избежать потери производительности перевычислений значения хэш-функции каждый раз для строк тот хеш к 0?
- Действительно ли это - лучшая практика способ кэшировать значения? (т.е. кэш все кроме одного?)
Для Вашего развлечения каждая строка здесь является строкой, которые хешируют к 0:
pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.
4 ответа
Вы ни о чем не беспокоитесь. Вот способ подумать об этой проблеме.
Предположим, у вас есть приложение, которое не делает ничего, кроме хеширования строк в течение всего года. Скажем, он берет тысячу строк, все в памяти, многократно вызывает hashCode () для них циклически, миллион раз, затем получает еще тысячу новых строк и делает это снова.
И предположим, что вероятность того, что хеш-код строки будет равен нулю, на самом деле намного больше, чем 1/2 ^ 32. Я уверен, что это несколько больше, чем 1/2 ^ 32, но допустим, что это намного хуже, чем это, например, 1/2 ^ 16 (квадратный корень! Теперь это намного хуже!).
В этой ситуации от инженеров Oracle, улучшающих кэширование хэш-кодов этих строк, больше пользы, чем от кого-либо еще. Итак, вы пишете им и просите исправить это. И они творит чудеса, так что всякий раз, когда s.hashCode () равен нулю, он немедленно возвращает (даже в первый раз! Улучшение на 100%!). И предположим, что они делают это без снижения производительности в любом другом случае.
Ура! Теперь ваше приложение ... посмотрим ... на 0,0015% быстрее!
То, что раньше занимало целый день, теперь занимает всего 23 часа 57 минут и 48 секунд!
И помните, мы создали сценарий, чтобы дать все возможные преимущества сомнения, часто до смехотворной степени.
Вам кажется, что это того стоит?
РЕДАКТИРОВАТЬ: с тех пор, как я опубликовал это пару часов назад, я позволил одному из моих процессоров работать безумно в поисках фраз из двух слов с нулевым хэш-кодом. Пока что это придумано: bequirtle zorillo, chronogrammic schtoff, contusive cloisterlike, creashaks organzine, драмвуд болдерхед, электроаналитическое упражнение и, предпочтительно, неконструктивное. Это из примерно 2 ^ 35 возможных вариантов, поэтому при идеальном распределении мы ожидаем увидеть только 8. Очевидно, что к тому времени, когда это будет сделано, у нас будет в несколько раз больше, но не намного больше. Что еще более важно, теперь я придумал несколько интересных названий групп / альбомов! Нечестное воровство!
Он использует 0 для обозначения "я еще не разработал хэш-код". Альтернативой было бы использование отдельного булевского флага, который занимал бы больше памяти. (Или вообще не кэшировать хэш-код, конечно).
Я не ожидаю, что многие строки хэшируются в 0; возможно, имеет смысл, чтобы процедура хэширования намеренно избегала 0 (например, переводила хэш из 0 в 1 и кэшировала его). Это увеличит количество коллизий, но позволит избежать повторного хэширования. Однако сейчас это делать уже поздно, поскольку алгоритм String hashCode явно документирован.
Что касается того, хорошая ли это идея в целом: это, безусловно, эффективный механизм кэширования, и может (см. правку) стать еще лучше с изменением, чтобы избежать перехеширования значений, которые заканчиваются хэшем 0. Лично мне было бы интересно увидеть данные, которые привели Sun к выводу, что это стоит делать в первую очередь - это занимает дополнительные 4 байта для каждой когда-либо созданной строки, как бы часто или редко она ни хэшировалась, и единственная польза - для строк, которые хэшируются более одного раза.
EDIT: Как отмечает KevinB в комментарии в другом месте, предложение "избегать 0" выше вполне может иметь чистую стоимость, потому что оно помогает в очень редком случае, но требует дополнительного сравнения для каждого вычисления хэша.
- Почему не кеширует ли String hashCode () 0?
Нулевое значение зарезервировано как означающее «хэш-код не кэшируется».
- Какова вероятность того, что хэш-код строки Java равен 0?
Согласно Javadoc, формула для хэш-кода строки:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
с использованием арифметики int , где s [ i] - это i-й символ строки, а n - длина строки. (Хэш пустой строки определяется как ноль в качестве особого случая.)
Моя интуиция такова, что функция хеш-кода, как указано выше, дает равномерный разброс значений хеш-функции String в диапазоне значений int . Равномерный спред, который означал бы, что вероятность случайно сгенерированного хеширования String до нуля была 1 из 2 ^ 32.
- Как лучше всего избежать потери производительности из-за перерасчета хеш-значения каждый раз для строк, хеш-значение которых равно 0?
Лучшая стратегия - игнорировать эту проблему. Если вы многократно хешируете одно и то же значение String, ваш алгоритм выглядит довольно странно.
- Это лучший способ кэширования значений? (т.е. кэшировать все, кроме одного?)
Это компромисс между пространством и временем. AFAIK, альтернативы:
Добавить
cachedфлаг к каждому объекту String, заставляя каждую строку Java принимать дополнительное слово.Используйте верхний бит элемента хэша
Не кэшировать хэш-коды в строках вообще.
Я думаю, что разработчики Java сделали правильный выбор в отношении строк, и я уверен, что они провели обширное профилирование, которое подтверждает правильность своего решения. Однако из не следует, что это всегда лучший способ справиться с кэшированием.
(Обратите внимание, что есть два «общих» значения String, хэш которых равен нулю: пустая строка и строка, состоящая только из символа NUL. Однако затраты на вычисление хэш-кодов для этих значений невелики по сравнению с затратами вычисления хэш-кода для типичного значения String.)
0 не кэшируется, поскольку реализация интерпретирует кэшированное значение 0 как "кэшированное значение еще не инициализировано". В качестве альтернативы можно было бы использовать java.lang.Integer, где null означал бы, что значение еще не кэшировано. Однако это означало бы дополнительные накладные расходы на хранение.
Что касается вероятности того, что хэш-код строки будет вычислен как 0, я бы сказал, что вероятность довольно низкая и может произойти в следующих случаях:
- Строка пуста (хотя пересчет этого хэш-кода каждый раз эффективно O(1)).
- Происходит переполнение, при котором окончательно вычисленный хэш-код равен 0 (
например, Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0). - Строка содержит только символ Unicode 0. Очень маловероятно, так как это управляющий символ, не имеющий никакого значения, кроме как в "мире бумажной ленты" (!):
Из Wikipedia:
Код 0 (ASCII кодовое имя NUL) является особый случай. В бумажной ленте это случай, когда нет отверстий. Это удобно рассматривать его как символ заполнения символ не имеющий иного значения.