Нужна ли новая стратегия JDK 8 для устранения коллизий HashMap (дерево вместо списка) только для тех, кто не может написать хороший хэш-код ()?

Question

В Java 8 HashMap заменяет связанный список двоичным деревом, когда число элементов в корзине достигает определенного порога

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

Answer 1

Если вы добавите достаточное количество записей в HashMap, по статистике вы получите коллизии. Обратите внимание, что столкновение сегмента - , а не - то же самое, что коллизия hashCode; в то время как коллизия hashCode всегда приводит к коллизии сегментов, любые 2 хэш-кода имеют ¹ / _{количество сегментов} вероятность попадания в один и тот же сегмент.

Если по случайности (многие разные ключи оказываются в одном и том же сегменте) или при плохом кодировании (плохо выбранный алгоритм генерирует одинаковый hashCode для разных ключей), количество ключей в сегменте становится большим, временная сложность поиска был O (n), но теперь O (log n).

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

Answer 2

В каких ситуациях невозможно написать хороший метод hashcode ()?

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

В одном случае вычисление хеш-кода на основе полного значения обходится слишком дорого, поэтому вы реализуете "дешевую и веселую" версию. Но тогда у этой версии есть некоторые крайние случаи, когда вы получаете столкновения.

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

Answer 3

http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l143

Дополнительная сложность древовидных элементов полезна для обеспечения операций O (log n) в худшем случае, когда ключи либо имеют различные хеши, либо подлежат упорядочению. Таким образом, производительность снижается из-заслучайные или злонамеренные использования, в которых методы hashCode () возвращают значения, которые плохо распределены, а также те, в которых многие ключи совместно используют hashCode, если они также являются сопоставимыми.

Это улучшение предотвращает отказслужебных атак, когда противник преднамеренно выбирает значения, которые попадут в одно и то же ведро.Невозможно написать hashCode, устойчивый к этому, который также стабилен между экземплярами JVM.

Answer 4

Ваш хэш-код может быть интерпретирован не так, как вы думаете, в HashMap. Например, когда вы создаете HashMap как:

Map<String, String> map = new HashMap<>();

Есть как минимум 3 вещи, о которых вы должны знать:

• Только последние 4 бита принимаются во внимание, чтобы решить, к каким элементам сегмента будут отправляться.

• A HashMap будет повторное хеширование ваш хэш-код через:

  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

• hashCode - это int, и он ограничен, поэтому коллизии хэшей происходят очень часто. IIRC для Integer.MAX_VALUE коллизий хешей начнется с нескольких десятков тысяч (44_000? Или что-то подобное, не помню).