Java TreeMap vs HashMap

1. Perkenalan

Pada artikel ini, kita akan membandingkan dua implementasi Map : TreeMap dan HashMap .

Kedua implementasi membentuk bagian integral dari Java Collections Framework dan menyimpan data sebagai pasangan nilai kunci .

2. Perbedaan

2.1. Penerapan

Kami pertama-tama akan berbicara tentang HashMap yang merupakan implementasi berbasis hashtable. Ini memperluas kelas AbstractMap dan mengimplementasikan antarmuka Peta . Sebuah HashMap bekerja pada prinsip hashing .

Implementasi Map ini biasanya bertindak sebagai tabel hash bergerombol , tetapi ketika bucket menjadi terlalu besar, mereka akan diubah menjadi node TreeNodes , masing-masing memiliki struktur yang mirip dengan java.util.TreeMap.

Anda dapat menemukan lebih banyak tentang internal HashMap di artikel yang berfokus padanya.

Di sisi lain, TreeMap memperluas kelas AbstractMap dan mengimplementasikan antarmuka NavigableMap . Sebuah TreeMap menyimpan elemen peta di pohon Merah-Hitam , yang merupakan Pohon Pencarian Biner Penyeimbang Diri .

Dan, Anda juga dapat menemukan lebih banyak tentang internal TreeMap dalam artikel yang difokuskan di sini.

2.2. Memesan

HashMap tidak memberikan jaminan apa pun atas cara elemen-elemen tersebut disusun di Peta .

Artinya, kami tidak dapat mengasumsikan urutan apa pun saat mengulang kunci dan nilai dari 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)); }

Namun, item dalam TreeMap yang diurutkan sesuai dengan tatanan alam mereka .

Jika objek TreeMap tidak dapat disortir menurut tatanan alam, maka kita dapat menggunakan Comparator atau Comparable untuk menentukan urutan elemen disusun dalam Peta:

@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. Nilai Null

HashMap memungkinkan penyimpanan paling banyak satu kunci nol dan banyak nilai nol .

Mari kita lihat contohnya:

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

Namun, TreeMap tidak mengizinkan kunci null tetapi mungkin berisi banyak nilai null .

Sebuah nol kunci tidak diperbolehkan karena compareTo () atau membandingkan () metode melempar NullPointerException:

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

Jika kita menggunakan TreeMap dengan Pembanding yang ditentukan pengguna , maka itu tergantung pada implementasi metode bandingkan () bagaimana nilai null ditangani.

3. Analisis Kinerja

Performa adalah metrik paling penting yang membantu kami memahami kesesuaian struktur data dalam kasus penggunaan.

Di bagian ini, kami akan memberikan analisis kinerja yang komprehensif untuk HashMap dan TreeMap.

3.1. HashMap

HashMap, sebagai implementasi berbasis hashtable, secara internal menggunakan struktur data berbasis array untuk mengatur elemennya sesuai dengan fungsi hash .

HashMap memberikan kinerja waktu konstan yang diharapkan O (1) untuk sebagian besar operasi seperti add () , remove (), dan contains (). Oleh karena itu, ini jauh lebih cepat daripada TreeMap .

Waktu rata-rata untuk mencari elemen dengan asumsi yang masuk akal, dalam tabel hash adalah O (1). Namun, penerapan fungsi hash yang tidak tepat dapat menyebabkan distribusi nilai yang buruk dalam keranjang yang mengakibatkan:

  • Overhead Memori - banyak ember tetap tidak digunakan
  • Penurunan Performa - semakin tinggi jumlah tabrakan, semakin rendah performanya

Sebelum Java 8, Rangkaian Terpisah adalah satu-satunya cara yang disukai untuk menangani tabrakan. Ini biasanya diimplementasikan menggunakan daftar tertaut, yaitu , jika ada benturan atau dua elemen berbeda memiliki nilai hash yang sama, maka simpan kedua item dalam daftar tertaut yang sama.

Oleh karena itu, mencari elemen dalam HashMap, dalam kasus terburuk bisa memakan waktu selama mencari elemen dalam daftar tertaut yaitu O (n) waktu.

Namun, dengan adanya JEP 180, ada perubahan halus dalam penerapan cara elemen disusun dalam HashMap.

Menurut spesifikasinya, ketika bucket menjadi terlalu besar dan berisi cukup node, mereka akan diubah menjadi mode TreeNodes , masing-masing memiliki struktur yang mirip dengan yang ada di TreeMap .

Oleh karena itu, jika terjadi tabrakan hash yang tinggi, performa kasus terburuk akan meningkat dari O (n) ke O (log n).

Kode yang melakukan transformasi ini telah diilustrasikan di bawah ini:

if(binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }

Nilai untuk TREEIFY_THRESHOLD adalah delapan yang secara efektif menunjukkan jumlah ambang batas untuk menggunakan pohon daripada daftar tertaut untuk keranjang.

Jelaslah bahwa:

  • Sebuah HashMap membutuhkan cara yang lebih memori daripada yang dibutuhkan untuk menyimpan data yang
  • Sebuah HashMap tidak boleh lebih dari 70% - 75% penuh. Jika mendekati, ukurannya akan diubah dan entri diulangi
  • Rehashing membutuhkan n operasi yang mahal dimana penyisipan waktu konstan kami menjadi orde O (n)
  • Ini adalah algoritma hashing yang menentukan urutan penyisipan objek di 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
  • Karena TreeMap memiliki lokalitas yang lebih signifikan, kita dapat mempertimbangkannya jika kita ingin mengakses objek yang relatif dekat satu sama lain sesuai dengan urutan aslinya.
  • HashMap dapat disetel menggunakan initialCapacity dan loadFactor , yang tidak dimungkinkan untuk TreeMap
  • Kita dapat menggunakan LinkedHashMap jika kita ingin mempertahankan urutan penyisipan sambil memanfaatkan akses waktu yang konstan

6. Kesimpulan

Pada artikel ini, kami menunjukkan perbedaan dan persamaan antara TreeMap dan HashMap .

Seperti biasa, contoh kode untuk artikel ini tersedia di GitHub.