LRU Cache

LRU Cache (Least Recently Used Cache) adalah salah satu jenis algoritma caching yang digunakan untuk mengelola data sementara di memori agar akses data lebih cepat. Ide utamanya adalah menyimpan data yang sering diakses (recently used) dan menghapus data yang paling jarang diakses (least recently used) ketika kapasitas cache sudah penuh. Ini sangat berguna dalam sistem seperti database, web server, atau aplikasi yang memerlukan akses cepat ke data tanpa selalu mengambil dari sumber utama (misalnya disk atau jaringan), sehingga mengurangi latensi dan beban.

LRU Cache biasanya memiliki operasi utama:

• Get(key): Mengambil nilai dari key jika ada, dan menandainya sebagai recently used.

• Put(key, value): Menambahkan atau memperbarui key-value pair. Jika cache penuh, hapus item LRU terlebih dahulu.

Cara Kerja LRU Cache

Cara kerja LRU Cache didasarkan pada prinsip "recently used" untuk menentukan prioritas data:

1. Inisialisasi: Cache memiliki kapasitas maksimal (misalnya, bisa menyimpan 5 item). Saat kosong, kita bisa menambahkan item baru tanpa masalah.

2. Akses Data (Get):

   • Jika key ada di cache (cache hit), ambil nilainya dan pindahkan item tersebut ke posisi "most recently used" (MRU).

   • Jika key tidak ada (cache miss), kembalikan nilai default (misalnya null) dan mungkin tambahkan dari sumber eksternal via put.

3. Tambah/Memperbarui Data (Put):

   • Jika key sudah ada, perbarui nilainya dan pindahkan ke posisi MRU.

   • Jika key baru dan cache belum penuh, tambahkan ke posisi MRU.

   • Jika cache penuh, hapus item di posisi "least recently used" (LRU), lalu tambahkan item baru ke MRU.

4. Pemeliharaan Urutan: Setiap akses (get atau put) memperbarui urutan penggunaan, sehingga item yang baru diakses selalu berada di depan, dan item yang lama tidak diakses berada di belakang.

Contoh sederhana:

• Kapasitas cache: 3.

• Put(1, A) → Cache: [1:A] (MRU: 1)

• Put(2, B) → Cache: [2:B, 1:A] (MRU: 2, LRU: 1)

• Put(3, C) → Cache: [3:C, 2:B, 1:A] (MRU: 3, LRU: 1)

• Get(1) → Pindah 1 ke MRU: [1:A, 3:C, 2:B] (MRU: 1, LRU: 2)

• Put(4, D) → Cache penuh, hapus LRU (2), tambah 4: [4:D, 1:A, 3:C] (MRU: 4, LRU: 3)

Ini memastikan data yang sering digunakan tetap ada, sementara data jarang dipakai dihapus.

Kaitannya dengan Hash Map dan Double Linked List

Implementasi LRU Cache yang efisien (dengan kompleksitas waktu O(1) untuk get dan put) biasanya menggunakan kombinasi Hash Map dan Doubly Linked List (DLL, atau linked list dua arah). Ini karena keduanya saling melengkapi untuk menangani akses cepat dan pemeliharaan urutan.

• Hash Map (atau Dictionary):

  • Digunakan untuk menyimpan key ke pointer node di linked list.

  • Alasan: Memberikan akses O(1) untuk mencari apakah key ada, dan langsung mendapatkan lokasi node-nya tanpa traversal.

  • Tanpa hash map, mencari key akan lambat (O(n) jika hanya linked list).

  • Contoh: Di Java, ini seperti HashMap<Key, Node>, di Python seperti dict[key: node].

• Doubly Linked List (DLL):

  • Digunakan untuk menyimpan urutan item berdasarkan recency (MRU di head, LRU di tail).

  • Setiap node di DLL berisi: key, value, pointer ke node sebelumnya (prev), dan selanjutnya (next).

  • Alasan: DLL memungkinkan penghapusan dan pemindahan node dengan cepat (O(1)) karena pointer dua arah.

    • Pindah node ke head (MRU): Hapus dari posisi saat ini (gunakan prev/next), lalu tambah ke head.

    • Hapus tail (LRU): Langsung akses tail dan hapus.

  • Tanpa DLL, memperbarui urutan akan mahal (misalnya array biasa butuh shifting O(n)).

Hubungan Kedua Struktur:

• Hash Map menunjuk ke node di DLL, sehingga saat get/put:

  • Cari key di hash map → Dapatkan node → Pindahkan node ke head DLL (update urutan) → Update hash map jika perlu.

• Ini seperti "jembatan": Hash map untuk lookup cepat, DLL untuk ordering cepat.

• Di banyak bahasa pemrograman, LRU Cache diimplementasikan seperti ini (misalnya LinkedHashMap di Java yang internally gabungkan hash map dan DLL).