Уважаемые java инженеры,

Объясните, если не сложно,

Когда HashMap в java начинает хранить бакеты в виде дерева, то оно вроде строит дерево для бакета с ключом hash
(java.util.HashMap.TreeNode#find)

Но ведь в бакете по идее hash должен быть одинаковый.

Не врубаюсь, как это должно работать ((

Здравствуйте, PitoWilson, Вы писали:

PW>Но ведь в бакете по идее hash должен быть одинаковый.

Да, правильно.

PW>Не врубаюсь, как это должно работать ((

А потом в бакете уже идёт поиск не по hash.

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

Здравствуйте, sambl74, Вы писали:

PW>>Но ведь в бакете по идее hash должен быть одинаковый.
S>Да, правильно.

PW>>Не врубаюсь, как это должно работать ((

S>А потом в бакете уже идёт поиск не по hash.
S>Поэтому важно для объекта написать хорошую hash-функцию, чтобы в HashMap в один бакет не попадало много разных объектов.

И тогда она не будет хранить объекты в дереве, бедолага))) А как в доброй старой 7-й версии? в связанном списке.

Здравствуйте, sambl74, Вы писали:


S>А потом в бакете уже идёт поиск не по hash.

Когда бакет — дерево, что является ключом в этом дереве?

Здравствуйте, PitoWilson, Вы писали:

S>>А потом в бакете уже идёт поиск не по hash.

PW>Когда бакет — дерево, что является ключом в этом дереве?

Исходный ключ.

Здравствуйте, vsb, Вы писали:

vsb>Исходный ключ.

Правильно понимаю, что такая "древоизация" произойдет, только если исходный ключ реализует Comparable?

Здравствуйте, PitoWilson, Вы писали:

vsb>>Исходный ключ.

PW>Правильно понимаю, что такая "древоизация" произойдет, только если исходный ключ реализует Comparable?

По сути да, сама процедура "древоизации" вроде произойдёт в любом случае, но без Comparable сформированное дерево выродится в связный список, по крайней мере по исходникам jdk8, насколько я вижу.

Здравствуйте, PitoWilson, Вы писали:

PW>Но ведь в бакете по идее hash должен быть одинаковый.
PW>Не врубаюсь, как это должно работать ((
Нужно, чтобы ключ реализовал Comparable. Это появилось в JDK6, до этого объекты тупо хранились в массиве.

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

Мы как-то потратили неделю на поиск ошибки из-за того, что один наш класс немного неправильно реализовал Comparable.

Здравствуйте, Географ, Вы писали:

Г>И тогда она не будет хранить объекты в дереве, бедолага))) А как в доброй старой 7-й версии? в связанном списке.

Ага, примерно так, с давних пор у меня такие знания по Java сохранились

Здравствуйте, sambl74, Вы писали:

PW>>Но ведь в бакете по идее hash должен быть одинаковый.
S>Да, правильно.
Ээээ?

Все в одном бакете:

HashMap<Integer, Object> map = new HashMap<>();
map.put(1, new Object());
map.put(17, new Object());

Здравствуйте, PitoWilson, Вы писали:

PW>Не врубаюсь, как это должно работать ((

Вкратце, HashMap хранит массив бакетов фиксированного размера. В методах get/put по хэш-коду ключа специальным образом вычисляется индекс в этом массиве. Бакет, элемент массива — либо пуст (null, т.е. по данному ключу ничего нет), либо единичная пара, либо список из пар "ключ"-"значение" (а также вычисленный хэш-код для ключа). Последний вариант означает, что у нас коллизии, и скорость работы HashMap падает с обычного O(1) ниже, вплоть до линейной O(n) в худшем варианте. Таким образом, в одном бакете при коллизиях могут лежать объекты с разными хэшами (если по ним получается одинаковый индекс). Ну и еще ключ null обрабатывается отдельно (для него хэшем всегда будет 0).

Если есть еще вопросы, можно посмотреть исходники в OpenJDK 8.

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