Java TreeMap срещу HashMap

1. Въведение

В тази статия ще сравним две реализации на Map : TreeMap и HashMap .

И двете изпълнения формират неразделна част от Java Collections Framework и съхраняват данни като двойки ключ-стойност .

2. Различия

2.1. Изпълнение

Първо ще говорим за HashMap, която е базирана на хеш-таблица реализация. Той разширява класа AbstractMap и реализира интерфейса Map . А HashMap работи на принципа на хеширане .

Тази реализация на Карта обикновено действа като хеш таблица , но когато кофите станат твърде големи, те се трансформират в възли на TreeNodes , всяка структурирана подобно на тези в java.util.TreeMap.

Можете да намерите повече за вътрешните елементи на HashMap в статията, фокусирана върху него.

От друга страна, TreeMap разширява класа AbstractMap и прилага интерфейс NavigableMap . А дървовидна карта магазини Карта на елементи в червено-черно дърво, което е самобалансиращо двоично дърво за търсене .

Освен това можете да намерите повече за вътрешните елементи на TreeMap в статията, фокусирана върху него тук.

2.2. Поръчка

HashMap не предоставя никаква гаранция за начина, по който елементите са подредени в картата .

Това означава, че не можем да приемем каквато и да е поръчка, докато итерираме върху ключове и стойности на 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 обектите не могат да бъдат сортирани според естествения ред, тогава можем да използваме Comparator или Comparable, за да определим реда, в който елементите са подредени в картата:

@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 позволява да се съхраняват най-много един нулев ключ и много нулеви стойности.

Да видим пример:

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

Въпреки това, дървовидна карта не позволява нула ключ , но може да съдържа много нулеви стойности.

А нула ключ не е позволено, защото compareTo () или за сравнение () метод хвърля NullPointerException:

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

Ако използваме TreeMap с дефиниран от потребителя Comparator , тогава от изпълнението на метода compare () зависи как се обработват нулевите стойности.

3. Анализ на ефективността

Ефективността е най-критичният показател, който ни помага да разберем пригодността на структурата от данни при даден случай на употреба.

В този раздел ще предоставим изчерпателен анализ на ефективността за HashMap и TreeMap.

3.1. HashMap

HashMap, като базирана на хеш -таблица реализация, използва вътрешно базирана на масив структура от данни, за да организира своите елементи според хеш функцията .

HashMap осигурява очаквана постоянна производителност O (1) за повечето операции като add () , remove () и contains (). Следователно, това е значително по-бързо от TreeMap .

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

  • Memory Overhead - много кофи остават неизползвани
  • Влошаване на производителността - колкото по-голям е броят на сблъсъците, толкова по-ниска е производителността

Преди Java 8, Separate Chaining беше единственият предпочитан начин за справяне с колизии. Обикновено се прилага с помощта на свързани списъци, т.е. ако има някакво сблъсък или два различни елемента имат една и съща хеш стойност, съхранявайте и двата елемента в един и същ свързан списък.

Следователно, търсенето на елемент в 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

The performance of a HashMap can be tuned by setting the custom initial capacity and the load factor, at the time of HashMap object creation itself.

However, we should choose a HashMap if:

  • we know approximately how many items to maintain in our collection
  • we don't want to extract items in a natural order

Under the above circumstances, HashMap is our best choice because it offers constant time insertion, search, and deletion.

3.2. TreeMap

A TreeMap stores its data in a hierarchical tree with the ability to sort the elements with the help of a custom Comparator.

A summary of its performance:

  • TreeMap provides a performance of O(log(n)) for most operations like add(), remove() and contains()
  • A Treemap can save memory (in comparison to HashMap) because it only uses the amount of memory needed to hold its items, unlike a HashMap which uses contiguous region of memory
  • A tree should maintain its balance in order to keep its intended performance, this requires a considerable amount of effort, hence complicates the implementation

We should go for a TreeMap whenever:

  • memory limitations have to be taken into consideration
  • we don't know how many items have to be stored in memory
  • we want to extract objects in a natural order
  • if items will be consistently added and removed
  • we're willing to accept O(log n) search time

4. Similarities

4.1. Unique Elements

Both TreeMap and HashMap don't support duplicate keys. If added, it overrides the previous element (without an error or an exception):

@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. Concurrent Access

Both Map implementations aren't synchronized and we need to manage concurrent access on our own.

Both must be synchronized externally whenever multiple threads access them concurrently and at least one of the threads modifies them.

We have to explicitly use Collections.synchronizedMap(mapName) to obtain a synchronized view of a provided map.

4.3. Fail-Fast Iterators

The Iterator throws a ConcurrentModificationException if the Map gets modified in any way and at any time once the iterator has been created.

Additionally, we can use the iterator’s remove method to alter the Map during iteration.

Let's see an example:

@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. Which Implementation to Use?

In general, both implementations have their respective pros and cons, however, it's about understanding the underlying expectation and requirement which must govern our choice regarding the same.

Summarizing:

  • We should use a TreeMap if we want to keep our entries sorted
  • We should use a HashMap if we prioritize performance over memory consumption
  • Тъй като TreeMap има по-значимо местоположение, бихме могли да го обмислим, ако искаме да получим достъп до обекти, които са относително близо един до друг според естествения им ред.
  • HashMap може да бъде настроен с помощта на InitiCapacity и loadFactor , което не е възможно за TreeMap
  • Можем да използваме LinkedHashMap, ако искаме да запазим реда за вмъкване, като същевременно се възползваме от постоянен достъп по време

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

В тази статия показахме разликите и приликите между TreeMap и HashMap .

Както винаги, примерите за кодове за тази статия са достъпни в GitHub.