Java 8 HashTable против обработки коллизий HashMap

Question

Мне нужны некоторые пояснения относительно различий между hashtable и hashmap в Java 8.

Насколько мне известно, HashTable функционирует аналогично HashMap, но является поточно-ориентированным и не допускает нулевые ключи или значения. Мне известно, что Java 8 обновляет класс HashMap, так что при возникновении коллизии вместо создания связанного списка элементов с одинаковым хэш-кодом в корзине создается дерево.

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

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

Answer 1

Это также относится и к хеш-таблице?

Нет.

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

Нет.Класс HashMap имеет константу с именем TREEIFY_THRESHOLD (значение 8).

Javadoc говорит "Порог числа бинов для использования дерева, а не списка для бина.Ячейки преобразуются в деревья при добавлении элемента в ячейку с как минимум таким количеством узлов ".

Кроме того, как Java гарантирует, что хеш-таблица является поточно-ориентированной?

Javadoc Hashtable явно говорит: "В отличие от новых реализаций коллекции, Hashtable синхронизирован " .

Создает ли очередь, когда два потока пытаются одновременно получить доступ к части данных?

Нет.

Answer 2

Этот ответ будет очень специфичным для текущей реализации, найденной в JDK, так что имейте это в виду.

1. Мне известно, что Java 8 обновляет класс HashMap, поэтому при возникновении коллизии вместо создания связанного списка элементов с одинаковым хэш-кодом в корзине создается дерево.

   Это также относится и к хеш-таблице?

Нет. Hashtable всегда будет таблицей связанных списков. Разработчики Java не обновляли Hashtable для этого варианта использования. Это также должно прояснить, что вы, вероятно, не должны использовать Hashtable в любом случае.

2. И является ли дерево методом хранения по умолчанию даже до столкновения?

Опять же, это в Java 8, на сегодняшний день, но нет, это не поведение по умолчанию. Как только запись сегмента достигает 8 связанных элементов , HashMap превращает этот связанный список в двоичное дерево.

3. Кроме того, как java гарантирует, что хеш-таблица является поточно-ориентированной? Создает ли он очередь, когда два потока пытаются одновременно получить доступ к части данных?

Путем синхронизации каждого метода, что означает, что каждый поток будет ставиться в очередь в методе, в то время как другой поток в настоящее время обращается к любому методу Hashtable. Это вызывает немало проблем, если вы хотите делать такие вещи, как атомарные путы или атомные вычисления.

Если вам нужна многопоточная карта HashMap, всегда используйте ConcurrentHashMap, а не Hashtable.

Answer 3

Из документов Hashtable Java Docs :

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

Итак, ответ на первый вопрос - «Нет».Он не создает никакого дерева.

Что касается механизма безопасности потоков, Hashtable использует простую синхронизацию для каждого метода чтения \ записи.Если вы беспокоитесь о производительности и безопасности потоков, вам лучше взглянуть на ConcurrentHashMap .