company_banner

Как работает hashCode() по умолчанию?

https://srvaroa.github.io/jvm/java/openjdk/biased-locking/2017/01/30/hashCode.html
  • Перевод

Попытка заглянуть вглубь hashCode() привела к спелеологическому путешествию по исходному коду JVM, с рассмотрением структуры объектов и привязанной блокировки (biased locking), а также удивительных последствий для производительности, связанных с использованием hashCode() по умолчанию.

Тривиальная загадка


Недавно в рабочем проекте я внёс в класс тривиальное изменение: реализацию toString(), чтобы от логов была польза. К моему удивлению, это привело примерно к 5-процентному уменьшению покрытия (coverage drop) класса. Я знал, что весь новый код покрывался уже имевшимися модульными тестами, так в чём же дело? При анализе отчётов о покрытии мой коллега заметил, что реализация hashCode() покрывалась только до внесения изменений, а не после. Причина была понятна: по умолчанию toString() вызывает hashCode():

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

После корректирования toString() наш кастомный hashCode() перестал вызываться. Мы пропустили тест.

Все знали, что собой представляет реализация по умолчанию toString(), но…

Чем является реализация по умолчанию hashCode()?


Реализация по умолчанию hashCode() возвращает значение, которое называется идентификационный хеш (identity hash code). Я и дальше буду использовать это значение, чтобы отличать его от хешей, генерируемых переопределёнными реализациями hashCode(). Для сведения: даже если класс переопределяет hashCode(), вы всегда можете получить идентификационный хеш объекта o с помощью вызова System.identityHashCode(o).

Здравый смысл подсказывает, что идентификационный хеш использует целочисленное представление адреса памяти. Об этом свидетельствует документация J2SE на Object.hashCode():

...обычно реализуется с помощью конвертации внутреннего адреса объекта в целочисленное значение, но в Java эта методика не требуется.

Однако с этим связаны проблемы, поскольку контракт метода (method contract) требует:

При применении к одному и тому же объекту более одного раза в ходе выполнения Java-приложения метод hashCode должен в обязательном порядке возвращать одно и то же целочисленное значение.

Учитывая, что JVM будет перемещать объекты (например, при сборке мусора в ходе продвижения или уплотнения), после вычисления идентификационного хеша объекта мы должны сделать так, чтобы он как-то отслеживал местоположение самого объекта.

Например, можно взять текущую позицию объекта в памяти при первом вызове hashCode() и сохранить её где-нибудь, например в заголовке объекта. Тогда при перемещении объекта в другое место с ним переедет и исходный хеш. Недостаток способа: два объекта могут иметь одинаковый хеш, но это разрешено спецификацией.

Лучшим подтверждением будет посмотреть в исходный код. К сожалению, дефолтная java.lang.Object::hashCode() является нативной функцией:

public native int hashCode();

Надеть каски!

Настоящий hashCode()


Обратите внимание, что идентификационная реализация hashCode() зависит от JVM. Я буду рассматривать только исходный код OpenJDK, помните об этом при каждом дальнейшем упоминании JVM. Все ссылки относятся к набору изменений 5934:87ee5ee27509 дерева Hotspot, и полагаю, что большинство из них применимы и к Oracle JVM, но в других машинах есть свои нюансы.

OpenJDK определяет входную точку hashCode() в src/share/vm/prims/jvm.h и src/share/vm/prims/jvm.cpp. Последняя содержит:

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  JVMWrapper("JVM_IHashCode");
// как реализовано в классической виртуальной машине; возвращает 0, если объект NULL
  return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END

ObjectSynchronizer::FastHashCode() также вызывается из identity_hash_value_for, который используется и несколькими другими точками вызова (например, System.identityHashCode())

intptr_t ObjectSynchronizer::identity_hash_value_for(Handle obj) {
  return FastHashCode (Thread::current(), obj()) ;
}

Можно наивно ожидать, что ObjectSynchronizer::FastHashCode() делает что-то вроде:

if (obj.hash() == 0) {
    obj.set_hash(generate_new_hash());
}
return obj.hash();

Но оказывается, что там функция на сотню строк. А это куда сложнее. По крайней мере, мы можем отметить пару блоков «если-не-существует-то-генерировать»:

mark = monitor->header();
...
hash = mark->hash();
if (hash == 0) {
  hash = get_next_hash(Self, obj);
...
}
...
return hash;

Это подтверждает нашу гипотезу. Пока что проигнорируем monitor и удовлетворимся получением заголовка объекта. Он хранится в mark, указателе на экземпляр markOop, который представляет слово mark, принадлежащее младшим битам заголовка объекта. Итак, попытаемся засунуть хеш в слово mark. Если он отсутствует, то сгенерируем с помощью get_next_hash, сохраним и вернём.

Реальное генерирование идентификационного хеша


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

0. Случайно сгенерированное число.
1. Функция адреса объекта в памяти.
2. Жёстко запрограммированное значение 1 (используется при тестировании на чувствительность (sensitivity testing)).
3. Последовательность.
4. Адрес объекта в памяти, приведённый к целочисленному значению.
5. Состояние потока, объединённое с xorshift (https://en.wikipedia.org/wiki/Xorshift)

Какой метод используется по умолчанию? Согласно globals.hpp, в OpenJDK 8 это метод 5:

product(intx, hashCode, 5,
         "(Unstable) select hashCode generation algorithm")

То же самое и в OpenJDK 9. В OpenJDK 7 и OpenJDK 6 используется первый метод, генератор случайных чисел.

Так что, если я не ошибаюсь, как минимум с шестой версии реализация по умолчанию hashCode в OpenJDK не имеет ничего общего с адресом памяти.

Заголовки объектов и синхронизация


Вернёмся немного и рассмотрим пару пропущенных моментов. Во-первых, функция ObjectSynchronizer::FastHashCode() выглядит слишком сложной, в ней используется больше 100 строк кода для выполнения того, что мы считали тривиальной операцией «получить-или-сгенерировать». Во-вторых, что это вообще такое – monitor – и почему у него есть заголовки нашего объекта?

Структура слова mark — хорошее место для начала изысканий. В OpenJDK она выглядит так:

// markOop описывает заголовок объекта.
//
// Обратите внимание, что mark — это не настоящий oop, а просто слово.
// Оно находится в иерархии oop по историческим причинам.
//
// Бит-формат заголовка объекта (сначала самые важные, дальше по убыванию):
//
//  32 битные:
//  --------
//             hash:25 ------------>| age:4    biased_lock:1 lock:2 (нормальный объект)
//             JavaThread*:23 epoch:2 age:4    biased_lock:1 lock:2 (привязанный (biased) объект)
//             size:32 ------------------------------------------>| (блок без CMS (CMS free block))
//             PromotedObject*:29 ---------->| promo_bits:3 ----->| (объект, продвигаемый (promoted) CMS)
//
//  64 bits:
//  --------
//  unused:25 hash:31 -->| unused:1   age:4    biased_lock:1 lock:2 (нормальный объект)
//  JavaThread*:54 epoch:2 unused:1   age:4    biased_lock:1 lock:2 (привязанный объект)
//  PromotedObject*:61 --------------------->| promo_bits:3 ----->| (объект, продвигаемый CMS)
//  size:64 ----------------------------------------------------->| (блок без CMS)
//
//  unused:25 hash:31 -->| cms_free:1 age:4    biased_lock:1 lock:2 (COOPы && нормальный объект)
//  JavaThread*:54 epoch:2 cms_free:1 age:4    biased_lock:1 lock:2 (COOPы && привязанный объект)
//  narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPы && объект, продвигаемый CMS)
//  unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPы && блок без CMS)

Для 32 и 64 битов формат несколько различается. Во втором случае могут быть два варианта, в зависимости от того, включены ли указатели сжатых объектов (Compressed Object Pointers). В Oracle и OpenJDK 8 по умолчанию они включены.

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

Но в других состояниях указатель связан с JavaThread или PromotedObject. Дело усложняется: если поместить идентификационный хеш в «нормальный объект», то извлечёт ли его кто-нибудь? И куда? Если объект привязан (biased), то куда мы можем поместить хеш? Что такое привязанный объект?

Попробуем ответить на все эти вопросы.

Привязанная блокировка (biased locking)


Привязанные объекты — это результат привязанной блокировки. Это запатентованный механизм, по умолчанию используемый начиная с HotSpot 6. Он пытается снизить стоимость блокирования объектов. Подобные операции дороги, поскольку ради безопасной обработки запросов блокировки/разблокировки объекта от разных потоков их реализации часто опираются на атомарные процессорные инструкции (сравнение с обменом). Но подмечено, что во многих реализациях большинство объектов когда-либо блокируются лишь одним потоком, так что использование атомарных операций зачастую расточительно. Чтобы этого избежать, JVM’ы с привязанной блокировкой позволяют потокам попытаться самостоятельно «привязать» объект. Когда потоку это удаётся, он может блокировать/разблокировать объект без использования атомарных инструкций. А раз у нас нет потоков, борющихся за один и тот же объект, то мы получаем прирост производительности.

Бит biased_lock в заголовке обозначает, привязан ли объект к потоку, указанному в JavaThread*. Биты lock обозначают, заблокирован ли объект.

В OpenJDK реализация привязанной блокировки требует прописывать указатель в слове mark, и в результате нужно также перемещать само слово mark (содержащее идентификационный хеш).
Это может объяснить повышенную сложность FastHashCode. Заголовок содержит не только идентификационный хеш, но и состояние блокировки (указатель на поток, установивший блокировку). Поэтому нам нужно рассмотреть все случаи и определить месторасположение идентификационного хеша.

Начнём с FastHashCode. Первое, что мы обнаруживаем:

intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
  if (UseBiasedLocking) {
    if (obj->mark()->has_bias_pattern()) {
      ...
      BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
      ...
      assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
    }
  }

Погодите. Здесь просто отменяются привязка и привязанная блокировка объекта (метод false означает «не пытайся снова привязать»). Несколькими строками ниже это остаётся действительно неизменным:

// объект должен оставаться недоступным для привязанной блокировки
assert (!mark->has_bias_pattern(), "invariant") ;

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

Чёрт возьми.

Почему сохранение состояния привязанной блокировки конфликтует с сохранением идентификационного хеша?


Для ответа на этот вопрос мы должны понять, где может находиться слово mark (содержащее идентификационный хеш) в зависимости от состояния блокировки объекта. Ниже показаны возможные переходы:



Моё (возможно, ошибочное) мнение таково.

Для четырёх состояний в верхней части схемы OpenJDK сможет использовать представления thin-блокировок. В простейшем случае (без блокировок) это означает хранение идентификационного хеша и других данных прямо в пространстве слова mark в объекте:

unused:25 hash:31 -->| unused:1   age:4    biased_lock:1 lock:2 (нормальный объект)

В более сложных случаях это пространство используется для хранения указателя на «запись о блокировке». Тогда слово mark будет «перемещено» в другое место.

Поскольку заблокировать объект у нас только пытается один поток, этот указатель фактически ссылается на область памяти в собственном стеке потока. Это хорошо по двум причинам:

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

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

Нашим нуждам удовлетворяет структура ObjectMonitor, которая на схеме называется «тяжёлый монитор». Оставшееся в заголовке объекта значение указывает не на «перемещённое слово mark», а на реальный объект (монитор). Теперь для доступа к идентификационному хешу требуется «получить монитор» (inflating the monitor): сделать указатель на объект и считывать/изменять в зависимости от поля, содержащего перемещённое слово mark. Это дороже и требует координации.

Есть работа и для FastHashCode.

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

Начиная с L682 придётся стиснуть зубы:

// Получаем монитор для сохранения хеша
monitor = ObjectSynchronizer::inflate(Self, obj);

// Загружаем перемещённый заголовок и проверяем на наличие хеша
mark = monitor->header();
...
hash = mark->hash();

Если тут есть id. hash (hash != 0), то JVM может его вернуть. В противном случае мы можем получить его от get_next_hash и спокойно сохранить в перемещённом заголовке, который содержится в ObjectMonitor.

Это даёт разумное объяснение, почему вызов hashCode() применительно к объекту класса, который не переопределяет реализацию по умолчанию, делает объекты недоступными для привязанной блокировки:

  • Чтобы сохранять консистентность идентификационного кеша после перемещения, нам нужно хранить хеш в заголовке объекта.
  • Потоки, запрашивающие идентификационный хеш, могут вообще не заморачиваться блокировкой объекта. Но на практике они будут совместно использовать структуры данных, применяемые механизмом блокировки. Это очень сложная система, поскольку она может не только менять, но и перемещать содержимое заголовков.
  • Привязанная блокировка помогает выполнять операции блокирования/разблокирования без использования атомарных операций. Это эффективно до тех пор, пока объект блокируется лишь одним потоком, потому что нам нужно хранить состояние блокировки в слове mark. Я не совсем уверен, но, как я понял, поскольку другие потоки могут запрашивать идентификационный хеш, даже если блокировка нужна лишь одному потоку, слово header будет конкурентным и для корректной обработки потребуется использовать атомарные операции. Что лишает смысла привязанную блокировку.

Промежуточные итоги


  • Реализация по умолчанию hashCode() (идентификационного хеша) не имеет отношения к адресу памяти объекта, как минимум в OpenJDK. В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Здесь проведён тест, который привёл к такому же выводу.
    • Доказательство предупреждений «зависит от реализации» не для эстетики: Azul’s Zing действительно генерирует идентификационный хеш на основании адреса памяти объекта.
  • В HotSpot идентификационный хеш генерируется лишь раз, а затем кешируется в слове mark в заголовке объекта.
    • В Zing для сохранения консистентности при перемещениях используется механизм задержки сохранения id.hash до тех пор, пока объект не переместится. В данном случае хеш хранится в «предзаголовке».
  • В HotSpot вызов дефолтного hashCode() или System.identityHashCode() приводит к недоступности объекта для привязанной блокировки.
    • Это означает, что при синхронизации объектов, не имеющих разногласий, вам лучше переопределить реализацию по умолчанию hashCode(), иначе вы не сможете воспользоваться оптимизациями JVM.
  • В HotSpot можно для каждого объекта в отдельности отключать привязанную блокировку.
    • Это очень полезная возможность. Мне встречались приложения, в которых очень часто возникают разногласия между очередями создания/потребления; привязанная блокировка больше мешала, чем помогала, так что приходилось её отключать. Мы делали это только для конкретных объектов/классов, просто вызывая применительно к ним System.identityHashCode().
  • Я не нашёл в HotSpot флага, позволяющего менять генератор по умолчанию, так что эксперименты с другими опциями могут потребовать компилирования из исходников.

Бенчмарки


Для проверки своих умозаключений я написал простой тест JMH.

Бенчмарк (исходник) делает нечто вроде этого:

object.hashCode();
while(true) {
    synchronized(object) {
        counter++;
    }
}

Одна конфигурация (withIdHash) синхронизирует объект, который использует идентификационный хеш, так что можно ожидать, что привязанная блокировка будет отключена при вызове hashCode(). Вторая конфигурация (withoutIdHash) реализует кастомный хеш, при котором привязанная блокировка не отключается. Каждая конфигурация сначала прогоняется с одним потоком, затем с двумя (они получают суффикс Contended).

Кстати, необходимо включить -XX:BiasedLockingStartupDelay=0, а иначе JVM понадобится четыре секунды на запуск оптимизации, что исказит результат.

Первый запуск:

Benchmark                                       Mode  Cnt       Score      Error   Units
BiasedLockingBenchmark.withIdHash              thrpt  100   35168,021 ±  230,252  ops/ms
BiasedLockingBenchmark.withoutIdHash           thrpt  100  173742,468 ± 4364,491  ops/ms
BiasedLockingBenchmark.withIdHashContended     thrpt  100   22478,109 ± 1650,649  ops/ms
BiasedLockingBenchmark.withoutIdHashContended  thrpt  100   20061,973 ±  786,021  ops/ms

Кастомный хеш в четыре раза ускоряет цикл блокировки/разблокировки по сравнению с идентификационным хешем (который отключает привязанную блокировку). Когда за блокировку конкурируют два потока, привязанная блокировка отключается в любом случае, так что между двумя методам хеширования не наблюдается значимой разницы.

При втором запуске привязанная блокировка отключается (-XX:-UseBiasedLocking) во всех конфигурациях.

Benchmark                                       Mode  Cnt      Score      Error   Units
BiasedLockingBenchmark.withIdHash              thrpt  100  37374,774 ±  204,795  ops/ms
BiasedLockingBenchmark.withoutIdHash           thrpt  100  36961,826 ±  214,083  ops/ms
BiasedLockingBenchmark.withIdHashContended     thrpt  100  18349,906 ± 1246,372  ops/ms
BiasedLockingBenchmark.withoutIdHashContended  thrpt  100  18262,290 ± 1371,588  ops/ms

Метод хеширования больше не влияет на результат, и withoutIdHash теряет своё преимущество.

Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц.

Ссылки


Всё, что не является дикими спекуляциями и моими слабыми рассуждениями в попытке осмыслить исходные коды JVM, собрано из разных источников. Основные из них:

Mail.Ru Group 562,84
Строим Интернет
Поделиться публикацией
Комментарии 51
  • 0
    Спасибо за очередную хорошую статью.)
    • –3
      Самое большое доказательство того, что String нельзя юзать как key в HashMap.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +4

          У стринга плохая хэш функция, к которой легко найти коллизии. Из-за этого до седьмой версии Java, при использовании строк в качестве ключей HashMap, нужно было следить, чтобы все ключи не легли в один и тот же бакет. Заменить хэш функцию на другую было нельзя, так как она описана в стандарте, поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.


          Правда, как сказали ниже, у String хэш функция не дефолтная, поэтому что хотел сказать автор комментария действительно не совсем понятно.

          • 0
            Она описана в javadoc к java.lang.String — менять в рамках одного вендора (и все кто базуируется на OpenJDK) не будут ибо сломают обратную совместимость,

            однако у каждого вендора она может быть своя — о том как она должна вычисляться нет в java lang spec.
            • +3

              Её менять нельзя из-за того, что в java 7 появился switch по строкам. А он как раз реализован через switch (str.hashCode()), и компилятор вставляет предвычисленные хэш-коды прямо в байт-код.

              • 0
                спасибо, это тоже аргумент
                • НЛО прилетело и опубликовало эту надпись здесь
                  • 0

                    Внутри case будет цепочка if/else if, где с помощью equals проверяется каждый вариант.

                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +1

                        Отсутствие в компиляторе знания о том, как именно в этих объектах реализован hashCode. Отсутствие знания в компиляторе о том, как именно сконструировать экземпляр объекта в compile-time. Для частных случаев (например, строки, enum-ы) это знание есть.

                        • НЛО прилетело и опубликовало эту надпись здесь
                          • 0

                            Что "делается"? Инстанс объекта создаётся? Нет, ничего не создаётся, но вычисление 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). Только не в духе "хорошо было бы сделать", а в духе "как ИМЕННО сделать" с учётом разных нюансов. Я уверяю, при попытке сформулировать предложение вы сами всё поймёте.

                            • НЛО прилетело и опубликовало эту надпись здесь
                              • 0

                                Ну а толку-то? По сути, не нужен для этого никакой цикл. Это будет эквивалентно какому-нибудь if..else if… else. На уровне синтаксиса это можно подсахарить. Вон, в Kotlin есть when, который по сути является сахаром для if..else if. Но чуда не ждите, на рантайме от этого быстрее не станет. Когда в Java 7 вводили switch по строкам, задизайнили фичу так, чтобы её можно было эффективно реализовать.

                                • 0

                                  Проблема с функцией хэширования строки сильно старше седьмой джавы. Соответственно, когда появилась конструкция switch для строки — проблема уже была и ничего не мешало переопределить String.hashCode одновременно с вводом конструкции. Ничего, кроме спеки.


                                  Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)

                                  • +2
                                    ломать обратную совместимость — слишком дорогое удовольствие — и ломали её один раз — в 1.2.0 — java bug #4045622

                                    Основную проблему, связанную с поломкой хэш кода для строк, кстати, зарешали именно в седьмой ждаве, путём внесения изменений в HashMap :)


                                    Что именно вы имеете в виду?
                                    • 0
                                      Что именно вы имеете в виду?

                                      Ну, что будет, если в HashMap класть объекты с одинаковым хеш кодом.

                                      • +1
                                        в 7ке как был chaining так и остался, в 8ке будет дерево, если превышен порог коллизий
                                        • 0

                                          Действительно. Спасибо, надеюсь теперь запомню надолго.

                                      • 0

                                        Спасибо, познавательное чтиво. Особенно это:


                                        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 было бы хуже, конечно.

                                        • +2
                                          С другой стороны, процессоры тоже давно умеют оптимизировать умножение на аппаратном уровне. Таким образом, strength reduction умножения потеряла первоначальную ценность и теперь, скорее, вредит:



                                          Хотя в исходниках до сих пор можно встретить подобную ручную «оптимизацию», например, в IdentityHashMap.
                    • +1
                      кстати — вот ещё раз попытался покопаться в java lang spec — и ничего не говорится о том как именно реализован switch(String) — т.е одно дело openjdk (или производный от него) javac создаст класс — а как его потом будут выполнять другие vm?

                      где-то это должно быть специфицировано, дабы не получить неожиданностей в поведении — может вы нашли это место?
                      • +1

                        Я так понимаю, это всё-таки не документируется в спеке языка. Т.е. компилятор может реализовывать switch по строкам в принципе как ему захочется. А вот в JDK это поведение чётко описано. Просто так особенности реализации в javadoc-ах не описывают, т.е. именно такой способ вычисления String.hashCode — это всё-таки публичный контракт. Учитывая особенности публичного контракта JDK, компилятор может порождать эффективную реализацию (что и делает javac).

                        • 0
                          String.hashCode — это всё-таки публичный контракт.


                          String.hashCode описан только в javadoc — в java lang spec его нет, ровно как и нет деталей о том, как компилировать switch(Strings) — формально любой другой вендор имеет право реализовывать свой String.hashCode и вроде как формально он не нарушает спецификацию языка, но как следствие — все либы, которые собраны с другим String.hashCode будут сломаны при использовании switch(String).

                          Выглядит скорее как дыра в спеке

                          • 0
                            Javadoc к публичным Java SE классам — это часть Java SE спецификации. Не языка Java, а API.
                            • +5
                              Если уж совсем точно, то полная спецификация платформы
                              • состоит из кучи документов
                              • имеет конкретную версию


                              То есть, нет спецификации «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 +…
                          • +2
                            Всё верно. Алгоритм String.hashCode прописан в спецификации Java SE API, и другие реализации Java SE не вправе его менять. А то, во что switch превращается — отдаётся на откуп компилятору. И javac генерирует код, который на любой Java SE-совместимой реализации будет корректен.
                            • 0
                              т.е чтобы быть java compatible нужно быть не только следовать java lang spec, но и java se api — и javadoc это вполне себе контракт.

                              спасибо
                              • 0
                                нужно следовать огромному количеству спецификаций. Более половине из тех, что есть тут на диаграмме.
                    • 0

                      Эта функция используется много где ещё в OpenJDK, например все перегрузки java.util.Arrays#hashCode и java.util.AbstractList.

                      • 0
                        поэтому в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.

                        Не в седьмой, а в восьмой.


                        Ну и константное число запросов к мапке на один запрос к сервису обычно не приводит к эффективной DoS-атаке. А если оно у вас не константное, то частенько вы ССЗБ.

                        • 0

                          Про номер джавы меня уже поправили :).


                          А вот про константное число запросов — если в бакете оооочень длинный лист, то для эффектиной DoS атаки достаточно просто сделать достаточное количество запросов. По крайней мере я так понял.

                  • +1

                    Всмысле? У String же не дефолтный hashCode.

                  • –5
                    Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц

                    Это примерно как в 2000 году написать, что все бенчмарки прогонялись на Celeron :).

                    • +2
                      А почему в JDK 8 изменили метод генерации identityHashCode, хотя все те же алгоритмы были и раньше?
                      • +5

                        … задаёт вопрос человек, написавший три года назад статью ;)


                        Для остальных: http://mail.openjdk.java.net/pipermail/hotspot-runtime-dev/2013-January/005212.html

                        • +10
                          Сорри, позволил себе лёгкий троллинг :) Просто зачем автор полез в такие глубины, не разобравшись в более простых вещах? Это ставит под сомнение и всю статью.
                          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. Только и всего.
                        • +2
                          Режим Ванги — Шипилёв прочитал вашу статью и подумал — «А чеб и не поменять, раз быстрее?» :)
                          UPD: Прочитал письмо, вроде похоже на правду.
                      • +1
                        На хабре была статья (как раз недавно ее читал) с названием «Откуда растут ноги у hashCode» . Автору бы не помешало разместить ее в ссылках. Собственно интересовал вопрос адресации памяти выше 4 ГБ, ведь int hashCode().
                      • +1

                        Статья выглядит очень подозрительно с точки зрения осведомленности автора:


                        Диаграмма состояний и доказательство невозможности выглядит странно, хотя в том же комментарии в oopMark.hpp видно, что в заголовке просто не хватает места на хэшкод и указатель на поток + эпоху.


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

                        Это может и правда, но у автора в бенчмарке ошибка копипасты и в обоих случаях он синхронизируется на withoutIdHash


                        В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока

                        И в переводе, и в оригинале это звучит так, будто в 8 и 9 число уже неслучайное.
                        Оно все еще случайно, просто seed теперь thread-local (и не один), а сам генератор работает по-другому.


                        Ну и флаг для смены генератора конечно же есть.

                        • 0
                          Если я правильно понял, то все эти танцы с бубнами преследует одну цель: вычислять hashCode лениво, при первом вызове.

                          Неужели это оправдано? Не проще ли было при создании объекта сразу проинициализировать его адресом или каким-то псевдослучайным числом?

                          Это выглядит как очень дешевое действие, которое отработает за пару тактов и ни на что особо не повлияет.
                          • +1
                            Нет, вычислять hashCode лениво вообще не проблема. Вся история о том, где это значение хранить. И в этом смысле инициализация hashCode при создании объекта ничем не поможет.
                            • 0
                              даже в каком-то смысле инициализация hashCode может навредить.
                          • 0
                            Где-то на ютуб канале jug Шипилев объяснял, что у них там так исторически сложилось: если позвали хешкод, то отключем навсегда привязанную блокировку этому объекту. Дело в том, что на размер объекта много чего завязано — и решили, что проще сэкономить 1 байт, чем иметь и то и другое.
                            • 0
                              Тоже помню этот доклад. Называется «О чем молчат HeapDump'ы», если кто захочет посмотреть.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое