Panduan untuk LinkedHashMap di Java

1. Ikhtisar

Pada artikel ini, kita akan mempelajari implementasi internal kelas LinkedHashMap . LinkedHashMap adalah implementasi umum dari antarmuka Peta .

Implementasi khusus ini adalah subclass dari HashMap dan karena itu berbagi blok bangunan inti dari implementasi HashMap . Akibatnya, sangat disarankan untuk memolesnya sebelum melanjutkan dengan artikel ini.

2. LinkedHashMap vs HashMap

Kelas LinkedHashMap sangat mirip dengan HashMap dalam banyak aspek. Namun, peta hash yang ditautkan didasarkan pada tabel hash dan daftar tertaut untuk meningkatkan fungsionalitas peta hash.

Ini memelihara daftar tertaut ganda yang berjalan melalui semua entri di samping array yang mendasari ukuran default 16.

Untuk menjaga urutan elemen, hashmap yang ditautkan mengubah kelas Map.Entry dari HashMap dengan menambahkan pointer ke entri berikutnya dan sebelumnya:

static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

Perhatikan bahwa kelas entri hanya menambahkan dua petunjuk; before dan after yang memungkinkannya untuk menghubungkan dirinya sendiri ke daftar tertaut. Selain itu, ia menggunakan implementasi kelas Entry dari HashMap.

Terakhir, ingatlah bahwa daftar tertaut ini mendefinisikan urutan iterasi, yang secara default adalah urutan penyisipan elemen (urutan-penyisipan).

3. LinkedHashMap Perjanjian Pemasangan Iklan

Mari kita lihat contoh peta hash tertaut yang mengurutkan entri sesuai dengan cara mereka dimasukkan ke dalam peta. Ini juga menjamin bahwa urutan ini akan dipertahankan sepanjang siklus hidup peta:

@Test public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() { LinkedHashMap map = new LinkedHashMap(); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); Integer[] arr = keys.toArray(new Integer[0]); for (int i = 0; i < arr.length; i++) { assertEquals(new Integer(i + 1), arr[i]); } }

Di sini, kami hanya membuat tes yang belum sempurna dan tidak meyakinkan tentang urutan entri di peta hash yang ditautkan.

Kami dapat menjamin bahwa tes ini akan selalu lulus karena urutan penyisipan akan selalu terjaga. Kami tidak dapat membuat jaminan yang sama untuk HashMap.

Atribut ini bisa sangat bermanfaat dalam API yang menerima peta apa pun, membuat salinan untuk dimanipulasi, dan mengembalikannya ke kode panggilan. Jika klien membutuhkan peta yang dikembalikan untuk diurutkan dengan cara yang sama sebelum memanggil API, maka hashmap yang ditautkan adalah cara yang tepat.

Urutan penyisipan tidak akan terpengaruh jika kunci dimasukkan kembali ke dalam peta.

4. Akses-Order LinkedHashMap

LinkedHashMap menyediakan konstruktor khusus yang memungkinkan kita menentukan, di antara faktor beban khusus (LF) dan kapasitas awal, mekanisme / strategi pemesanan berbeda yang disebut urutan akses :

LinkedHashMap map = new LinkedHashMap(16, .75f, true);

Parameter pertama adalah kapasitas awal, diikuti oleh faktor beban dan parameter terakhir adalah mode pemesanan . Jadi, dengan meneruskan true , kami mengaktifkan access-order, sedangkan default-nya adalah insertion-order.

Mekanisme ini memastikan bahwa urutan iterasi elemen adalah urutan elemen terakhir kali diakses, dari yang paling terakhir diakses hingga yang terakhir diakses.

Jadi, membuat cache Least recent used (LRU) cukup mudah dan praktis dengan jenis peta ini. Sebuah sukses put atau mendapatkan operasi hasil dalam akses untuk entri:

@Test public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() { LinkedHashMap map = new LinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.get(4); assertEquals("[1, 2, 3, 5, 4]", keys.toString()); map.get(1); assertEquals("[2, 3, 5, 4, 1]", keys.toString()); map.get(3); assertEquals("[2, 5, 4, 1, 3]", keys.toString()); }

Perhatikan bagaimana urutan elemen dalam kumpulan kunci diubah saat kita melakukan operasi akses pada peta.

Sederhananya, setiap operasi akses pada hasil peta dalam urutan sedemikian rupa sehingga elemen yang diakses akan muncul terakhir jika iterasi akan segera dilakukan.

Setelah contoh di atas, jelaslah bahwa operasi putAll menghasilkan satu akses entri untuk setiap pemetaan di peta yang ditentukan.

Secara alami, iterasi pada tampilan peta tidak mempengaruhi urutan iterasi peta pendukung; hanya operasi akses eksplisit di peta yang akan memengaruhi pesanan .

LinkedHashMap juga menyediakan mekanisme untuk mempertahankan sejumlah pemetaan tetap dan untuk tetap melepaskan entri terlama jika ada yang baru perlu ditambahkan.

The removeEldestEntry metode dapat diganti untuk menegakkan kebijakan ini untuk menghapus pemetaan basi otomatis.

Untuk melihat ini dalam praktiknya, mari kita buat kelas peta hash tertaut kita sendiri, dengan tujuan semata-mata untuk memaksakan penghapusan pemetaan lama dengan memperluas LinkedHashMap :

public class MyLinkedHashMap extends LinkedHashMap { private static final int MAX_ENTRIES = 5; public MyLinkedHashMap( int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }

Penimpaan kami di atas akan memungkinkan peta berkembang menjadi ukuran maksimum 5 entri. Ketika ukurannya melebihi itu, setiap entri baru akan dimasukkan dengan biaya kehilangan entri tertua di peta, yaitu entri yang waktu akses terakhirnya mendahului semua entri lainnya:

@Test public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() { LinkedHashMap map = new MyLinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.put(6, null); assertEquals("[2, 3, 4, 5, 6]", keys.toString()); map.put(7, null); assertEquals("[3, 4, 5, 6, 7]", keys.toString()); map.put(8, null); assertEquals("[4, 5, 6, 7, 8]", keys.toString()); }

Perhatikan bagaimana entri terlama di awal kumpulan kunci terus menurun saat kita menambahkan yang baru ke peta.

5. Pertimbangan Kinerja

Sama seperti HashMap , LinkedHashMap melakukan operasi Peta dasar untuk menambah, menghapus, dan memuat dalam waktu konstan, selama fungsi hash berdimensi baik. Ini juga menerima kunci nol serta nilai nol.

Namun, kinerja LinkedHashMap waktu konstan ini kemungkinan akan sedikit lebih buruk daripada waktu konstan HashMap karena biaya tambahan untuk mempertahankan daftar tertaut ganda.

Iterasi atas tampilan kumpulan LinkedHashMap juga membutuhkan waktu linier O (n) mirip dengan HashMap . Di sisi lain, kinerja waktu linier LinkedHashMap selama iterasi lebih baik daripada waktu linier HashMap .

Ini karena, untuk LinkedHashMap , n di O (n) hanyalah jumlah entri di peta terlepas dari kapasitasnya. Sedangkan untuk HashMap , n adalah kapasitas dan ukuran dijumlahkan, O (ukuran + kapasitas).

Faktor Beban dan Kapasitas Awal didefinisikan persis seperti untuk HashMap . Namun, perhatikan bahwa hukuman untuk memilih nilai yang terlalu tinggi untuk kapasitas awal tidak terlalu berat untuk LinkedHashMap daripada untuk HashMap , karena waktu iterasi untuk kelas ini tidak terpengaruh oleh kapasitas.

6. Konkurensi

Sama seperti HashMap , implementasi LinkedHashMap tidak disinkronkan. Jadi jika Anda akan mengaksesnya dari beberapa utas dan setidaknya satu dari utas ini cenderung mengubahnya secara struktural, maka itu harus disinkronkan secara eksternal.

Yang terbaik adalah melakukan ini saat pembuatan:

Map m = Collections.synchronizedMap(new LinkedHashMap());

Perbedaan dengan HashMap terletak pada apa yang memerlukan modifikasi struktural. Dalam peta hash tertaut dengan urutan akses, hanya memanggil get API akan menghasilkan modifikasi struktural . Bersamaan dengan ini, ada operasi seperti put dan hapus .

7. Kesimpulan

Pada artikel ini, kami telah menjelajahi kelas Java LinkedHashMap sebagai salah satu implementasi utama antarmuka Peta dalam hal penggunaan. Kami juga telah mengeksplorasi cara kerja internal dalam hal perbedaan dari HashMap yang merupakan superclass-nya.

Mudah-mudahan, setelah membaca posting ini, Anda dapat membuat keputusan yang lebih tepat dan efektif tentang implementasi Peta mana yang akan diterapkan dalam kasus penggunaan Anda.

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