Почему String hashCode () не кеширует 0?

Question

Я заметил в исходном коде Java 6 для String, что hashCode кэширует только значения, отличные от 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.

Итак, мои вопросы:

• Почему String hashCode () не кеширует 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.

Answer 1

Ты ни о чем не беспокоишься. Вот способ подумать об этой проблеме.

Предположим, у вас есть приложение, которое ничего не делает, кроме того, что весь год хэширует строки. Допустим, для этого требуется тысяча строк, все в памяти, они неоднократно вызывают hashCode () циклически, миллион раз, затем получают еще тысячу новых строк и делают это снова.

И предположим, что вероятность того, что хеш-код строки равен нулю, на самом деле намного больше 1/2 ^ 32. Я уверен, что это несколько больше, чем 1/2 ^ 32, но, скажем, это намного хуже, например, 1/2 ^ 16 (квадратный корень! Теперь это намного хуже!).

В этой ситуации у вас есть больше преимуществ от инженеров Oracle, которые улучшают способ кэширования хеш-кодов этих строк, чем кто-либо еще жив. Таким образом, вы пишете им и просите их исправить это. И они используют свою магию так, что когда s.hashCode () равен нулю, он возвращает мгновенно (даже в первый раз! Улучшение на 100%!). И скажем, что они делают это, не снижая производительность вообще для любого другого случая.

Ура! Теперь ваше приложение ... посмотрим ... на 0,0015% быстрее!

То, что раньше занимало целый день, теперь занимает всего 23 часа, 57 минут и 48 секунд!

И помните, мы создали сценарий, чтобы использовать все возможные преимущества сомнения, часто до смешной степени.

Вам это кажется, стоит?

РЕДАКТИРОВАТЬ: с тех пор, как я опубликовал это пару часов назад, я позволил одному из моих процессоров бездельничать в поисках фраз из двух слов с нулевыми хэш-кодами. До сих пор это придумали: bequirtle zorillo, хронограмма schtoff, контузивный подобный монастырю, creashaks органзин, валун головки барабана, электроаналитический осуществимый, и благоприятно неконструктивный. Это из примерно 2 ^ 35 возможностей, поэтому при идеальном распределении мы ожидаем увидеть только 8. Очевидно, что к тому времени, когда это будет сделано, у нас будет в несколько раз больше, но не намного больше. Что еще более важно, теперь я придумала несколько интересных названий групп / названий альбомов! Нет честного воровства!

Answer 2

Используется 0 для обозначения «Я еще не определил хеш-код».Альтернативой может быть использование отдельного логического флага, который занимал бы больше памяти.(Или, конечно, вообще не кэшировать хеш-код.)

Я не ожидаю, что много строк хэшируют до 0;возможно, было бы целесообразно, чтобы подпрограмма хеширования сознательно избегала 0 (например, преобразовывала хэш от 0 до 1 и кэшировала его).Это увеличит коллизии, но избегайте перефразировки.Сейчас уже слишком поздно делать это, поскольку алгоритм String hashCode явно задокументирован.

Что касается того, является ли это хорошей идеей в целом: это, безусловно, эффективный механизм кэширования, и может (см. редактирование), чтобы изменения были перефразированы со значениями, которые заканчиваются хэш-кодом 0. Будем еще лучше. Лично мне было бы интересно посмотреть на данные, которые привели Sun к выводу, что это стоит делать в первую очередь - она ​​принимаетдополнительные 4 байта для каждой когда-либо созданной строки, как бы часто или редко она ни хэшировалась, и единственное преимущество - для строк, которые хэшируются более одного раза .

РЕДАКТИРОВАТЬ: Как указывает КевинБ вкомментарий в другом месте, предложение «избежать 0», приведенное выше, вполне может иметь чистую стоимость , поскольку оно помогает в очень редком случае, но требует дополнительного сравнения для каждого хешарасчет.

Answer 3

Я думаю, что есть кое-что важное, что другие ответы пока отсутствуют: нулевое значение существует, чтобы механизм кэширования hashCode работал надежно в многопоточной среде.

Если у вас есть две переменные, такие как сам cachedHashCode и логическое значение isHashCodeCalculated для указания того, был ли рассчитан cachedHashCode, вам потребуется синхронизация потоков для работы в многопоточной среде. А синхронизация будет вредна для производительности, особенно потому, что строки часто используются в нескольких потоках.

Мое понимание модели памяти Java немного схематично, но вот примерно то, что происходит:

1. Когда несколько потоков обращаются к переменной (например, кешированный хэш-код), нет гарантии, что каждый поток увидит последнее значение. Если переменная начинается с нуля, то A обновляет ее (устанавливает ненулевое значение), затем поток B вскоре считывает ее, а поток B все еще может видеть нулевое значение.

2. Существует еще одна проблема с доступом к общим значениям из нескольких потоков (без синхронизации) - вы можете попытаться использовать объект, который был только частично инициализирован (создание объекта не является атомарным процессом). Многопоточные операции чтения и записи 64-битных примитивов, таких как long и double, также не обязательно являются атомарными, поэтому, если два потока пытаются прочитать и изменить значение long или double, один поток может в конечном итоге увидеть что-то странное и частично установленное , Или что-то подобное в любом случае. Существуют аналогичные проблемы, если вы пытаетесь использовать две переменные вместе, например, cachedHashCode и isHashCodeCalculated - поток может легко прийти и увидеть последнюю версию одной из этих переменных, но более старую версию другой.

3. Обычный способ обойти эти проблемы с многопоточностью - использовать синхронизацию. Например, вы можете поместить весь доступ к кэшированному hashCode внутри синхронизированного блока или использовать ключевое слово volatile (хотя будьте осторожны с этим, потому что семантика немного сбивает с толку).

4. Однако синхронизация замедляет работу. Плохая идея для чего-то вроде строки hashCode. Строки очень часто используются в качестве ключей в HashMaps, поэтому вам нужен метод hashCode, чтобы работать хорошо, в том числе в многопоточных средах.

5. Примитивы Java, которые 32-битные или менее, такие как int, являются специальными. В отличие, скажем, от long (64-битное значение), вы можете быть уверены, что никогда не будете читать частично инициализированное значение типа int (32 бита). Когда вы читаете int без синхронизации, вы не можете быть уверены, что получите последнее установленное значение, но вы можете быть уверены, что полученное вами значение является значением, которое было явно установлено в какой-то момент вашим потоком или другая тема.

Механизм кэширования hashCode в java.lang.String настроен на использование пункта 5 выше. Вы можете понять это лучше, посмотрев на источник java.lang.String.hashCode (). По сути, если несколько потоков вызывают hashCode одновременно, hashCode может в конечном итоге вычисляться несколько раз (либо если вычисленное значение равно нулю, либо если несколько потоков вызывают hashCode одновременно и оба видят нулевое кэшированное значение), но вы можете быть уверены, что hashCode () всегда будет возвращать одно и то же значение. Так что он надежный и эффективный (потому что в многопоточных средах нет синхронизации, которая могла бы стать узким местом).

Как я уже сказал, мое понимание модели памяти Java немного схематично, но я почти уверен, что правильно понял суть вышесказанного. В конечном счете, это очень умная идиома для кэширования hashCode без накладных расходов на синхронизацию.

Answer 4

0 не кэшируется, поскольку реализация интерпретирует кэшированное значение 0 как «кэшированное значение, еще не инициализированное». Альтернативой было бы использовать java.lang.Integer, при этом значение null подразумевало, что значение еще не было кэшировано. Однако это означало бы дополнительные затраты на хранение.

Что касается вероятности того, что хеш-код строки будет вычислен как 0, я бы сказал, что вероятность довольно мала и может произойти в следующих случаях:

• Строка пуста (хотя каждый раз при повторном вычислении этого хэш-кода получается O (1)).
• Переполнение происходит, когда окончательный вычисленный хэш-код равен 0 (e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0).
• Строка содержит только символ Unicode 0. Очень маловероятно, поскольку это контрольный символ, не имеющий никакого значения, кроме как в «мире бумажной ленты» (!):

Из Википедия :

Код 0 (кодовое имя ASCII NUL) является особый случай. В бумажной ленте это случай, когда нет отверстий. это удобно рассматривать это как заполнение символ без значения в противном случае .

Answer 5

Это хороший вопрос, связанный с уязвимостью безопасности .

"При хешировании строки Java также кэширует значение хеш-функции в атрибуте хеш-функции, но только если результат отличается от нуля. Таким образом, целевое значение ноль особенно интересно для злоумышленника, поскольку оно предотвращает кеширование и заставляет повторное хеширование. "

Answer 6

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

Конечно, реализация String не может быть изменена, но нет необходимости увековечивать проблему.

Answer 7

Ну, ребята, он сохраняет 0, потому что если это нулевая длина, он все равно будет равен нулю.

И это не займет много времени, чтобы выяснить, что len равен нулю, и поэтому хеш-код должен быть.

Итак, для вашего кода-reviewz! Вот во всей красе Java 8:

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

Как видите, всегда будет быстрый ноль, если строка пуста:

  if (h == 0 && value.length > 0) ...

Answer 8

• Почему String hashCode () не кеширует 0?

Нулевое значение зарезервировано как означающее "хеш-код не кэширован".

• Какова вероятность того, что строка Java хэшируется в 0?

Согласно Javadoc, формула для хеш-кода строки:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

с использованием int арифметики, где s[i] - это i-й символ строки, а n - длина строки. (Хеш пустой строки определяется как ноль в качестве особого случая.)

Моя интуиция заключается в том, что функция хэш-кода, описанная выше, обеспечивает равномерное распределение значений хеш-строк в диапазоне значений int. Равномерный разброс, который будет означать, что вероятность случайного генерирования хэширования строки в ноль была 1 в 2 ^ 32.

• Каков наилучший способ избежать потери производительности при повторном вычислении значения хеш-функции каждый раз для строк, хэш-значение которых равно 0?

Лучшая стратегия - игнорировать проблему. Если вы неоднократно хэшируете одно и то же значение String, в вашем алгоритме есть что-то довольно странное.

• Это лучший способ кэширования значений? (т.е. кэшировать все, кроме одного?)

Это компромисс между пространством и временем. AFAIK, альтернативы:

• Добавьте флаг cached к каждому объекту String, чтобы каждая строка Java заняла дополнительное слово.

• Использовать верхний бит элемента hash в качестве кэшированного флага. Таким образом, вы можете кэшировать все хеш-значения, но у вас есть только половина возможных строковых хеш-значений.

• Не кэшировать хеш-коды в строках вообще.

Я думаю, что Java-дизайнеры сделали правильный вызов для Strings, и я уверен, что они провели обширное профилирование, которое подтверждает правильность их решения. Однако из не следует , что всегда будет лучшим способом решения проблемы с кэшированием.

(Обратите внимание, что есть два «общих» строковых значения, которые хэшируются до нуля; пустая строка и строка, состоящая только из символа NUL. Однако стоимость вычисления хеш-кодов для этих значений мала по сравнению со стоимостью вычисления хеш-кода для типичного строкового значения.)