Comments 53
У стринга плохая хэш функция, к которой легко найти коллизии. Из-за этого до седьмой версии Java, при использовании строк в качестве ключей HashMap, нужно было следить, чтобы все ключи не легли в один и тот же бакет. Заменить хэш функцию на другую было нельзя, так как она описана в стандарте, поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.
Правда, как сказали ниже, у String хэш функция не дефолтная, поэтому что хотел сказать автор комментария действительно не совсем понятно.
однако у каждого вендора она может быть своя — о том как она должна вычисляться нет в java lang spec.
Её менять нельзя из-за того, что в java 7 появился switch по строкам. А он как раз реализован через switch (str.hashCode()), и компилятор вставляет предвычисленные хэш-коды прямо в байт-код.
Внутри case будет цепочка if/else if, где с помощью equals проверяется каждый вариант.
Отсутствие в компиляторе знания о том, как именно в этих объектах реализован hashCode. Отсутствие знания в компиляторе о том, как именно сконструировать экземпляр объекта в compile-time. Для частных случаев (например, строки, enum-ы) это знание есть.
Что "делается"? Инстанс объекта создаётся? Нет, ничего не создаётся, но вычисление hashCode требует знания, какое у объекта внутреннее состояния. Без знания логики конструирования объекта о внутреннем состоянии судить нельзя, следовательно невозможно вычислить hashCode.
Зачем компилятору вычислять hashCode? А как он сгенерит такое:
switch (str.hashCode()) {
case FOO_HASHCODE: if (o.equals("foo")) { ... } else goto default;
case BAR_HASHCODE: if (o.equals("bar")) { ... } else goto default;
default: { ... }
}Ну хорошо, мы можем и дальше так продолжать играть в вопросы. Давайте так, если есть что предложить — предлагайте (и даже можете кинуть JSR в JCP). Только не в духе "хорошо было бы сделать", а в духе "как ИМЕННО сделать" с учётом разных нюансов. Я уверяю, при попытке сформулировать предложение вы сами всё поймёте.
Ну а толку-то? По сути, не нужен для этого никакой цикл. Это будет эквивалентно какому-нибудь if..else if… else. На уровне синтаксиса это можно подсахарить. Вон, в Kotlin есть when, который по сути является сахаром для if..else if. Но чуда не ждите, на рантайме от этого быстрее не станет. Когда в Java 7 вводили switch по строкам, задизайнили фичу так, чтобы её можно было эффективно реализовать.
Проблема с функцией хэширования строки сильно старше седьмой джавы. Соответственно, когда появилась конструкция switch для строки — проблема уже была и ничего не мешало переопределить String.hashCode одновременно с вводом конструкции. Ничего, кроме спеки.
Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)
Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)
Что именно вы имеете в виду?
Что именно вы имеете в виду?
Ну, что будет, если в HashMap класть объекты с одинаковым хеш кодом.
Спасибо, познавательное чтиво. Особенно это:
I suppose I'd rule out Vo's variant and Weinberger's
function because of their added complexity, albeit minor. Of the remaining
four, I'd probably select P(31), as it's the cheapest to calculate on a RISC
machine (because 31 is the difference of two powers of two). P(33) is
similarly cheap to calculate, but it's performance is marginally worse, and
33 is composite, which makes me a bit nervous.
HotSpot JIT-компилятор давно умеет оптимизировать умножение на 31 через сдвиг и вычитание. С множителем 37 было бы хуже, конечно.
Хотя в исходниках до сих пор можно встретить подобную ручную «оптимизацию», например, в IdentityHashMap.
где-то это должно быть специфицировано, дабы не получить неожиданностей в поведении — может вы нашли это место?
Я так понимаю, это всё-таки не документируется в спеке языка. Т.е. компилятор может реализовывать switch по строкам в принципе как ему захочется. А вот в JDK это поведение чётко описано. Просто так особенности реализации в javadoc-ах не описывают, т.е. именно такой способ вычисления String.hashCode — это всё-таки публичный контракт. Учитывая особенности публичного контракта JDK, компилятор может порождать эффективную реализацию (что и делает javac).
String.hashCode — это всё-таки публичный контракт.
String.hashCode описан только в javadoc — в java lang spec его нет, ровно как и нет деталей о том, как компилировать switch(Strings) — формально любой другой вендор имеет право реализовывать свой String.hashCode и вроде как формально он не нарушает спецификацию языка, но как следствие — все либы, которые собраны с другим String.hashCode будут сломаны при использовании switch(String).
Выглядит скорее как дыра в спеке
- состоит из кучи документов
- имеет конкретную версию
То есть, нет спецификации «Java SE», а есть, например, спецификация «Java SE 8»:
Java SE 8 Platform Specification = JLS 8 + JVMS 8 + Java SE 8 API Specification (aka javadoc 8) + JOSS + Security + Extentions +…
String.hashCode прописан в спецификации Java SE API, и другие реализации Java SE не вправе его менять. А то, во что switch превращается — отдаётся на откуп компилятору. И javac генерирует код, который на любой Java SE-совместимой реализации будет корректен.спасибо
поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.
Не в седьмой, а в восьмой.
Ну и константное число запросов к мапке на один запрос к сервису обычно не приводит к эффективной DoS-атаке. А если оно у вас не константное, то частенько вы ССЗБ.
Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц
Это примерно как в 2000 году написать, что все бенчмарки прогонялись на Celeron :).
… задаёт вопрос человек, написавший три года назад статью ;)
Для остальных: http://mail.openjdk.java.net/pipermail/hotspot-runtime-dev/2013-January/005212.html
I have found no HotSpot flag that allows changing the default generator, so experimenting with other options might need to compile from source.Как же так? Про
-XX:hashCode=N уже миллион раз писали в блогах, твиттере, на Stack Overflow и пр.even if there is a single thread interested in the lock, the header word will be contended and require atomic operations to be handled correctly. Which defeats the whole point of biased locking.Объяснение про несовместимость Biased Lock с identityHashCode вообще жуткое: какие-то диаграммы состояний, перемещение заголовков, бла-бла-бла… Истинная же причина проста: в целях экономии места в заголовок помещается либо признак Biased-блокировки, либо identityHashCode. Только и всего.
UPD: Прочитал письмо, вроде похоже на правду.
Статья выглядит очень подозрительно с точки зрения осведомленности автора:
Диаграмма состояний и доказательство невозможности выглядит странно, хотя в том же комментарии в oopMark.hpp видно, что в заголовке просто не хватает места на хэшкод и указатель на поток + эпоху.
Когда за блокировку конкурируют два потока, привязанная блокировка отключается в любом случае, так что между двумя методам хеширования не наблюдается значимой разницы.
Это может и правда, но у автора в бенчмарке ошибка копипасты и в обоих случаях он синхронизируется на withoutIdHash
В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока
И в переводе, и в оригинале это звучит так, будто в 8 и 9 число уже неслучайное.
Оно все еще случайно, просто seed теперь thread-local (и не один), а сам генератор работает по-другому.
Ну и флаг для смены генератора конечно же есть.
Неужели это оправдано? Не проще ли было при создании объекта сразу проинициализировать его адресом или каким-то псевдослучайным числом?
Это выглядит как очень дешевое действие, которое отработает за пару тактов и ни на что особо не повлияет.
Мне кажется, или у меня в JVM 6 от Oracle хэш-коды, которые я вижу в отладчике, больше похожи именно на адреса в памяти (режим 1), т.к. идут строго последовательно для разных объектов? Или это не то, о чём я думаю?
Как работает hashCode() по умолчанию?