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

Jaka jest różnica między HashMap, LinkedHashMapa TreeMapw Javie? Nie widzę żadnej różnicy w wynikach, ponieważ wszystkie trzy mają keySeti values. Co to Hashtablejest

Map m1 = new HashMap();
m1.put("map", "HashMap");
m1.put("schildt", "java2");
m1.put("mathew", "Hyden");
m1.put("schildt", "java2s");
print(m1.keySet()); 
print(m1.values()); 

SortedMap sm = new TreeMap();
sm.put("map", "TreeMap");
sm.put("schildt", "java2");
sm.put("mathew", "Hyden");
sm.put("schildt", "java2s");
print(sm.keySet()); 
print(sm.values());

LinkedHashMap lm = new LinkedHashMap();
lm.put("map", "LinkedHashMap");
lm.put("schildt", "java2");
lm.put("mathew", "Hyden");
lm.put("schildt", "java2s");
print(lm.keySet()); 
print(lm.values());

Wszystkie trzy klasy implementują Mapinterfejs i oferują głównie tę samą funkcjonalność. Najważniejszą różnicą jest kolejność, w której nastąpi iteracja po wpisach:

• HashMapnie daje absolutnie żadnych gwarancji co do kolejności iteracji. Może (i będzie) całkowicie się zmieniać, gdy dodawane są nowe elementy.
• TreeMapwykona iterację zgodnie z „naturalnym uporządkowaniem” kluczy zgodnie z ich compareTo()metodą (lub dostarczoną zewnętrznie Comparator). Dodatkowo implementuje SortedMapinterfejs, który zawiera metody zależne od tego porządku sortowania.
• LinkedHashMap wykona iterację w kolejności, w jakiej wpisy zostały umieszczone na mapie

„Hashtable” to ogólna nazwa map opartych na haszowaniu. W kontekście interfejsu API języka Java Hashtablejest to przestarzała klasa z czasów Java 1.1, zanim istniała struktura kolekcji. Nie należy go już używać, ponieważ jego interfejs API jest zaśmiecony przestarzałymi metodami powielającymi funkcjonalność, a jego metody są zsynchronizowane (co może obniżyć wydajność i jest generalnie bezużyteczne). Użyj ConcurrentHashMap zamiast Hashtable.

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 od unikatowych kluczy do wartości, a zatem implementują interfejs Map .

1. HashMap to mapa oparta na haszowaniu klawiszy. Obsługuje operacje O / 1 get / put. Klucze muszą mieć spójne implementacje hashCode()iequals() aby to działało.

2. LinkedHashMap jest bardzo podobny do HashMap, ale zwiększa świadomość 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 to mapowanie oparte na drzewie. Operacje put / get zajmują czas O (log n). Wymaga, aby przedmioty miały jakiś mechanizm porównywania, albo z Porównywalnym, albo z Komparatorem. Kolejność iteracji jest określana przez ten mechanizm.

Zobacz, gdzie każda klasa znajduje się w hierarchii klas na poniższym diagramie ( większy ). TreeMap implementuje, SortedMapa NavigableMapwhile HashMapnie.

HashTablejest przestarzały i ConcurrentHashMapnależy użyć odpowiedniej klasy.

HashMap

• Ma wartości par (klucze, wartości)
• NIE wartości klucza duplikacji
• nieuporządkowane nieposortowane
• umożliwia jeden klucz zerowy i więcej niż jedną wartość zerową

HashTable

• tak samo jak mapa hash
• nie zezwala na klucze null i wartości null

LinkedHashMap

• Jest to uporządkowana wersja implementacji mapy
• Na podstawie połączonej listy i struktur danych mieszających

TreeMap

• Wersja uporządkowana i posortowana
• oparty na hashujących strukturach danych

Jeszcze trochę informacji z własnego doświadczenia z mapami, kiedy będę z nich korzystać:

• HashMap - Najbardziej przydatny, gdy szukasz implementacji o najlepszej wydajności (szybkiej).
• TreeMap (interfejs SortedMap) - Najbardziej przydatny, gdy martwię się o możliwość sortowania lub iterowania kluczy w określonej przeze mnie kolejności.
• LinkedHashMap - Łączy zalety gwarantowanego zamawiania z TreeMap bez zwiększonych kosztów utrzymania TreeMap. (Jest prawie tak szybki jak HashMap). W szczególności LinkedHashMap stanowi również doskonały punkt wyjścia do utworzenia obiektu Cache poprzez przesłonięcie removeEldestEntry()metody. Umożliwia to utworzenie obiektu pamięci podręcznej, który może wygasać dane przy użyciu określonych przez Ciebie kryteriów.

Wszystkie trzy klasy HashMap, TreeMapi LinkedHashMapimplementuje java.util.Mapinterfejs i reprezentuje mapowanie z unikalnym kluczem do wartości.

HashMap

1. A HashMapzawiera wartości oparte na kluczu.

2. Zawiera tylko unikalne elementy.

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

4. Nie utrzymuje porządku .

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

LinkedHashMap

1. A LinkedHashMapzawiera wartości oparte na kluczu.
2. Zawiera tylko unikalne elementy.
3. Może mieć jeden klucz zerowy i wiele wartości zerowych.

4. Jest to to samo, co HashMap zamiast tego utrzymuje porządek wstawiania . // Zobacz spowolnienie klasy poniżej

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

TreeMap

1. A TreeMapzawiera wartości oparte na kluczu. Implementuje interfejs NavigableMap i rozszerza klasę AbstractMap.
2. Zawiera tylko unikalne elementy.
3. Nie może mieć klucza zerowego, ale może mieć wiele wartości zerowych.

4. Jest to to samo, co HashMapzamiast tego utrzymuje porządek rosnący (posortowany według naturalnej kolejności klucza).

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

Hashtable

1. Hashtable to tablica listy. Każda lista jest znana jako segment. Pozycja segmentu 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 lub wartości zerowej.
4. Jest zsynchronizowany .

5. Jest to klasyczna klasa.

   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 absolutnie nie udziela gwarancji na kolejność iteracji. Może (i będzie) całkowicie się zmieniać, gdy dodawane są nowe elementy. TreeMap wykona iterację zgodnie z „naturalnym uporządkowaniem” kluczy zgodnie z ich metodą CompareTo () (lub zewnętrznie dostarczonym komparatorem). Dodatkowo implementuje interfejs SortedMap, który zawiera metody zależne od tego porządku sortowania. LinkedHashMap wykona iterację w kolejności, w jakiej wpisy zostały umieszczone na mapie

Zobacz, jak zmienia się wydajność.

Mapa drzewa będąca implementacją mapy posortowanej. Złożoność operacji put, get i zawiera klucz to O (log n) ze względu na naturalne uporządkowanie

@Amit: SortedMapto interfejs, podczas TreeMapgdy klasa, która implementuje SortedMapinterfejs. Oznacza to, że jeśli postępuje zgodnie z protokołem, o który SortedMapprosi jego implementator. Drzewo, o ile nie zostanie zaimplementowane jako drzewo wyszukiwania, nie może dać uporządkowanych danych, ponieważ drzewo może być dowolnym rodzajem drzewa. Aby więc TreeMap działał jak Sorted Order, implementuje SortedMap (np. Binary Search Tree - BST, zrównoważony BST jak AVL i RB Tree, a nawet Ternary Search Tree - najczęściej używane do wyszukiwania iteracyjnego w uporządkowany sposób).

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

W NUT-SHELL HashMap: podaje dane w O (1), bez zamawiania

TreeMap : podaje dane w O (log N), baza 2. z uporządkowanymi kluczami

LinkedHashMap: jest funkcją tabeli mieszania z połączoną listą (pomyśl o indeksowanej liście SkipList) do przechowywania danych w sposób, w jaki są wstawiane do drzewa. Najlepiej nadaje się do implementacji LRU (ostatnio używane).

Poniżej wymieniono główne różnice między HashMap i TreeMap

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

2. Wewnętrzna implementacja HashMap korzysta z funkcji Hashing, a TreeMap wewnętrznie korzysta z implementacji drzewa czerwono-czarnego.

3. HashMap może przechowywać jeden klucz zerowy i wiele wartości zerowych. Drzewo nie może zawierać kluczy zerowych, ale może zawierać wiele wartości zerowych.

4. HashMap ma stałą wydajność czasową dla podstawowych operacji, takich jak get i put, tj. O (1). Zgodnie z dokumentacją Oracle, TreeMap zapewnia gwarantowany koszt dziennika (n) dla metody get and put.

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

6. HashMap używa do porównania metody equals (), a TreeMap do porównywania używa metody CompareTo ().

7. HashMap implementuje interfejs Map, a TreeMap implementuje interfejs NavigableMap.

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

Szczegółowe informacje znajdują się w javadoc TreeMap , HashMap , LinkedHashMap .

Mapa mieszania nie zachowuje kolejności wstawiania.
Przykład. Hashmap Jeśli wstawiasz klucze jak

1  3
5  9
4   6
7   15
3   10

Może przechowywać jako

4  6
5  9
3  10
1  3
7  15

Połączony Hashmap zachowuje kolejność wstawiania.

Przykład.
Jeśli wkładasz klucze

1  3
5  9
4   6
7   15
3   10

Będzie przechowywać jako

1  3
5  9
4   6
7   15
3   10

tak samo jak wstawiamy.

Mapa drzewa przechowuje wartości w porządku rosnącym kluczy. Przykład.
Jeśli wkładasz klucze

1  3
5  9
4   6
7   15
3   10

Będzie przechowywać jako

1  3
3  10
4   6
5   9
7   15

• HashMap:

  • Zamówienie nie utrzymuje
  • Szybszy niż LinkedHashMap
  • Służy do przechowywania stosu obiektów

• LinkedHashMap:

  • Kolejność wstawiania LinkedHashMap zostanie zachowana
  • Wolniej niż HashMap i szybciej niż TreeMap
  • Jeśli chcesz zachować zamówienie reklamowe, skorzystaj z tego.

• TreeMap:

  • TreeMap to mapowanie oparte na drzewie
  • TreeMap podąży za naturalną kolejnością kluczy
  • Wolniej niż HashMap i LinkedHashMap
  • Użyj TreeMap, jeśli chcesz zachować porządek naturalny (domyślny)

Wszystkie oferują mapę klucz-> wartość oraz sposób na iterację po klawiszach. Najważniejsze rozróżnienie między tymi klasami to gwarancje czasowe i kolejność kluczy.

1. HashMap oferuje wyszukiwanie i wstawianie 0 (1). Jednak w przypadku iteracji po kluczach kolejność kluczy jest zasadniczo dowolna. Jest realizowany przez szereg połączonych list.
2. TreeMap oferuje wyszukiwanie i wstawianie O (log N). Klucze są uporządkowane, więc jeśli chcesz iterować po nich w uporządkowanej kolejności, możesz to zrobić. Oznacza to, że klucze muszą implementować interfejs Porównywalny. Drzewo Drzew jest realizowane przez Drzewo Czerwono-Czarne.
3. LinkedHashMap oferuje wyszukiwanie i wstawianie 0 (1). Klucze są uporządkowane według kolejności wstawiania. Jest realizowany przez podwójnie połączone wiadra.

Wyobraź sobie, że przekazałeś pustą TreeMap, 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 + ", ");
  }
}

Dane wyjściowe dla każdego będą wyglądać jak poniżej.

W przypadku HashMap dane wyjściowe były według moich testów {0, 1, -1}, ale może to być dowolna kolejność. Nie ma gwarancji na zamówienie.
Treemap, dane wyjściowe to {-1, 0, 1}
LinkedList, dane wyjściowe to {1, -1, 0}

Chociaż jest tu wiele doskonałych odpowiedzi, chciałbym przedstawić własną tabelę opisującą różne Mapimplementacje dołączone do Java 11.

Widzimy te różnice wymienione na grafice tabeli:

• HashMapjest uniwersalnym zastosowaniem Map powszechnie stosowanym, gdy nie masz specjalnych potrzeb.
• LinkedHashMaprozszerza HashMap, dodając to zachowanie: Utrzymuje porządek, w kolejności, w jakiej wpisy zostały pierwotnie dodane . Zmiana wartości przy wprowadzaniu wartości klucza nie zmienia jej miejsca w kolejności.
• TreeMaprównież utrzymuje porządek, ale używa albo (a) „naturalnego” porządku , co oznacza wartość compareTometody na kluczowych obiektach zdefiniowanych w Comparableinterfejsie, lub (b) wywołuje podaną przezComparator Ciebie implementację .
  • TreeMapimplementuje zarówno SortedMapinterfejs, jak i jego następcę, NavigableMapinterfejs.
• NULL s: TreeMapnie nie pozwalają NULL jako klucz , a HashMap&LinkedHashMap zrobić.
  • Wszystkie trzy pozwalają na wartość NULL.
• HashTablejest dziedzictwem , od Java 1 . Dostarczone przez ConcurrentHashMapklasę. Cytując Javadoc: ConcurrentHashMapprzestrzega tej samej specyfikacji funkcjonalnej co Hashtablei zawiera wersje metod odpowiadające każdej z metod Hashtable.

HashMap
może zawierać jeden klucz zerowy.

HashMap nie utrzymuje kolejności.

TreeMap

TreeMap nie może zawierać żadnego klucza zerowego.

TreeMap utrzymuje porządek rosnący.

LinkedHashMap

LinkedHashMap może być używany do utrzymywania kolejności wstawiania, na której klucze są wstawiane do mapy lub może być również używany do utrzymania kolejności dostępu, na której dostępne są klucze.

Przykłady ::

1) Mapa HashMap = nowa 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 = nowa 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) Mapa LinkedHashMap = nowy 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());
    }

Najważniejszym spośród wszystkich trzech jest sposób, w jaki zapisują kolejność wpisów.

HashMap- Nie zapisuje kolejności wpisów. na przykład.

public static void main(String[] args){
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("First",1);// First ---> 1 is put first in the map
        hashMap.put("Second",2);//Second ---> 2 is put second in the map
        hashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : hashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

LinkedHashMap: Zapisuje kolejność, w jakiej dokonano wpisów. na przykład:

public static void main(String[] args){
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("First",1);// First ---> 1 is put first in the map
        linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
        linkedHashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

TreeMap: Zapisuje wpisy w kolejności rosnącej klawiszy. na przykład:

public static void main(String[] args) throws IOException {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("A",1);// A---> 1 is put first in the map
        treeMap.put("C",2);//C---> 2 is put second in the map
        treeMap.put("B",3); //B--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : treeMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }