Почему хеш-карты в Java 8 используют бинарное дерево вместо связанного списка?

Question

Недавно я узнал, что в хэш-картах Java 8 используется бинарное дерево вместо связанного списка, а хеш-код используется как фактор ветвления. Я понимаю, что в случае большого столкновения поиск восстанавливается до O (log n) из O (n) с помощью двоичных деревьев. Мой вопрос заключается в том, что хорошо делает это, так как амортизированная временная сложность по-прежнему равна O (1), а может быть, если вы принудительно сохраняете все записи в одном и том же ведре, предоставляя одинаковый хэш-код для всех мы видим значительную разницу во времени, но никто в здравом уме не сделает этого.

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

Answer 1

Это главным образом связанное с безопасностью изменение. Хотя в обычной ситуации редко бывает много столкновений, если хеш-ключи поступают из ненадежного источника (например, имена заголовков HTTP, полученные от клиента), тогда возможно и не очень сложно специально обработать ввод, поэтому полученные ключи будут иметь тот же хэш-код. Теперь, если вы выполняете много запросов, вы можете столкнуться с отказом в обслуживании. Похоже, что в дикой природе довольно много кода, который уязвим для такого рода атак, поэтому было решено исправить это на стороне Java.

Для получения дополнительной информации см. JEP-180.

Answer 2

Ваш вопрос содержит неправильные помещения.

1. Столкновение ведро не обязательно хэш столкновения. Вам не нужно иметь один и тот же хэш-код для двух объектов, которые должны быть в одном и том же ведре. Ведро - это элемент массива, и хэш-код должен быть сопоставлен определенному индексу. Поскольку размер массива должен быть разумным в отношении размера Map, вы не можете поднять размер массива произвольно, чтобы избежать столкновений с ведром. Существует даже теоретическое ограничение на то, что размер массива может составлять максимум 2³¹, в то время как существует 2 ² возможных хэш-кодов.
2. Наличие столкновений с хешем не является признаком плохого программирования. Для всех объектов, имеющих пространство значений более 2 м², возможность отдельных объектов с одинаковым хэш-кодом неизбежна. String s - очевидный пример, но даже Point с двумя значениями int или простым ключом Long имеют неизбежные хэш-коллизии. Поэтому они могут быть более распространенными, чем вы думаете, и это сильно зависит от варианта использования.
3. Реализация переключается на двоичное дерево только тогда, когда количество коллизий в ковше превышает определенный порог, поэтому более высокие затраты на память применяются только тогда, когда они окупится. похоже, существует общее недоразумение относительно того, как они работают. Поскольку столкновение ковша не обязательно связано с хеш-коллизиями, двоичный поиск сначала будет искать хэш-коды. Только когда хэш-коды идентичны, и ключ надлежащим образом реализует Comparable, его естественный порядок будет использоваться. Примеры, которые вы, возможно, нашли в Интернете, намеренно используют один и тот же хэш-код для объектов, чтобы продемонстрировать использование реализации Comparable, которая иначе не отображалась бы. То, что они вызывают, является лишь последним средством реализации.
4. Как Tagir pointed out, эта проблема может повлиять на безопасность программного обеспечения, так как медленный резерв может открыть возможность DoS-атак. В предыдущих версиях JRE было несколько попыток решить эту проблему, у которой было больше недостатков, чем потребление памяти двоичным деревом. Например, была предпринята попытка рандомизировать отображение хеш-кодов на записи массива в Java 7, что вызвало служебные данные инициализации, как описано в this bug report. Это не относится к этой новой реализации.