Java TreeMap vs HashMap - javascopes.com

1. введение

В этой статье мы сравним две реализации Map : TreeMap и HashMap .

Обе реализации являются неотъемлемой частью платформы Java Collections и хранят данные в виде пар ключ-значение .

2. Различия

2.1. Реализация

Сначала мы поговорим о HashMap , который является реализацией на основе хэш-таблицы. Он расширяет класс AbstractMap и реализует интерфейс Map . A HashMap работает по принципу хеширования .

Эта реализация Map обычно действует как привязанная хэш-таблица , но когда ведра становятся слишком большими, они преобразуются в узлы TreeNodes , каждый из которых структурирован аналогично узлам в java.util.Карта деревьев.

Вы можете найти больше о HashMap внутренностях в статье, посвященной этому .

С другой стороны, TreeMap расширяет AbstractMap класс и реализует NavigableMap интерфейс. A TreeMap хранит элементы карты в Красно-черном дереве, которое является Самобалансирующимся Бинарным деревом поиска .

И вы также можете найти больше информации о Treemap internals в статье, посвященной этому здесь .

2.2. Порядок

HashMap не дает никаких гарантий относительно того, как элементы расположены на карте .

Это означает, что мы не можем предполагать какой-либо порядок при переборе ключей и значений хэш-карты :

@Test
public void whenInsertObjectsHashMap_thenRandomOrder() {
    Map hashmap = new HashMap<>();
    hashmap.put(3, "TreeMap");
    hashmap.put(2, "vs");
    hashmap.put(1, "HashMap");
    
    assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}

Однако элементы в TreeMap сортируются в соответствии с их естественным порядком .

Если TreeMap объекты не могут быть отсортированы в соответствии с естественным порядком, то мы можем использовать Компаратор или Сопоставимый для определения порядка, в котором элементы расположены в пределах Карты:

@Test
public void whenInsertObjectsTreeMap_thenNaturalOrder() {
    Map treemap = new TreeMap<>();
    treemap.put(3, "TreeMap");
    treemap.put(2, "vs");
    treemap.put(1, "HashMap");
    
    assertThat(treemap.keySet(), contains(1, 2, 3));
}

2.3. Нулевые значения

HashMap позволяет хранить не более одного null | ключа и множество null значений.

Давайте рассмотрим пример:

@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
    Map hashmap = new HashMap<>();
    hashmap.put(null, null);
    
    assertNull(hashmap.get(null));
}

Однако TreeMap не допускает null | ключ , но может содержать много null значений.

Ключ null не разрешен, поскольку метод compareTo() или compare() вызывает исключение NullPointerException:

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
    Map treemap = new TreeMap<>();
    treemap.put(null, "NullPointerException");
}

Если мы используем Древовидная карта с определяемым пользователем Компаратор , то это зависит от реализации сравнения () метод как нулевой значения обрабатываются.

3. Анализ производительности

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

В этом разделе мы предоставим всесторонний анализ производительности для HashMap и TreeMap.

3.1. Хэш-карта

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

HashMap обеспечивает ожидаемую производительность в режиме постоянного времени O(1) для большинства операций, таких как add () , remove() и contains(). Следовательно, это значительно быстрее, чем Древовидная карта .

Среднее время поиска элемента в хэш-таблице при разумном предположении составляет O(1). Но неправильная реализация хэш-функции может привести к плохому распределению значений в сегментах, что приведет к:

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

До Java 8 Отдельная цепочка была единственным предпочтительным способом обработки коллизий. Обычно это реализуется с использованием связанных списков, т. Е. , если есть какое-либо столкновение или два разных элемента имеют одинаковое хэш-значение, то сохраните оба элемента в одном связанном списке.

Таким образом, поиск элемента в HashMap, в худшем случае может занять столько же времени, сколько поиск элемента в связанном списке т. Е. | O(n) время.

Однако с появлением JEP 180 произошли незначительные изменения в реализации способа расположения элементов в HashMap.

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

Следовательно, в случае высоких хэш-коллизий худшая производительность улучшится с O(n) к O(log n).

Код, выполняющий это преобразование, был проиллюстрирован ниже:

if(binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

Значение для TREEIFY_THRESHOLD равно восьми, что фактически обозначает пороговое значение для использования дерева, а не связанного списка для ведра.

Очевидно, что:

HashMap требует гораздо больше памяти, чем требуется для хранения его данных
HashMap не должен быть заполнен более чем на 70-75%. Если он приближается, его размер изменяется, а записи перефразируются
Перефразирование требует n операций, которые являются дорогостоящими, когда наша вставка с постоянным временем становится упорядоченной O(n)
Это алгоритм хеширования, который определяет порядок вставки объектов в HashMap

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

Однако мы должны выбрать HashMap , если:

мы примерно знаем, сколько предметов нужно сохранить в нашей коллекции
мы не хотим извлекать предметы в естественном порядке

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

3.2. Карта деревьев

TreeMap хранит свои данные в иерархическом дереве с возможностью сортировки элементов с помощью пользовательского Компаратора.

Краткое описание его работы:

TreeMap обеспечивает производительность O(log(n)) для большинства операций, таких как add () , remove() и содержит()
A Treemap может экономить память (по сравнению с HashMap) , поскольку он использует только объем памяти, необходимый для хранения своих элементов, в отличие от a HashMap , который использует непрерывную область памяти
Дерево должно поддерживать свой баланс, чтобы сохранить свою предполагаемую производительность, это требует значительных усилий, следовательно, усложняет реализацию

Мы должны пойти на древовидную карту всякий раз, когда:

необходимо учитывать ограничения памяти
мы не знаем, сколько элементов должно храниться в памяти
мы хотим извлекать объекты в естественном порядке
если элементы будут последовательно добавляться и удаляться
мы готовы принять O(log n) время поиска

4. Сходство

4.1. Уникальные элементы

Как TreeMap , так и HashMap не поддерживают дубликаты ключей. При добавлении он переопределяет предыдущий элемент (без ошибки или исключения):

@Test
public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {
    Map treeMap = new HashMap<>();
    treeMap.put(1, "Baeldung");
    treeMap.put(1, "Baeldung");

    assertTrue(treeMap.size() == 1);

    Map treeMap2 = new TreeMap<>();
    treeMap2.put(1, "Baeldung");
    treeMap2.put(1, "Baeldung");

    assertTrue(treeMap2.size() == 1);
}

4.2. Параллельный доступ

Обе реализации Map не синхронизированы , и нам нужно управлять параллельным доступом самостоятельно.

Оба должны быть синхронизированы извне всякий раз, когда несколько потоков обращаются к ним одновременно и по крайней мере один из потоков изменяет их.

Мы должны явно использовать Коллекции.synchronizedMap(имя карты) для получения синхронизированного представления предоставленной карты.

4.3. Отказоустойчивые итераторы

Итератор создает исключение ConcurrentModificationException , если Карта будет изменена каким-либо образом и в любое время после создания итератора.

Кроме того, мы можем использовать метод remove итератора для изменения Map во время итерации.

Давайте рассмотрим пример:

@Test
public void whenModifyMapDuringIteration_thenThrowExecption() {
    Map hashmap = new HashMap<>();
    hashmap.put(1, "One");
    hashmap.put(2, "Two");
    
    Executable executable = () -> hashmap
      .forEach((key,value) -> hashmap.remove(1));
 
    assertThrows(ConcurrentModificationException.class, executable);
}

5. Какую реализацию использовать?

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

Подведение:

Мы должны использовать TreeMap , если мы хотим, чтобы наши записи были отсортированы
Мы должны использовать HashMap , если мы отдаем приоритет производительности над потреблением памяти
Поскольку Древовидная карта имеет более значительную локальность, мы могли бы рассмотреть ее, если хотим получить доступ к объектам, которые относительно близки друг к другу в соответствии с их естественным порядком
HashMap можно настроить с помощью initialCapacity и loadFactor , что невозможно для TreeMap
Мы можем использовать LinkedHashMap , если хотим сохранить порядок вставки, используя при этом постоянный доступ к времени

6. Заключение

В этой статье мы показали различия и сходства между TreeMap и HashMap .

Как всегда, примеры кода для этой статьи доступны на GitHub .