Thiết kế LRU Cache với get/put O(1) — vì sao cần kết hợp HashMap và doubly linked list?

Ý tưởng: Cần hai khả năng O

1. cùng lúc:
2. tra cứu key
3. biết & dời phần tử "vừa dùng" và loại phần tử "lâu nhất chưa dùng". - HashMap key → node: tra cứu O(1). - Doubly linked list xếp theo thứ tự dùng: đầu = mới nhất, đuôi = cũ nhất. Có con trỏ trước/sau nên tách & chèn node bất kỳ trong O(1)

Mỗi get/put đẩy node lên đầu. Khi đầy, xóa node ở đuôi. Dùng dummy head/tail để khỏi xử lý biên.

class LRUCache {
  private map = new Map<number, number>() // Map JS giữ thứ tự chèn → mô phỏng LRU
  constructor(private capacity: number) {}
  get(key: number): number {
    if (!this.map.has(key)) return -1
    const val = this.map.get(key)!
    this.map.delete(key); this.map.set(key, val) // chuyển xuống cuối = mới dùng
    return val
  }
  put(key: number, value: number): void {
    if (this.map.has(key)) this.map.delete(key)
    else if (this.map.size >= this.capacity)
      this.map.delete(this.map.keys().next().value!) // xóa key cũ nhất
    this.map.set(key, value)
  }
}

Độ phức tạp: get/put O(1) thời gian, O(capacity) bộ nhớ.

Lưu ý: Phỏng vấn thường muốn bạn tự cài doubly linked list + HashMap để chứng tỏ hiểu cơ chế O(1); bản trên lợi dụng Map của JS giữ thứ tự chèn — gọn nhưng nên nói rõ trade-off khi được hỏi.