Dalam artikel ini, kami mulai menganalisis kode sumber LinkedHashMap. LinkedHashMap mewarisi hashmap, yang berarti bahwa LinkedHashMap diperluas berdasarkan hashmap. Oleh karena itu, sebelum melihat kode sumber LinkedHashMap, pembaca perlu memahami kode sumber hashmap. Anda dapat memeriksa pengenalan artikel saya sebelumnya "Java Collection Series [3] ---- Analisis Kode Sumber Hashmap". Selama Anda memiliki pemahaman yang mendalam tentang prinsip implementasi hashmap, dan kemudian lihat kode sumber LinkedHashMap, Hashset dan LinkedHashset semuanya sangat sederhana. Oleh karena itu, pembaca harus bersabar dan mempelajari kode sumber hashmap. Ini adalah bisnis yang baik untuk membeli satu mendapatkan tiga gratis. Ketika menganalisis kode sumber hashmap sebelumnya, saya menggunakan analisis yang berorientasi masalah dari kode sumber sehingga saya tidak akan menganalisisnya secara acak seperti lalat tanpa kepala, dan pembaca juga dapat memiliki pemahaman yang lebih dalam tentang masalah tersebut. Dalam artikel ini, saya memutuskan untuk menggunakan metode ini untuk menganalisis LinkedHashMap.
1. Struktur seperti apa yang digunakan di dalam LinkedHashMap?
Seperti yang Anda lihat, karena LinkedHashMap mewarisi dari HashMap, masih ada tabel hash di dalam LinkedHashMap, tetapi LinkedHashMap telah menulis ulang entri dan menambahkan dua variabel anggota ke entri HashMap asli, yaitu referensi simpul sebelumnya dan referensi simpul penerus. Dengan cara ini, semua node dihubungkan bersama untuk membentuk daftar tertaut dua arah. Saat mendapatkan elemen, cukup lintasi daftar ditautkan dua arah secara langsung. Mari kita lihat seperti apa implementasi entri LinkedHashMap.
Entri kelas statis pribadi <k, v> memperluas hashmap.entry <k, v> {// referensi simpul sebelumnya dari node saat ini dalam entri daftar ditautkan dua arah <K, V> sebelumnya; // Referensi simpul selanjutnya dari node saat ini dalam entri daftar ditautkan dua arah <k, v> setelah; Entri (int hash, K key, nilai v, hashmap.entry <k, v> next) {super (hash, kunci, nilai, selanjutnya); } // Hapus simpul ini dari daftar ditautkan dianjeksi pribadi void rape () {before.after = setelah; After.Before = Sebelumnya; } // Masukkan simpul saat ini ke dalam node yang ada dalam daftar tautan dua arah private void addBefore (entri <k, v> existingEntry) {// referensi simpul berikutnya dari node saat ini menunjuk ke simpul yang diberikan setelah = yang ada; // Referensi node sebelumnya dari simpul saat ini menunjuk ke simpul sebelumnya dari simpul yang diberikan sebelum = yang ada. Sebelum; // Referensi simpul berikutnya dari simpul yang diberikan poin ke simpul saat ini sebelumnya. // Referensi node sebelumnya dari simpul yang diberikan menunjuk ke simpul saat ini setelah. Before = this; } // diurutkan dalam urutan akses, rekam setiap kali operasi diperoleh void recordAccess (hashMap <k, v> m) {linkedHashMap <k, v> lm = (linkedHashMap <k, v>) m; // jika diurutkan dalam urutan akses if (lm.accessorder) {lm.modcount ++; // Lepaskan diri Anda dari daftar ditautkan dua arah terlebih dahulu; // Tempatkan diri Anda pada ekor daftar tautan dua arah addbefore (lm.header); }} void recordRemoval (hashMap <k, v> m) {remove (); }}2. Bagaimana LinkedHashMap menerapkan penyortiran dalam urutan penyisipan?
// Metode yang akan dipanggil dalam metode put dari kelas inden indentry induk (int hash, k kunci, nilai v, int bucketIndex) {// memanggil metode addEntry dari kelas induk super.addentry (hash, kunci, nilai, bucketindex); // Operasi berikut nyaman untuk implementasi cache LRU. Jika kapasitas cache tidak cukup, lepaskan entri elemen tertua <k, v> elderly = header.after; if (RemestEldestEntry (tertua)) {RemoveEntryForKey (Eldest.key); }} // Metode membatalkan CreateEntry (int hash, K key, value v, int bucketIndex) {// Pertama dapatkan entri hashmap hashmap.entry <k, v> old = tabel [bucketindex]; // Bungkusnya menjadi entri LinkedHashMap sendiri <k, v> e = entri baru <> (hash, kunci, nilai, lama); tabel [bucketindex] = e; // Masukkan simpul saat ini ke ekor daftar ditautkan dua arah e.addbefore (header); ukuran ++;}LinkedHashMap mengesampingkan metode addentry dan createentry dari hashmap kelas induknya. Ketika Anda ingin memasukkan pasangan nilai kunci, metode put hashmap kelas induknya akan dipanggil terlebih dahulu. Dalam metode put, kami akan memeriksa apakah kunci yang sesuai ada di tabel hash. Jika ada, ganti saja nilainya secara langsung. Jika tidak ada, hubungi metode AddEntry untuk membuat entri baru. Perhatikan bahwa saat ini, metode addEntry LinkedHashMap dipanggil. Kami melihat kode di atas. Selain menelepon kembali metode addeldestentry dari kelas induk, addeldestentry ini juga akan memanggil reme -estentry untuk menghapus elemen tertua. Operasi ini terutama untuk mengimplementasikan algoritma LRU, yang akan dibahas di bawah ini. Kami melihat bahwa LinkedHashMap juga menulis ulang metode CreateEntry. Saat Anda ingin membuat entri baru, metode ini akan dipanggil. Setelah setiap kali entri dimasukkan ke dalam tabel hash, metode AddBefore akan dipanggil untuk memasukkan node saat ini ke dalam ekor daftar ditautkan dua arah. Dengan cara ini, daftar ditautkan dua arah mencatat urutan setiap node yang dimasukkan. Saat mendapatkan elemen, cukup lintasi daftar ditautkan dua arah. Gambar berikut menunjukkan pengoperasian setiap panggilan untuk menambahkan. Karena ini adalah daftar ditautkan dua arah, sebelum memasukkan simpul saat ini ke dalam simpul head, sebenarnya memasukkan simpul saat ini ke dalam ekor daftar ditautkan dua arah.
3. Bagaimana cara menggunakan LinkedHashMap untuk mengimplementasikan cache LRU?
Kita tahu bahwa implementasi cache tergantung pada memori komputer, dan sumber daya memori sangat terbatas, dan tidak mungkin untuk menyimpan elemen tanpa batas. Oleh karena itu, kita perlu menghapus beberapa elemen dengan tepat ketika kapasitas tidak cukup. Jadi elemen mana yang lebih baik untuk dihapus? Gagasan algoritma LRU adalah bahwa jika data telah diakses baru -baru ini, kemungkinan diakses di masa depan juga lebih tinggi. Jadi kita dapat menghapus data yang tidak sering diakses. Selanjutnya, mari kita lihat bagaimana LinkedHashMap mengimplementasikan mekanisme LRU.
kelas publik LinkedHashMap <K, V> memperluas hashmap <k, v> mengimplementasikan peta <k, v> {// tajuk tajuk private transient header private header <K, v>; // Urutkan Private Final Boolean AccessOrder dalam urutan akses; ... Public LinkedHashMap (int InitialCapacity, Float LoadFactor, Boolean AccessOrder) {Super (InitialCapacity, LoadFactor); this.accessOrder = accessOrder; } // Dapatkan nilai sesuai dengan kunci publik v get (kunci objek) {// Memanggil metode kelas induk untuk mendapatkan entri entri yang sesuai <k, v> e = (entri <k, v>) getEntrry (key); if (e == null) {return null; } // Jika diurutkan dalam urutan akses, simpul setelah setiap penggunaan akan ditempatkan pada akhir daftar ditautkan dua arah E.RecordAccess (ini); mengembalikan nilai E.; } Entri kelas statis pribadi <K, v> memperluas hashmap.entry <k, v> {... // Masukkan simpul saat ini ke depan simpul yang ada dalam daftar dua kalimat yang ditautkan. // Referensi node sebelumnya dari simpul saat ini menunjuk ke simpul sebelumnya dari simpul yang diberikan sebelum = yang ada. Sebelum; // Referensi simpul berikutnya dari simpul yang diberikan poin ke simpul saat ini sebelumnya. // Referensi node sebelumnya dari simpul yang diberikan menunjuk ke simpul saat ini setelah. Before = this; } // diurutkan dalam urutan akses, rekam setiap kali operasi void recordAccess (hashMap <k, v> m) {linkedHashMap <k, v> lm = (linkedHashMap <k, v>) m; // jika diurutkan dalam urutan akses if (lm.accessorder) {lm.modcount ++; // Lepaskan diri Anda dari daftar ditautkan dua arah terlebih dahulu; // Tempatkan diri Anda pada ekor daftar tautan dua arah addbefore (lm.header); }} ...} // Metode ini akan dipanggil di kelas induk. Metode put void addEntry (int hash, tombol k, nilai v, int bucketindex) {// Hitung metode addEntry kelas induk super.addentry (hash, kunci, nilai, bucketindex); // Operasi berikut nyaman untuk implementasi cache LRU. Jika kapasitas cache tidak cukup, lepaskan entri elemen tertua <k, v> elderly = header.after; if (remeforEldestry (ELDEST)) {RemexelDestForKey (eldest.key); }} // Di mana harus menghapus elemen tertua? Metode ini dirancang untuk ditimpa oleh subclasses yang dilindungi boolean lepasDestEntry (map.entry <k, v> elderly) {return false; }}Agar lebih intuitif, saya menghilangkan beberapa kode yang tidak relevan dalam kode yang diposting di atas. Kita dapat melihat bahwa LinkedHashMap memiliki Variable AccessOrder anggota, yang mencatat apakah perlu diurutkan dalam urutan akses. Ini menyediakan konstruktor yang dapat menentukan nilai AccessOrder itu sendiri. Setiap kali Anda memanggil metode GET untuk mendapatkan elemen, E.RecordAccess (ini) dipanggil, yang akan memindahkan simpul saat ini ke akhir daftar ditautkan dua arah. Sekarang kita tahu bahwa jika AccessOrder benar, maka setiap kali kita mendapatkan elemen, kita akan memindahkan elemen ini ke akhir daftar tautan dua arah. Tujuan dari langkah ini adalah untuk membedakan elemen yang paling umum digunakan dari yang tidak sering digunakan, dan elemen yang sering digunakan ditempatkan di ujung dan elemen yang kurang umum digunakan ditempatkan di kepala. Mari kita kembali ke kode di atas dan lihat bahwa setiap kali metode addentry dipanggil, kita akan menentukan apakah elemen tertua perlu dihapus. Logika penilaian diimplementasikan oleh RemestEldestentry, yang dirancang untuk ditimpa oleh subkelas dan menulis ulang logika di dalamnya. Perhatikan bahwa karena node yang baru -baru ini dikunjungi dipindahkan ke ekor daftar ditautkan dua arah, simpul tertua dikeluarkan dari kepala daftar ditautkan dua arah untuk dihapus. Contoh berikut mengimplementasikan cache LRU sederhana.
kelas publik lrumap <k, v> meluas linkedhashmap <k, v> {private int kapasitas; Lrumap (int kapasitas) {// memanggil konstruktor kelas induk, diatur untuk mengurutkan order akses super (kapasitas, 1f, true); this.capacity = kapasitas; } @Override Public Boolean RemestEldestEntry (MAP.ENTRY <K, V> Elderly) {// Ketika pasangan nilai kunci lebih besar dari atau sama dengan pengembalian kapasitas tabel hash ini.size ()> = kapasitas; } public static void main (string [] args) {lrumap <integer, string> map = new lrumap <integer, string> (4); Map.put (1, "A"); peta.put (2, "b"); Map.put (3, "C"); System.out.println ("Koleksi Asli:" + Peta); String s = map.get (2); System.out.println ("Get Element:" + Map); Map.put (4, "D"); System.out.println ("Setelah penyisipan:" + peta); }}Hasilnya adalah sebagai berikut:
Catatan: Semua analisis di atas didasarkan pada JDK1.7, dan akan ada perbedaan antara versi yang berbeda, pembaca perlu memperhatikan.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.