@ericcartman

Возможет ли отрицательный хешкод и расширение капасити при плохом хешкоде? А также как соотносится хешкод с адресом?

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

1 Вопрос: там такой хитрый алгоритм, что сам учитывает путешествия объекта по памяти, или просто сразу при создании пишется хеш код?

2. Если я переопределю хешкод и он иногда ( или всегда, например -1) будет выдавать отрицательные целые, что будет? Очевидно это число как-то преобразуется под капотом? потому что должен выдаваться номер бакета?

3. При заполнении хешсета ( хешмапы) происходит увеличение капасити при достижении 0.75 заполнения. Вопрос: учитываются заполнения корзин ( бакетов ) или вообще всего? Ну то есть я определю хешкод == 1, у меня в этом бакете будет расти список ( дерево). Будет в этом случае расширяться капасити?

Спасибо
  • Вопрос задан
  • 332 просмотра
Решения вопроса 2
sergey-gornostaev
@sergey-gornostaev Куратор тега Java
Седой и строгий
Во-первых, важно определиться с тем, что генерируемый по умолчанию хэш не соответствует требованиям к хорошему хэшу. Поэтому метод hashCode всего надо переопределять в своих классах. Во-вторых, важно понимать, что способ генерации хэшкода по умолчанию не оговорен в спецификаций Java, а потому может отличать в разных реализациях виртуальной машины или даже в разных версиях одной и той же реализации. Я дальше буду писать про HotSpot.

Несмотря на то, что в документации написано, что генерируемый по умолчанию хэш - "this is typically implemented by converting the internal address of the object into an integer", этот internal address не имеет никакого отношения к положению объекта в памяти. Попробуем разобраться откуда он берётся. Для этого заглянем в исходный код Object. Как видно, hashCode() - это нативный метод, а значит придётся покопаться в сишном коде. Находим его определение:
JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  JVMWrapper("JVM_IHashCode");
  // as implemented in the classic virtual machine; return 0 if object is NULL
  return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END

Ага, хэшкод генерирует функция ObjectSynchronizer::FastHashCode(). Посмотрим, что в ней. Интересная часть:
mark = monitor->header();
...
hash = mark->hash();
if (hash == 0) {
  hash = get_next_hash(Self, obj);
...
}
...
return hash;

Функция пытается получить хэш из заголовка объекта, а если его там нет, то генерирует вызовом get_next_hash. В этой функции определяются несколько методов генерации хэша. В HotSpot шестой и седьмой версии использовался первый - генерация случайного числа. Вообще ни разу не internal address! С восьмой версии используется пятый - "Marsaglia's xor-shift scheme with thread-specific state". Почитать про этот алгоритм можно здесь. Если отбросить нюансы, опять случайное число, не internal address.

Если я переопределю хешкод и он иногда ( или всегда, например -1) будет выдавать отрицательные целые, что будет? Очевидно это число как-то преобразуется под капотом? потому что должен выдаваться номер бакета?

Заглядываем в исходный код HashMap
if ((p = tab[i = (n - 1) & hash]) == null)
  tab[i] = newNode(hash, key, value, null);

Переменная n в этой точке равна количеству бакетов - положительному числу, а значит i тоже будет положительным числом.

3. Учитывается заполнение всех бакетов. В вашем случае, когда элементы возвращают один и тот же хэш, а значит скапливаются в одном бакете, будет учитываться другой параметр - TREEIFY_THRESHOLD. По умолчанию он равен 8 и после накопления в бакете стольки элементов, он будет преобразован из списка в дерево.

P.S. Виртуальная машина Zing генерирует хэшкоды по умолчанию на основе адреса объекта в памяти.
Ответ написан
zagayevskiy
@zagayevskiy Куратор тега Java
Android developer at Yandex
1) As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)
Это детали реализации конкретной JVM. Зачем тебе это знать?

2) ничего не будет, там битовая арифметика, -1 валидное значение.

3) Детали реализации конкретной хэштаблицы, открой исходники и почитай. Там не рокетсайнс.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@ericcartman Автор вопроса
Пока шли бурные дебаты, залез в буржунет:

Even though there are some answers here stating that the default implementation is "memory" based, this is plain wrong. This is not the case for a lot of years now.

Under java-8, you can do :

java -XX:+PrintFlagsFinal | grep hashCode
To get the exact algorithm that is used (5 being default).

0 == Lehmer random number generator,
1 == "somehow" based on memory address
2 == always 1
3 == increment counter
4 == memory based again ("somehow")
5 == read below
By default (5), it is using Marsaglia XOR-Shift algorithm, that has nothing to do with memory.

This is not very hard to prove, if you do:

System.out.println(new Object().hashCode());
multiple times, in a new VM all the time - you will get the same value, so Marsaglia XOR-Shift starts with a seed (always the same, unless some other code does not alter it) and works from that.

But even if you switch to some hashCode that is memory based, and Objects potentially move around (Garbage Collector calls), how do you ensure that the same hashCode is taken after GC has moved this object? Hint: indentityHashCode and Object headers.
Человек грамотно вроде разжевал, но оставил на конец загадку с подсказкой насчет использования адресов в памяти
Hint: indentityHashCode and Object headers

помогите решить загадку?
( человек как и следовало ожидать оказался нашим соотечественником, то есть это прям у нас черта такая, не говорить ничего, оставлять загадки и подсказки или отсылать в исходный код джавы)))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ЛАНИТ Москва
от 180 000 руб.
YLab Москва
от 100 000 до 160 000 руб.
Дневник.ру Санкт-Петербург
от 110 000 руб.
23 окт. 2019, в 00:16
25000 руб./за проект
22 окт. 2019, в 23:57
100000 руб./за проект
22 окт. 2019, в 23:26
4000 руб./за проект