What is hashmap and treemap in java

What is the difference between a HashMap and a TreeMap? [duplicate]

Stackoverflow isn’t just for the question asker but also for other people looking for answers. Thus it is perfectly fine for me if I find an answer here that is also contained in some book I don’t have.

8 Answers 8

TreeMap is an example of a SortedMap , which means that the order of the keys can be sorted, and when iterating over the keys, you can expect that they will be in order.

HashMap on the other hand, makes no such guarantee. Therefore, when iterating over the keys of a HashMap , you can’t be sure what order they will be in.

HashMap will be more efficient in general, so use it whenever you don’t care about the order of the keys.

TreeMap only works with Comparable objects, HashMap only works with objects with a suitable hashCode() implementation.

HashMap allows null key and null values (Only one null key is allowed). If TreeMap uses natural ordering or its comparator, does not allow null keys, an exception will be thrown.

HashMap is implemented by Hash Table while TreeMap is implemented by Red-Black tree . The main difference between HashMap and TreeMap actually reflect the main difference between a Hash and a Binary Tree , that is, when iterating, TreeMap guarantee can the key order which is determined by either element’s compareTo() method or a comparator set in the TreeMap’s constructor.

• HashMap: Lookup-array structure, based on hashCode(), equals() implementations, O(1) runtime complexity for inserting and searching, unsorted
• TreeMap: Tree structure, based on compareTo() implementation, O(log(N)) runtime complexity for inserting and searching, sorted

The complexity o a HashMap is O(1+a). Dependent on the hashCode function «a» can reach «n» in the worst case.

Use HashMap most of the times but use TreeMap when you need the key to be sorted (when you need to iterate the keys).

I’ll talk about the HashMap and TreeMap implementation in Java:

• HashMap — implement basic map interface
  1. implemented by an array of buckets, each bucket is a LinkedList of entries
  2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
  3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(. ));
  4. Iteration order of the map is unpredictable.
• TreeMap — implement navigable map interface
  1. implemented by a red-black tree
  2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
  3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(. ));
  4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap , which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Java to know more about their implementations.

Источник

Java TreeMap против HashMap

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

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

2. Различия

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

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

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

Вы можете найти более подробную информацию о HashMap’s внутренности в ссылке:/java-hashmap[статья посвящена этому].

С другой стороны, TreeMap расширяет класс AbstractMap и реализует интерфейс NavigableMap . TreeMap хранит элементы карты в дереве Red-Black , которое представляет собой Self-Balancing Binary Search Tree .

И вы также можете найти больше информации о внутренностях TreeMap’s по ссылке:/java-treemap[статья сосредоточена на этом здесь].

2.2. Порядок

Это означает, что мы не можем принимать любой порядок при переборе keys и values HashMap :

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

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

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

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

2.3. Null Значения

HashMap позволяет хранить не более одного null key и многих null значений.

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

@Test public void whenInsertNullInHashMap__thenInsertsNull() < Maphashmap = new HashMap<>(); hashmap.put(null, null); assertNull(hashmap.get(null)); >

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

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

@Test(expected = NullPointerException.class) public void whenInsertNullInTreeMap__thenException() < Maptreemap = new TreeMap<>(); treemap.put(null, "NullPointerException"); >

• Если мы используем TreeMap с пользовательским Comparator , то от того, как обрабатываются null значения, зависит реализация метода _ () _ метода. **

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

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

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

3.1. HashMap

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

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

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

• Затраты памяти — многие ведра остаются неиспользованными
• Снижение производительности — чем больше количество столкновений, тем

• До Java 8 Separate Chaining был единственным предпочтительным способом обработки коллизий. ** Обычно он реализован с использованием связанных списков, i.e. , если есть какая-либо коллизия или два разных элемента имеют одинаковое значение хеш-функции, тогда сохраняются оба элемента в тот же связанный список.

Следовательно, поиск элемента в HashMap, в худшем случае мог бы занять столько же времени, сколько и поиск элемента в связанном списке i.e. O (n) .

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

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

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

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

if(binCount >= TREEIFY__THRESHOLD - 1)

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

• HashMap требует гораздо больше памяти, чем необходимо для хранения своих данных
• HashMap не должен быть заполнен более чем на 70% — 75%. Если это близко,

он изменяется и записи перефразируются ** Перефразирование требует n операций, что является дорогостоящим, когда наша постоянная

время вставки становится порядка O (n) ** Это алгоритм хеширования, который определяет порядок вставки

• Производительность HashMap можно настроить, установив пользовательские initialacity и load factor ** во время самого создания объекта HashMap .

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

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

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

3.2. TreeMap

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

Краткое описание его производительности:

как add () , remove () и contains () ** Treemap может сэкономить память (по сравнению с HashMap) , потому что это

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

производительность, это требует значительных усилий, следовательно, усложняет реализацию

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

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

4. сходства

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

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

@Test public void givenHashMapAndTreeMap__whenputDuplicates__thenOnlyUnique() < MaptreeMap = 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 не являются synchronized ** , и нам нужно управлять параллельным доступом самостоятельно.

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

Мы должны явно использовать Collections.synchronizedMap (mapName) , чтобы получить синхронизированное представление предоставленной карты.

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

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

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

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

@Test public void whenModifyMapDuringIteration__thenThrowExecption() < Maphashmap = 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 , если мы отдаем приоритет производительности над памятью

потребление ** Поскольку TreeMap имеет более существенное местоположение, мы могли бы рассмотреть

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

что невозможно для TreeMap ** Мы можем использовать LinkedHashMap , если мы хотим сохранить порядок вставки

пользуясь постоянным доступом

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

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

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

Источник