Panduan untuk TreeMap di Java

1. Ikhtisar

Pada artikel ini, kita akan mengeksplorasi implementasi TreeMap dari antarmuka Peta dari Java Collections Framework (JCF).

TreeMap adalah implementasi peta yang membuat entri diurutkan sesuai dengan urutan alami kuncinya atau lebih baik lagi menggunakan pembanding jika disediakan oleh pengguna pada waktu konstruksi.

Sebelumnya, kami telah membahas implementasi HashMap dan LinkedHashMap dan kami akan menyadari bahwa ada cukup banyak informasi tentang cara kerja kelas-kelas ini yang serupa.

Artikel-artikel yang disebutkan sangat disarankan untuk dibaca sebelum melanjutkan dengan yang ini.

2. Penyortiran Default di TreeMap

Secara default, TreeMap mengurutkan semua entri menurut urutan aslinya. Untuk integer, ini berarti urutan menaik dan untuk string, urutan abjad.

Mari kita lihat urutan alami dalam tes:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); }

Perhatikan bahwa kami menempatkan kunci integer dengan cara yang tidak teratur tetapi saat mengambil kunci set, kami mengonfirmasi bahwa mereka memang dipertahankan dalam urutan menaik. Ini adalah urutan alami bilangan bulat.

Begitu juga saat kita menggunakan string, string akan diurutkan sesuai urutan aslinya, yaitu menurut abjad:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() { TreeMap map = new TreeMap(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); }

TreeMap , tidak seperti peta hash dan peta hash tertaut, tidak menggunakan prinsip hashing di mana pun karena tidak menggunakan array untuk menyimpan entri.

3. Penyortiran Kustom di TreeMap

Jika kita tidak puas dengan pengurutan alami TreeMap , kita juga bisa mendefinisikan aturan kita sendiri untuk pengurutan dengan menggunakan komparator selama pembuatan peta pohon.

Dalam contoh di bawah ini, kami ingin kunci integer diurutkan dalam urutan menurun:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }

Peta hash tidak menjamin urutan kunci yang disimpan dan secara khusus tidak menjamin bahwa urutan ini akan tetap sama dari waktu ke waktu, tetapi peta pohon menjamin bahwa kunci akan selalu diurutkan sesuai dengan urutan yang ditentukan.

4. Pentingnya Penyortiran TreeMap

Kita sekarang tahu bahwa TreeMap menyimpan semua entri dalam urutan yang diurutkan. Karena atribut peta pohon ini, kita dapat melakukan kueri seperti; temukan "terbesar", temukan "terkecil", temukan semua kunci yang kurang dari atau lebih besar dari nilai tertentu, dll.

Kode di bawah ini hanya mencakup sebagian kecil dari kasus-kasus ini:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); }

5. Implementasi Internal TreeMap

TreeMap mengimplementasikan antarmuka NavigableMap dan mendasarkan pekerjaan internalnya pada prinsip-prinsip pohon merah-hitam:

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

Prinsip pohon merah-hitam berada di luar cakupan artikel ini, namun, ada hal-hal penting yang perlu diingat untuk memahami bagaimana mereka cocok dengan TreeMap .

Pertama-tama , pohon merah-hitam adalah struktur data yang terdiri dari node; bayangkan sebuah pohon mangga terbalik dengan akarnya di langit dan cabang-cabangnya tumbuh ke bawah. Akar akan berisi elemen pertama yang ditambahkan ke pohon.

Aturannya adalah bahwa mulai dari root, elemen apa pun di cabang kiri node mana pun selalu lebih kecil dari elemen di node itu sendiri. Mereka yang di kanan selalu lebih besar. Apa yang mendefinisikan lebih besar atau lebih kecil dari ditentukan oleh urutan alami elemen atau pembanding yang ditentukan pada konstruksi seperti yang kita lihat sebelumnya.

Aturan ini menjamin bahwa entri peta hierarki akan selalu dalam urutan yang diurutkan dan dapat diprediksi.

Kedua , pohon merah-hitam adalah pohon pencarian biner yang menyeimbangkan diri. Atribut ini dan di atas menjamin bahwa operasi dasar seperti pencarian, dapatkan, letakkan dan hapus membutuhkan waktu logaritmik O (log n) .

Menjadi penyeimbang diri adalah kuncinya di sini. Saat kita terus memasukkan dan menghapus entri, bayangkan pohon itu tumbuh lebih panjang di satu sisi atau lebih pendek di sisi lain.

Ini berarti bahwa operasi akan memakan waktu yang lebih singkat pada cabang yang lebih pendek dan waktu yang lebih lama pada cabang yang paling jauh dari akar, sesuatu yang kita tidak ingin terjadi.

Karena itu, ini diperhatikan dalam desain pohon merah-hitam. Untuk setiap penyisipan dan penghapusan, tinggi maksimum pohon di tepi mana pun dipertahankan pada O (log n) yaitu pohon menyeimbangkan dirinya sendiri secara terus menerus.

Sama seperti peta hash dan peta hash yang ditautkan, peta pohon tidak disinkronkan dan oleh karena itu aturan untuk menggunakannya dalam lingkungan multi-utas serupa dengan yang ada di dua implementasi peta lainnya.

6. Memilih Peta yang Tepat

Setelah melihat implementasi HashMap dan LinkedHashMap sebelumnya dan sekarang TreeMap , penting untuk membuat perbandingan singkat antara ketiganya untuk memandu kami tentang mana yang cocok di mana.

Peta hash bagus sebagai implementasi peta tujuan umum yang menyediakan penyimpanan cepat dan operasi pengambilan. Namun, itu gagal karena pengaturan entri yang kacau dan tidak teratur.

Hal ini menyebabkan performanya buruk dalam skenario di mana ada banyak iterasi karena seluruh kapasitas array yang mendasari memengaruhi traversal selain hanya jumlah entri.

A linked hash map possesses the good attributes of hash maps and adds order to the entries. It performs better where there is a lot of iteration because only the number of entries is taken into account regardless of capacity.

A tree map takes ordering to the next level by providing complete control over how the keys should be sorted. On the flip side, it offers worse general performance than the other two alternatives.

We could say a linked hash map reduces the chaos in the ordering of a hash map without incurring the performance penalty of a tree map.

7. Conclusion

Pada artikel ini, kita telah menjelajahi kelas Java TreeMap dan implementasi internalnya. Karena ini adalah yang terakhir dari rangkaian implementasi antarmuka Peta umum, kami juga melanjutkan untuk membahas secara singkat di mana yang paling cocok dalam kaitannya dengan dua lainnya.

Kode sumber lengkap untuk semua contoh yang digunakan dalam artikel ini dapat ditemukan di proyek GitHub.