Perbedaan antara HashMap, LinkedHashMap dan TreeMap

Apa perbedaan antara HashMap, LinkedHashMapdan TreeMapdi Jawa? Saya tidak melihat perbedaan dalam output karena ketiganya memiliki keySetdan values. Apa Hashtables?

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());

Ketiga kelas mengimplementasikan Mapantarmuka dan menawarkan sebagian besar fungsi yang sama. Perbedaan yang paling penting adalah urutan pengulangan melalui entri:

• HashMapsama sekali tidak menjamin tentang urutan iterasi. Itu dapat (dan akan) bahkan berubah sepenuhnya ketika elemen baru ditambahkan.
• TreeMapakan beralih sesuai dengan "pemesanan alami" kunci sesuai dengan compareTo()metode mereka (atau dipasok secara eksternal Comparator). Selain itu, ia mengimplementasikan SortedMapantarmuka, yang berisi metode yang bergantung pada urutan semacam ini.
• LinkedHashMap akan mengulangi urutan entri dimasukkan ke dalam peta

"Hashtable" adalah nama umum untuk peta berbasis hash. Dalam konteks Java API, Hashtableadalah kelas usang dari zaman Java 1.1 sebelum kerangka koleksi ada. Seharusnya tidak digunakan lagi, karena API-nya berantakan dengan metode usang yang menduplikasi fungsi, dan metode-metodenya disinkronkan (yang dapat menurunkan kinerja dan umumnya tidak berguna). Gunakan ConcurrentHashMap, bukan Hashtable.

Saya lebih suka presentasi visual:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

Ketiganya mewakili pemetaan dari kunci unik hingga nilai, dan karenanya mengimplementasikan antarmuka Peta .

1. HashMap adalah peta berdasarkan hashing dari kunci. Ini mendukung O (1) mendapatkan / menempatkan operasi. Kunci harus memiliki implementasi yang konsisten hashCode()danequals() agar ini berfungsi.

2. LinkedHashMap sangat mirip dengan HashMap, tetapi menambah kesadaran pada urutan item ditambahkan (atau diakses), sehingga urutan iterasi sama dengan urutan penyisipan (atau urutan akses, tergantung pada parameter konstruksi).

3. TreeMap adalah pemetaan berbasis pohon. Operasi put / get-nya membutuhkan waktu O (log n). Dibutuhkan item untuk memiliki beberapa mekanisme perbandingan, baik dengan Sebanding atau Pembanding. Urutan iterasi ditentukan oleh mekanisme ini.

Lihat di mana setiap kelas berada dalam hierarki kelas dalam diagram berikut ( lebih besar ). TreeMap mengimplementasikan SortedMapdan NavigableMapsementara HashMaptidak.

HashTablesudah usang dan ConcurrentHashMapkelas yang sesuai harus digunakan.

HashMap

• Ini memiliki nilai pasangan (kunci, nilai)
• TIDAK ADA nilai kunci duplikasi
• unordered unsorted
• itu memungkinkan satu kunci nol dan lebih dari satu nilai nol

HashTable

• sama seperti peta hash
• itu tidak memungkinkan kunci nol dan nilai nol

LinkedHashMap

• Diperintahkan versi implementasi peta
• Berdasarkan daftar tertaut dan hashing struktur data

TreeMap

• Versi yang dipesan dan disortir
• berdasarkan struktur data hashing

Hanya beberapa masukan lagi dari pengalaman saya sendiri dengan peta, kapan saya akan menggunakan masing-masing:

• HashMap - Paling berguna ketika mencari implementasi dengan kinerja terbaik (cepat).
• TreeMap (antarmuka SortedMap) - Paling berguna ketika saya ingin mengurutkan atau beralih pada kunci dalam urutan tertentu yang saya tentukan.
• LinkedHashMap - Menggabungkan keuntungan dari pemesanan yang dijamin dari TreeMap tanpa peningkatan biaya pemeliharaan TreeMap. (Ini hampir secepat HashMap). Secara khusus, LinkedHashMap juga menyediakan titik awal yang bagus untuk membuat objek Cache dengan mengganti removeEldestEntry()metode. Ini memungkinkan Anda membuat objek Cache yang dapat kedaluwarsa menggunakan beberapa kriteria yang Anda tentukan.

Ketiga kelas HashMap, TreeMapdan LinkedHashMapmengimplementasikan java.util.Mapantarmuka, dan mewakili pemetaan dari kunci unik ke nilai.

HashMap

1. A HashMapberisi nilai-nilai berdasarkan kunci.

2. Ini hanya mengandung elemen unik.

3. Mungkin memiliki satu kunci nol dan beberapa nilai nol.

4. Tidak mempertahankan pesanan .

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

LinkedHashMap

1. A LinkedHashMapberisi nilai-nilai berdasarkan kunci.
2. Ini hanya mengandung elemen unik.
3. Mungkin memiliki satu kunci nol dan beberapa nilai nol.

4. Ini sama dengan HashMap sebagai gantinya mempertahankan urutan penyisipan . // Lihat deselerasi kelas di bawah

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

TreeMap

1. A TreeMapberisi nilai-nilai berdasarkan kunci. Ini mengimplementasikan antarmuka NavigableMap dan memperluas kelas AbstractMap.
2. Ini hanya mengandung elemen unik.
3. Itu tidak dapat memiliki kunci nol tetapi dapat memiliki beberapa nilai null.

4. Ini sama dengan HashMapsebaliknya mempertahankan urutan naik (Diurutkan menggunakan urutan alami kuncinya.).

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

Hashtable

1. Hashtable adalah array daftar. Setiap daftar dikenal sebagai ember. Posisi bucket diidentifikasi dengan memanggil metode kode hash (). Hashtable berisi nilai berdasarkan kunci.
2. Ini hanya mengandung elemen unik.
3. Mungkin tidak memiliki kunci atau nilai nol.
4. Ini disinkronkan .

5. Ini adalah kelas warisan.

   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 sama sekali tidak menjamin tentang urutan iterasi. Itu dapat (dan akan) bahkan berubah sepenuhnya ketika elemen baru ditambahkan. TreeMap akan beralih sesuai dengan "pemesanan alami" kunci sesuai dengan metode compareTo () mereka (atau Pembanding yang dipasok secara eksternal). Selain itu, ini mengimplementasikan antarmuka SortedMap, yang berisi metode yang bergantung pada urutan pengurutan ini. LinkedHashMap akan mengulangi urutan entri dimasukkan ke dalam peta

Lihatlah bagaimana kinerja bervariasi.

Tree tree yang merupakan implementasi dari Sorted map. Kompleksitas operasi put, get, dan containKey adalah O (log n) karena pemesanan Natural

@Amit: SortedMapadalah antarmuka sedangkan TreeMapkelas yang mengimplementasikan SortedMapantarmuka. Itu berarti jika mengikuti protokol yang SortedMapmeminta pelaksana untuk melakukannya. Sebuah pohon kecuali diimplementasikan sebagai pohon pencarian, tidak dapat memberi Anda data yang diurutkan karena pohon dapat berupa jenis pohon apa pun. Jadi untuk membuat TreeMap berfungsi seperti urutan Diurutkan, itu mengimplementasikan SortedMap (misalnya, Binary Search Tree - BST, BST seimbang seperti AVL dan RB Tree, bahkan Pohon Pencarianary - kebanyakan digunakan untuk pencarian berulang dengan cara yang dipesan).

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

Dalam NUT-SHELL HashMap: memberikan data dalam O (1), tanpa pemesanan

TreeMap : memberikan data dalam O (log N), basis 2. dengan kunci yang dipesan

LinkedHashMap: adalah tabel Hash dengan daftar tertaut (pikirkan indeks-SkipList) kemampuan untuk menyimpan data dengan cara itu dimasukkan ke dalam pohon. Paling cocok untuk menerapkan LRU (paling baru digunakan).

Berikut ini adalah perbedaan utama antara HashMap dan TreeMap

1. HashMap tidak mempertahankan pesanan apa pun. Dengan kata lain, HashMap tidak memberikan jaminan bahwa elemen yang dimasukkan terlebih dahulu akan dicetak terlebih dahulu, sedangkan Sama seperti TreeSet, elemen TreeMap juga diurutkan sesuai dengan urutan alami dari elemen-elemennya.

2. Implementasi HashMap internal menggunakan Hashing dan TreeMap secara internal menggunakan implementasi Red-Black tree.

3. HashMap dapat menyimpan satu kunci nol dan banyak nilai null. MapMap tidak dapat berisi kunci nol tetapi mungkin mengandung banyak nilai null.

4. HashMap mengambil kinerja waktu yang konstan untuk operasi dasar seperti get and put yaitu O (1). Menurut Oracle docs, TreeMap menyediakan jaminan log (n) biaya waktu untuk metode get and put.

5. HashMap jauh lebih cepat daripada TreeMap, karena waktu kinerja HashMap konstan terhadap waktu log TreeMap untuk sebagian besar operasi.

6. HashMap menggunakan metode equals () sebagai perbandingan sementara TreeMap menggunakan metode compareTo () untuk mempertahankan pemesanan.

7. HashMap mengimplementasikan antarmuka Peta sementara TreeMap mengimplementasikan antarmuka NavigableMap.

Ini adalah implementasi yang berbeda dari antarmuka yang sama. Setiap implementasi memiliki beberapa kelebihan dan beberapa kelemahan (insert cepat, pencarian lambat) atau sebaliknya.

Untuk detail, lihat javadoc TreeMap , HashMap , LinkedHashMap .

Peta hash tidak mempertahankan urutan penyisipan.
Contoh. Hashmap Jika Anda memasukkan kunci sebagai

1  3
5  9
4   6
7   15
3   10

Itu bisa menyimpannya sebagai

4  6
5  9
3  10
1  3
7  15

Linked Hashmap mempertahankan urutan penyisipan.

Contoh.
Jika Anda memasukkan kunci

1  3
5  9
4   6
7   15
3   10

Ini akan menyimpannya sebagai

1  3
5  9
4   6
7   15
3   10

sama seperti yang kita masukkan.

Peta pohon menyimpan katup dalam Meningkatkan Urutan Kunci. Contoh.
Jika Anda memasukkan kunci

1  3
5  9
4   6
7   15
3   10

Ini akan menyimpannya sebagai

1  3
3  10
4   6
5   9
7   15

• HashMap:

  • Pesanan tidak berlaku
  • Lebih cepat dari LinkedHashMap
  • Digunakan untuk menyimpan tumpukan benda

• LinkedHashMap:

  • Pesanan penyisipan LinkedHashMap akan dipertahankan
  • Lebih lambat dari HashMap dan lebih cepat dari TreeMap
  • Jika Anda ingin mempertahankan urutan penyisipan, gunakan ini.

• TreeMap:

  • TreeMap adalah pemetaan berbasis pohon
  • TreeMap akan mengikuti pemesanan kunci secara alami
  • Lebih lambat dari HashMap dan LinkedHashMap
  • Gunakan TreeMap ketika Anda perlu mempertahankan pemesanan alami (default)

Semua menawarkan kunci-> peta nilai dan cara untuk beralih melalui kunci. Perbedaan paling penting antara kelas-kelas ini adalah jaminan waktu dan pemesanan kunci.

1. HashMap menawarkan 0 (1) pencarian dan penyisipan. Jika Anda beralih melalui kunci, pemesanan kunci pada dasarnya sewenang-wenang. Ini diterapkan oleh berbagai daftar tertaut.
2. TreeMap menawarkan pencarian dan penyisipan O (log N). Kunci dipesan, jadi jika Anda perlu mengulangi kunci dalam urutan, Anda bisa. Ini berarti bahwa kunci harus mengimplementasikan antarmuka yang sebanding. TreeMap diimplementasikan oleh Pohon Merah-Hitam.
3. LinkedHashMap menawarkan 0 (1) pencarian dan penyisipan. Kunci diperintahkan oleh urutan penyisipan mereka. Ini diimplementasikan oleh bucket yang tertaut ganda.

Bayangkan Anda melewati TreeMap, HashMap, dan LinkedHashMap kosong ke dalam fungsi berikut:

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 + ", ");
  }
}

Output untuk masing-masing akan terlihat seperti hasil di bawah ini.

Untuk HashMap, hasilnya adalah, dalam pengujian saya sendiri, {0, 1, -1}, tetapi bisa berupa pemesanan apa pun. Tidak ada jaminan pemesanan.
Treemap, outputnya adalah, {-1, 0, 1}
LinkedList, outputnya adalah, {1, -1, 0}

Meskipun ada banyak Jawaban yang sangat bagus di sini, saya ingin menyajikan meja saya sendiri yang menjelaskan berbagai Map implementasi yang dibundel dengan Java 11.

Kita dapat melihat perbedaan-perbedaan ini tercantum pada grafik tabel:

• HashMapadalah tujuan Map umum yang umum digunakan ketika Anda tidak memiliki kebutuhan khusus.
• LinkedHashMapmeluas HashMap, menambahkan perilaku ini: Mempertahankan pesanan, urutan entri awalnya ditambahkan . Mengubah nilai untuk entri nilai kunci tidak mengubah tempatnya dalam urutan.
• TreeMapjuga mempertahankan pesanan, tetapi menggunakan salah satu (a) urutan "alami" , yang berarti nilai dari compareTometode pada objek kunci yang didefinisikan padaComparable interface, atau (b) memanggil sebuah Comparatorimplementasi yang Anda berikan.
  • TreeMap mengimplementasikan kedua SortedMap antarmuka, dan penggantinya, NavigableMapantarmuka.
• NULL s:TreeMap tidak tidak memungkinkan NULL sebagai kunci , sementara HashMap& LinkedHashMaplakukan.
  • Ketiganya memungkinkan NULL sebagai nilainya.
• HashTableadalah warisan , dari Jawa 1 . Disuplai oleh ConcurrentHashMapkelas. Mengutip Javadoc: ConcurrentHashMapmematuhi spesifikasi fungsional yang sama dengan Hashtable, dan termasuk versi metode yang sesuai dengan masing-masing metode Hashtable.

HashMap
dapat berisi satu kunci nol.

HashMap tidak melakukan pemesanan.

TreeMap

TreeMap tidak dapat berisi kunci null.

TreeMap mempertahankan urutan naik.

LinkedHashMap

LinkedHashMap dapat digunakan untuk mempertahankan urutan penyisipan, di mana kunci dimasukkan ke dalam Peta atau juga dapat digunakan untuk mempertahankan urutan akses, di mana kunci diakses.

Contohnya ::

1) Peta HashMap = HashMap baru ();

    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) Peta TreeMap = TreeMap baru ();

    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());
    }

Yang paling penting di antara ketiganya adalah bagaimana mereka menyimpan urutan entri.

HashMap- Tidak menyimpan urutan entri. misalnya.

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: Ini menyimpan urutan entri dibuat. misalnya:

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: Ini menyimpan entri dalam urutan tombol. misalnya:

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());
        }
    }