Różnica między HashMap, LinkedHashMap i TreeMap

Wolę prezentację wizualną:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Iteration    ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║  Get/put     ║                     ║                   ║                     ║
║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)        ║
║ containsKey  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableMap    ║                     ║
║  Interfaces  ║         Map         ║       Map         ║         Map         ║
║              ║                     ║    SortedMap      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║                   ║                     ║
║     Null     ║       allowed       ║    only values    ║       allowed       ║
║ values/keys  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣
║              ║                     ║                   ║                     ║
║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked    ║
║              ║                     ║                   ║       buckets       ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

Wszystkie trzy reprezentują mapowanie z unikalnych kluczy do wartości, a zatem implementują interfejs Map .

1. HashMap jest mapą opartą na hashowaniu kluczy. Obsługuje operacje o (1) get/put. Klucze muszą mieć spójne implementacje hashCode() i equals() żeby to zadziałało.

2. LinkedHashMap jest bardzo podobny do HashMap, ale dodaje świadomość do kolejności, w której elementy są dodawane (lub dostępne) , więc kolejność iteracji jest taka sama jak kolejność wstawiania (lub kolejność dostępu, w zależności od parametrów konstrukcyjnych).

3. TreeMap jest mapowaniem opartym na drzewie. Jego operacje put/get zajmują czas o (log n). Wymaga to, aby elementy miały jakiś mechanizm porównawczy, albo z porównywalnym, albo porównawczym. Kolejność iteracji jest określona przez ten mechanizm.

Zobacz, gdzie każda klasa znajduje się w hierarchii klas na poniższym diagramie (większy ). TreeMap implementuje SortedMap i NavigableMap, podczas gdy HashMap nie.

HashTable jest przestarzały i należy użyć odpowiedniej klasy ConcurrentHashMap.

HashMap

• ma wartości pary (klucze,wartości)
• Brak wartości klucza duplikacji
• nieuporządkowane niesortowane
• pozwala na jeden klucz null i więcej niż jedną wartość null

HashTable

• tak samo jak hash map
• nie pozwala na klucze null i wartości null

LinkedHashMap

• jest to uporządkowana wersja implementacji map
• na podstawie połączonych list i danych hashujących struktury

TreeMap

• Wersja uporządkowana i sortowana
• na podstawie haszujących struktur danych

Tylko trochę więcej informacji z mojego własnego doświadczenia z mapami, kiedy używam każdej z nich:

• HashMap - najbardziej przydatny przy szukaniu najlepszej (szybkiej) implementacji.
• TreeMap (SortedMap interface) - najbardziej przydatne, gdy chodzi o możliwość sortowania lub iteracji kluczy w określonej kolejności, którą definiuję.
• LinkedHashMap-łączy zalety gwarantowanego zamawiania z mapy drzewa bez zwiększonych kosztów utrzymania mapy drzewa. (Jest prawie tak szybki jak HashMap). W szczególności, LinkedHashMap zapewnia również świetny punkt wyjścia do tworzenia obiektu pamięci podręcznej poprzez nadpisanie removeEldestEntry() metoda. Umożliwia to utworzenie obiektu pamięci podręcznej, który może wygasać dane przy użyciu określonych kryteriów.

Wszystkie trzy klasy HashMap, TreeMap and LinkedHashMap implementuje interfejs java.util.Map i reprezentuje mapowanie z unikalnego klucza do wartości.

HashMap

1. A HashMap zawiera wartości oparte na kluczu.

2. Zawiera tylko unikalne elementy.

3. Może mieć jeden klucz null i wiele wartości null.

4. Utrzymuje nie. zamówienie.

   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

1. a LinkedHashMap zawiera wartości oparte na kluczu.
2. zawiera tylko unikalne elementy.
3. może mieć jeden klucz null i wiele wartości null.

4. Jest taki sam jak HashMap zamiast tego utrzymuje kolejność wstawiania. //Patrz Klasa opóźnienia poniżej

   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

1. A TreeMap zawiera wartości oparte na kluczu. Implementuje interfejs NavigableMap i rozszerza klasę AbstractMap.
2. zawiera tylko unikalne elementy.
3. nie może mieć klucza null, ale może mieć wiele wartości null.

4. Jest taka sama jak HashMap zamiast tego utrzymuje kolejność rosnąca(sortowane według naturalnego porządku klucza.).

   public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

Hashtable

1. Hashtable jest tablicą listy. Każda lista jest znany jako wiadro. Pozycja bucket jest identyfikowana przez wywołanie metody hashcode (). Hashtable zawiera wartości oparte na kluczu.
2. zawiera tylko unikalne elementy.
3. może nie mieć żadnego klucza ani wartości null.
4. jest zsynchronizowane.

5. Jest klasą dziedziczną.

   public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

Ref: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

HashMap nie daje absolutnie żadnych gwarancji co do kolejności iteracji. Informatyka może (i będzie) zmieniać się nawet całkowicie po dodaniu nowych elementów. Mapa drzewa będzie iteracją zgodnie z" naturalną kolejnością " kluczy zgodnie z ich metodą compareTo () (lub dostarczaną zewnętrznie Komparator). Dodatkowo implementuje interfejs SortedMap, który zawiera metody, które zależą od tego porządku sortowania. LinkedHashMap będzie iteracją w kolejności, w jakiej wpisy zostały umieszczone w mapa

Zobacz, jak różna jest wydajność..

Mapa drzewa, która jest implementacją Mapy posortowanej. Złożoność operacji put, get i containsKey wynosi O (log n) ze względu na naturalną kolejność

@ Amit: SortedMap jest interfejsem, podczas gdy {[2] } jest klasą implementującą interfejs SortedMap. Oznacza to, że jeśli postępuje zgodnie z protokołem, który SortedMap prosi o to jego implementatorów. Drzewo, o ile nie jest zaimplementowane jako drzewo wyszukiwania, nie może podać uporządkowanych danych, ponieważ drzewo może być dowolnym rodzajem drzewa. Tak więc, aby TreeMap działał jak posortowany porządek, implementuje SortedMap (np. binarne drzewo wyszukiwania-BST, zbalansowane drzewo wyszukiwania jak AVL i R-B Tree, nawet trójkowe drzewo wyszukiwania-najczęściej używane do iteracyjnych wyszukiwań w uporządkowany sposób ).

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

W skorupie orzecha HashMap: podaje dane w O(1), no ordering

TreeMap : podaje dane w o (log N), baza 2. z zamówionymi kluczami

LinkedHashMap : jest tabelą Hashową z listą linkowaną (pomyśl o indexed-SkipList) umożliwiającą przechowywanie danych w sposób, w jaki są one wstawiane do drzewa. Najlepiej nadaje się do wdrożenia LRU(ostatnio używane).

Są to różne implementacje tego samego interfejsu. Każda implementacja ma pewne zalety i wady (szybkie wstawianie, powolne wyszukiwanie) lub odwrotnie.

Aby uzyskać szczegóły, spójrz na javadoc z TreeMap, HashMap, LinkedHashMap .

Poniżej znajdują się główne różnice między HashMap i TreeMap

1. HashMap nie utrzymuje żadnego porządku. Innymi słowy , HashMap nie daje żadnej gwarancji, że element wstawiony jako pierwszy zostanie wydrukowany jako pierwszy, gdzie podobnie jak TreeSet , Elementy TreeMap są również sortowane zgodnie z naturalną kolejnością jego elementów

2. Wewnętrzna implementacja HashMap używa hashowania i TreeMap wewnętrznie używa Czerwono-czarnego drzewa wdrożenie.

3. HashMap może przechowywać jeden klucz null i wiele wartości null.Mapa drzewa nie może zawierać kluczy null, ale może zawierać wiele wartości null.

4. HashMap przyjmuje stałą wydajność czasu dla podstawowych operacji, takich jak get I put i. e O (1).Zgodnie z dokumentami Oracle , TreeMap zapewnia gwarantowany koszt czasu log (n) dla metody get I put.

5. HashMap jest znacznie szybszy niż mapa drzewa, ponieważ czas działania HashMap jest stały w stosunku do mapy drzewa dziennika dla większości operacji.

6. HashMap używa metody equals() w porównaniu, podczas gdy TreeMap używa metody compareTo () do utrzymywania porządku.

7. HashMap implementuje interfejs mapy, podczas gdy TreeMap implementuje interfejs NavigableMap.

Hash map nie zachowuje kolejności wstawiania.
Przykład. Hashmap Jeśli wstawiasz klucze jako

1  3
5  9
4   6
7   15
3   10

Może przechowywać go jako

4  6
5  9
3  10
1  3
7  15

Linked Hashmap zachowuje kolejność wstawiania.

Przykład.
Jeśli wstawiasz klucze

1  3
5  9
4   6
7   15
3   10

Zapisze go jako

1  3
5  9
4   6
7   15
3   10

Tak samo jak wstawiamy.

Mapa drzewa przechowuje wartości w rosnącej kolejności kluczy. Przykład.
Jeśli wstawiasz klucze

1  3
5  9
4   6
7   15
3   10

Będzie go przechowywać as

1  3
3  10
4   6
5   9
7   15

Wszystkie oferują mapę klucza - > wartości i sposób iteracji kluczy. Najważniejsze rozróżnienie między zajęcia te to gwarancja czasu i kolejność kluczy.

1. HashMap oferuje 0 (1) wyszukiwanie i wstawianie. Jeśli jednak przejdziesz przez klawisze, kolejność klucze są zasadniczo dowolne. Jest on realizowany przez tablicę połączonych list.
2. TreeMap oferuje o (log N) wyszukiwanie i wstawianie. Klucze są uporządkowane, więc jeśli potrzebujesz iteracji poprzez klucze w uporządkowany porządek, możesz. Oznacza to, że klucze muszą zaimplementować porównywalny interfejs.Mapa drzewa jest realizowana przez czerwono-czarne drzewo.
3. LinkedHashMap oferuje 0 (1) wyszukiwanie i wstawianie. Klucze są zamawiane według zamówienia wstawionego. On zaimplementowane przez podwójnie połączone wiadra.

Wyobraź sobie, że przekazałeś pustą mapę drzewa, HashMap i LinkedHashMap do następującej funkcji:

void insertAndPrint(AbstractMap<Integer, String> map) {
  int[] array= {1, -1, 0};
  for (int x : array) {
    map.put(x, Integer.toString(x));
  }
  for (int k: map.keySet()) {
   System.out.print(k + ", ");
  }
}

Wyniki dla każdego z nich będą wyglądały jak wyniki poniżej.

Dla HashMap, wyjście było, w moich własnych testach, {0, 1, -1}, ale to może być dowolne zamówienie. Nie ma gwarancji na zamawiam.
Treemap, wyjście było,{ -1, 0, 1}
LinkedList, wyjście było,{ 1, -1, 0}

• HashMap:

  • zamówienie nie jest utrzymywane
  • szybciej niż LinkedHashMap
  • używane do przechowywania sterty obiektów

• LinkedHashMap:

  • Kolejność wstawiania LinkedHashMap będzie zachowana
  • wolniejszy niż HashMap i szybszy niż TreeMap
  • jeśli chcesz utrzymać zamówienie reklamowe, użyj tego.

• TreeMap:

  • TreeMap jest mapowaniem opartym na drzewie
  • TreeMap będzie podążał za naturalnym kolejność klucza
  • wolniej niż HashMap i LinkedHashMap
  • Użyj mapy drzewa, gdy musisz zachować naturalną (domyślną) kolejność

HashMap
może zawierać jeden klucz null.

HashMap nie utrzymuje porządku.

TreeMap

Mapa drzewa nie może zawierać żadnego klucza null.

TreeMap utrzymuje kolejność rosnącą.

LinkedHashMap

LinkedHashMap może być używany do utrzymywania porządku wstawiania, w którym klucze są wstawiane do mapy lub może być również używany do utrzymywania porządku dostępu, w którym klucze są dostępne.

Przykłady::

1) Mapa HashMap = new HashMap ();

    map.put(null, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");`enter code here`
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    } 

2) Mapa TreeMap = new TreeMap ();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }

3) linkedhashmap map = new LinkedHashMap ();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }