Is it possible to have a negative hashcode and capacity expansion with a bad hashcode? And also how does the hashcode correspond to the address?

Question

Hashing

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

Answer 1

Во-первых, важно определиться с тем, что генерируемый по умолчанию хэш не соответствует требованиям к хорошему хэшу. Поэтому метод 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.
Заглядываем в исходный код 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 генерирует хэшкоды по умолчанию на основе адреса объекта в памяти.

Answer 2

Пока шли бурные дебаты, залез в буржунет:
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.Человек грамотно вроде разжевал, но оставил на конец загадку с подсказкой насчет использования адресов в памяти
помогите решить загадку?
( человек как и следовало ожидать оказался нашим соотечественником, то есть это прям у нас черта такая, не говорить ничего, оставлять загадки и подсказки или отсылать в исходный код джавы)))