Cache adalah tempat menyimpan data yang sering dipakai, supaya gak perlu diambil atau dihitung ulang. Masalahnya, tempatnya terbatas. LRU cache (Least Recently Used) punya aturan sederhana waktu penuh: buang data yang paling lama gak dipakai. Mirip meja belajar yang cuma muat empat buku: mau taruh buku baru, buku yang paling lama gak kamu sentuh balik ke rak. Aturan ini dipakai di banyak cache berkapasitas tetap, misalnya cache browser dan Redis.
🧪 Tebakan cepat: cache muat 2 data. Kamu simpan 1, simpan 2, baca 1, lalu simpan 3. Mana yang dibuang, 1 atau 2? Jawabannya ada di bagian "Cara kerjanya: get dan put".
Cara kerjanya: get dan put
LRU cache punya dua operasi:
put(key, value)menyimpanvaluedengan namakey. Kalau cache sudah penuh, yang paling lama gak dipakai dibuang dulu.get(key)mengambil value milikkey. Kalau key-nya gak ada, hasilnya-1, penanda "gak ketemu".
Yang penting: get juga dihitung memakai. Key yang baru dibaca jadi yang paling baru.
const cache = new LRUCache(2); // muat 2 data (class-nya dibuat di bagian berikutnya)
cache.put(1, "A");
cache.put(2, "B");
cache.get(1); // "A", sekarang 1 yang paling baru dipakai
cache.put(3, "C"); // penuh: 2 dibuang, karena 2 paling lama gak dipakai
cache.get(2); // -1, 2 sudah gak ada
| Langkah | Isi cache (paling lama → paling baru) | Keterangan |
|---|---|---|
put(1, "A") |
1 | masih ada tempat |
put(2, "B") |
1, 2 | sekarang penuh |
get(1) → "A" |
2, 1 | 1 baru dipakai, pindah ke paling baru |
put(3, "C") |
1, 3 | penuh, 2 paling lama: dibuang |
get(2) → -1 |
1, 3 | 2 sudah gak ada |
Jadi jawaban tebakannya: 2, karena get(1) barusan memakai 1. Di Lab, cache-nya muat 4 dan key yang gak ada mengembalikan undefined; di latihan penandanya -1.
Membuatnya dengan Map
Map di JavaScript menyimpan pasangan key dan value, dan ingat urutan masuknya: key paling depan adalah yang paling lama masuk. Triknya: tiap kali sebuah key dipakai, hapus lalu set lagi, jadi key itu pindah ke paling belakang. Key paling depan otomatis jadi yang paling lama gak dipakai.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return -1;
const value = this.map.get(key);
this.map.delete(key); // hapus...
this.map.set(key, value); // ...lalu set lagi: pindah ke paling baru
return value;
}
put(key, value) {
if (this.map.has(key)) {
this.map.delete(key); // key lama: hapus dulu supaya jadi paling baru
} else if (this.map.size === this.capacity) {
const oldest = this.map.keys().next().value;
this.map.delete(oldest); // penuh: buang key paling depan
}
this.map.set(key, value);
}
}
deletelalusetmemindahkan key ke paling belakangMap, posisi "paling baru dipakai".getmelakukannya sebelum mengembalikan value.- Di
put, key yang sudah ada juga dihapus dulu, karena menimpa value dihitung memakai. Gak ada yang perlu dibuang. this.map.keys().next().valuemengambil key paling depan, yaitu yang paling lama gak dipakai:keys()memberi key satu per satu,next()mengambil yang pertama.
Kenapa cepat: hash map plus urutan
Cache harus cepat di dua hal: menemukan key, dan tahu mana yang paling lama.
- Hash map (seperti
Map) menemukan key dalam O(1), artinya waktunya tetap (rata-rata), mau isinya 10 atau 10.000. Tapi sendirian dia gak tahu urutan pakai. - Doubly linked list bisa menyimpan urutan pakai dan memindah atau membuang node dalam O(1), asal node-nya sudah dipegang. Tapi mencari key di dalamnya harus jalan satu per satu, O(n): datanya dua kali lipat, waktunya kira-kira dua kali lipat.
Makanya LRU cache klasik menggabungkan keduanya: hash map menunjuk langsung ke node di list, list menjaga urutannya, jadi get dan put sama-sama O(1). Map JavaScript kebetulan sudah mengingat urutan, jadi kode di atas cukup pendek.
⚠️ Jebakan yang sering ketemu
getgak memperbarui urutan. Cumathis.map.get(key)tanpa hapus lalu set bikin key yang sering dibaca tetap terlihat lama, lalu ikut dibuang.putkey lama gak memindah.setpada key yang sudah ada mengganti value-nya, tapi posisinya tetap di tempat lama. Hapus dulu, baru set.- Membuang padahal key-nya sudah ada. Kalau cache penuh dan key-nya cuma diperbarui, gak ada yang perlu dibuang. Cek
has(key)sebelum mengecek penuh. - Pakai object biasa. Key berupa angka di object selalu diurutkan dari kecil, bukan urutan masuk, jadi "yang paling lama" gak bisa diandalkan. Pakai
Map.
TL;DR: LRU cache punya kapasitas tetap dan, waktu penuh, membuang key yang paling lama gak dipakai. get dan put sama-sama dihitung memakai, jadi key-nya pindah ke paling baru. Dengan Map: hapus lalu set untuk memindah, map.keys().next().value untuk key paling lama, dan -1 untuk key yang gak ada. Hash map memberi pencarian O(1), doubly linked list memberi urutan O(1); Map JavaScript sudah punya keduanya.
