146. LRU Cache
Description of the Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of the key if thekeyexists, otherwise return-1.void put(int key, int value)Update the value of thekeyif the key exists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5- At most
2 * 10^5calls will be made togetandput.
Solution 1 - Simple Idea (Does not meet the requirement)
Explanation
The whole idea is provided by NeetCode's Video:
Double-ended queuestores key-value pairs where the head is the least recently used (LRU) element and the tail is the most recently used (MRU) element.HashMapstores the pointer of nodes of the deque.HashMapprovides constant time insert and query on average.
The following code is just a simplified version of his solution which does not meet the requirement of the problem (The functions get and put must each run in O(1) average time complexity). However, once we implmment double-end queue, the following code can be easily modified in order to meet the requirement.
Code (Rust)
use std::collections::{HashMap, VecDeque};
struct LRUCache{
capacity : usize,
hash_map : HashMap<i32, i32>,
deque : VecDeque<i32>,
}
impl LRUCache {
fn new(capacity: i32) -> LRUCache {
return LRUCache {
capacity : capacity.try_into().unwrap(),
hash_map: HashMap::new(),
deque: VecDeque::new()
};
}
fn get(&mut self, key : i32) -> i32 {
if let Some(&value) = self.hash_map.get(&key) {
self.move_into_back(key);
return value;
}
return -1;
}
fn put(&mut self, key : i32, value: i32) {
if let Some(value_ref) = self.hash_map.get_mut(&key) {
*value_ref = value;
self.move_into_back(key);
return;
}
if self.deque.len() >= self.capacity {
let lru_key = self.deque.pop_front();
if let Some(lru_key) = lru_key {
self.hash_map.remove(&lru_key);
}
}
self.hash_map.insert(key.clone(), value.clone());
self.deque.push_back(key);
}
fn move_into_back(&mut self, key : i32){
let i = self.deque.iter().position(|&x| x == key).unwrap();
self.deque.remove(i);
self.deque.push_back(key);
}
}
Solution 2
Explanation
It is so difficult to implement Safe LinkedList with Rust.
Fortunately, Learn Rust With Entirely Too Many Linked Lists provides good demostration for the implementation of a safe LinkedList (see: A Bad Safe Deque)
The source code of std::collections::LinkedList also provides a very good demostration for LinkedList.
Remember to use Unit Test when implementing these data strctures, it helps you DEBUG :).
Code (Rust)
** For implmentation details of double-end queue, please see Apppendix A1
struct LRUCache {
cache : base::LRUCache<i32, i32>,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
LRUCache {
cache : base::LRUCache::new(capacity as usize)
}
}
fn get(&mut self, key: i32) -> i32 {
self.cache.get(&key).unwrap_or(-1)
}
fn put(&mut self, key: i32, value: i32) {
self.cache.put(key, value);
}
}
mod base {
// -- Snip --
// Please see Appendix A1
}
Complexity
Time Complexity
- get: \(O(1)\)
- put: \(O(1)\)
Auxiliary Space
- get: \(O(1)\)
- put: \(O(1)\)
Appendix A1 - Implementation Details of LRUCache using Safe Deque
//! # Least Recently Used Cache
//! A LRU cache supports Generics with trait bounds.
use std::{hash::Hash, collections::HashMap, cell::RefCell, rc::Rc};
type NodeRef<T> = Rc<RefCell<Node<T>>>;
/// `K` must be `Copy` to remind "callers" that the `K` should be small
/// Otherwise it will be expensive to copy the key.
pub struct LRUCache<K, V>
where
K: Copy + Eq + Hash,
V: Clone
{
capacity: usize,
hash_map: HashMap<K, NodeRef<(K,V)>>,
deque: Deque<(K,V)>,
}
/// The idea of the implementation of this deque mostly comes from the **Learn Rust With Entirely Too Many Linked Lists**
/// see: [A Bad but Safe Doubly-Linked Deque](https://rust-unofficial.github.io/too-many-lists/fourth-final.html)
/// The idea of `unsafe fn unlink_node(&mut self, node: &NodeRef<T>)` comes from the offcial implementation of `std::collections::LinkedList`
struct Deque<T> {
len: usize,
front: Option<NodeRef<T>>,
back: Option<NodeRef<T>>,
}
#[derive(Debug)]
struct Node<T> {
val: T,
prev: Option<NodeRef<T>>,
next: Option<NodeRef<T>>,
}
impl<K, V> LRUCache<K, V>
where
K: Copy + Eq + Hash,
V: Clone
{
pub fn new(capacity: usize) -> Self {
LRUCache {
capacity,
hash_map: HashMap::new(),
deque: Deque::new(),
}
}
pub fn get(&mut self, key: &K) -> Option<V> {
self.hash_map.get_mut(key).map(|node_ref| {
unsafe { self.deque.move_node_into_back(node_ref) };
node_ref.borrow().val.1.clone()
})
}
pub fn put(&mut self, key: K, value: V) {
if let Some(node_ref) = self.hash_map.get_mut(&key) {
unsafe { self.deque.move_node_into_back(node_ref) };
node_ref.borrow_mut().val.1 = value;
return;
}
if self.hash_map.len() >= self.capacity {
let old_node = self.deque.pop_front_node().unwrap();
let old_key = &old_node.borrow().val.0;
self.hash_map.remove(old_key);
}
let node_ref = Deque::create_node_ref((key, value));
self.hash_map.insert(key, node_ref.clone());
unsafe { self.deque.push_back_node(node_ref) };
}
}
impl<T> Deque<T> {
/* "Public" Interfaces */
fn new() -> Self {
Deque {
len: 0,
front: None,
back: None,
}
}
#[allow(dead_code)]
fn push_front(&mut self, val: T) {
let new_front = Self::create_node_ref(val);
// Safety: `new_front` is newly created
unsafe { self.push_front_node(new_front) };
}
#[allow(dead_code)]
fn push_back(&mut self, val: T) {
let new_back = Self::create_node_ref(val);
// Safety: `new_back` is newly created
unsafe { self.push_back_node(new_back) };
}
#[allow(dead_code)]
fn pop_front(&mut self) -> Option<T> {
self.pop_front_node()
.map(|old_front| Rc::try_unwrap(old_front).ok().unwrap().into_inner().val)
}
#[allow(dead_code)]
fn pop_back(&mut self) -> Option<T> {
self.pop_back_node()
.map(|old_back| Rc::try_unwrap(old_back).ok().unwrap().into_inner().val)
}
/* "Private" Auxiliary Functions */
/// # Safety
/// The node must have only one strong reference.
/// It cause problem when the node is popped later otherwise
#[allow(dead_code)]
unsafe fn push_front_node(&mut self, new_front: NodeRef<T>) {
match self.front.take() {
Some(old_front) => {
old_front.borrow_mut().prev = Some(new_front.clone());
new_front.borrow_mut().next = Some(old_front);
new_front.borrow_mut().prev = None;
self.front = Some(new_front);
},
None => {
self.front = Some(new_front.clone());
self.back = Some(new_front);
}
}
self.len += 1;
}
/// # Safety
/// The node must have only one strong reference.
/// It cause problem when the node is popped later otherwise
unsafe fn push_back_node(&mut self, new_back: NodeRef<T>) {
match self.back.take() {
Some(old_back) => {
old_back.borrow_mut().next = Some(new_back.clone());
new_back.borrow_mut().prev = Some(old_back);
new_back.borrow_mut().next = None;
self.back = Some(new_back);
},
None => {
self.back = Some(new_back.clone());
self.front = Some(new_back);
}
}
self.len += 1;
}
fn pop_front_node(&mut self) -> Option<NodeRef<T>> {
self.front.take().map(|old_front| {
match old_front.borrow_mut().next.take() {
Some(new_front) => {
new_front.borrow_mut().prev = None;
self.front = Some(new_front);
},
None => {
self.back = None;
}
}
self.len -= 1;
old_front
})
}
#[allow(dead_code)]
fn pop_back_node(&mut self) -> Option<NodeRef<T>> {
self.back.take().map(|old_back| {
match old_back.borrow_mut().prev.take() {
Some(new_back) => {
new_back.borrow_mut().next = None;
self.back = Some(new_back);
},
None => {
self.front = None;
}
}
self.len -= 1;
old_back
})
}
/// # Safety
/// see reason from the below method
unsafe fn move_node_into_back(&mut self, node: &NodeRef<T>) {
unsafe { self.unlink_node(node) };
self.push_back_node(node.clone());
}
/// # Safety
/// Warning: it does not check whether `node` belongs to the lists.
unsafe fn unlink_node(&mut self, node: &NodeRef<T>) {
let prev = node.borrow_mut().prev.take();
let next = node.borrow_mut().next.take();
if let Some(ref prev) = prev {
prev.borrow_mut().next = next.clone();
} else {
self.front = next.clone();
}
if let Some(ref next) = next {
next.borrow_mut().prev = prev;
} else {
self.back = prev;
}
self.len -= 1;
}
fn create_node_ref(val : T) -> NodeRef<T> {
Rc::new(RefCell::new(Node::new(val)))
}
}
impl<T> Node<T> {
fn new(val: T) -> Self {
Node { val, prev: None, next: None }
}
}
#[cfg(test)]
mod cache_tests{
use crate::LRUCache;
#[test]
fn test_01(){
let mut cache = LRUCache::new(2);
cache.put(1,1);
cache.put(2,2);
assert_eq!(cache.get(&1),Some(1));
cache.put(3,3);
assert_eq!(cache.get(&2),None);
cache.put(4,4);
assert_eq!(cache.get(&1),None);
assert_eq!(cache.get(&3),Some(3));
assert_eq!(cache.get(&4),Some(4));
}
#[test]
fn test_02(){
let mut cache = LRUCache::new(2);
cache.put(1,1);
cache.put(2,2);
assert_eq!(cache.get(&1),Some(1));
cache.put(2,3);
assert_eq!(cache.get(&2),Some(3));
cache.put(2,3);
}
}
#[cfg(test)]
mod deque_tests {
use crate::Deque;
#[test]
fn pop_front_test(){
let mut deque = Deque::<i32>::new();
deque.push_front(3);
deque.push_front(2);
deque.push_front(1);
deque.push_back(4);
deque.push_back(5);
deque.push_back(6);
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_front(), Some(2));
assert_eq!(deque.pop_front(), Some(3));
assert_eq!(deque.pop_front(), Some(4));
assert_eq!(deque.pop_front(), Some(5));
assert_eq!(deque.pop_front(), Some(6));
}
// Pop Back Test
#[test]
fn pop_back_test(){
let mut deque = Deque::<i32>::new();
deque.push_front(3);
deque.push_front(2);
deque.push_front(1);
deque.push_back(4);
deque.push_back(5);
deque.push_back(6);
assert_eq!(deque.pop_back(), Some(6));
assert_eq!(deque.pop_back(), Some(5));
assert_eq!(deque.pop_back(), Some(4));
assert_eq!(deque.pop_back(), Some(3));
assert_eq!(deque.pop_back(), Some(2));
assert_eq!(deque.pop_back(), Some(1));
}
// Push Test
#[test]
fn push_test(){
let mut deque = Deque::<i32>::new();
deque.push_front(3);
deque.push_front(2);
deque.push_front(1);
deque.push_back(4);
deque.push_back(5);
deque.push_back(6);
let mut front = deque.front.clone();
for i in 1..=6 {
if let Some(node) = front.clone() {
let val = node.borrow().val;
assert_eq!(val, i);
} else{
panic!("There should be an element in the list");
}
front = front.and_then(
|rc| {
let rc = rc.borrow();
let rc = rc.next.clone();
rc
}
);
}
let mut back = deque.back.clone();
for i in (1..=6).rev() {
if let Some(node) = back.clone() {
let val = node.borrow().val;
assert_eq!(val, i);
} else{
panic!("There should be an element in the list");
}
back = back.and_then(
|rc| {
let rc = rc.borrow();
let rc = rc.prev.clone();
rc
}
);
}
}
// unlink test
#[test]
fn unlink_test(){
unsafe {
let mut deque = Deque::<i32>::new();
let node_6 = Deque::create_node_ref(6);
let node_5 = Deque::create_node_ref(5);
let node_4 = Deque::create_node_ref(4);
let node_3 = Deque::create_node_ref(3);
let node_2 = Deque::create_node_ref(2);
let node_1 = Deque::create_node_ref(1);
deque.push_front_node(node_3.clone());
deque.push_front_node(node_2);
deque.push_front_node(node_1);
deque.push_back_node(node_4);
deque.push_back_node(node_5);
deque.push_back_node(node_6);
deque.unlink_node(&node_3);
for i in &[1,2,4,5,6] {
let i = *i;
let j = deque.pop_front().unwrap();
assert_eq!(i, j);
}
}
}
}
Appendix A2 - Implementation of LRUCache using std::collections::linked_list::LinkedList
//! # Least Recently Used Cache
//! Using unsafe `LinkedList` from std::collections::linked_list
use std::{collections::HashMap, hash::Hash, marker::PhantomData, ptr::NonNull};
type NodePtr<T> = NonNull<Node<T>>;
pub struct LRUCache<K, V>
where
K: Copy + Eq + Hash,
V: Clone
{
capacity: usize,
hash_map: HashMap<K, NodePtr<(K,V)>>,
deque: LinkedList<(K,V)>,
}
struct LinkedList<T> {
len: usize,
front: Option<NodePtr<T>>,
back: Option<NodePtr<T>>,
_marker: PhantomData<Box<Node<T>>>,
}
#[derive(Debug)]
struct Node<T> {
val: T,
prev: Option<NodePtr<T>>,
next: Option<NodePtr<T>>,
}
impl<K, V> LRUCache<K, V>
where
K: Copy + Eq + Hash,
V: Clone
{
pub fn new(capacity: usize) -> Self {
LRUCache {
capacity,
hash_map: HashMap::new(),
deque: LinkedList::new()
}
}
pub fn get(&mut self, key: &K) -> Option<V> {
self.hash_map.get_mut(key).map(|node_ptr| unsafe {
self.deque.move_node_into_back(*node_ptr);
(*node_ptr.as_ptr()).val.1.clone()
})
}
pub fn put(&mut self, key: K, value: V) {
if let Some(node_ptr) = self.hash_map.get_mut(&key) {
unsafe {
self.deque.move_node_into_back(*node_ptr);
(*node_ptr.as_ptr()).val.1 = value;
return;
}
}
if self.hash_map.len() >= self.capacity {
let old_node = self.deque.pop_front_node().unwrap();
let old_key = (*old_node).val.0;
self.hash_map.remove(&old_key);
}
let node_ptr = LinkedList::create_node_ptr((key, value));
self.hash_map.insert(key, node_ptr.clone());
unsafe { self.deque.push_back_node(node_ptr) };
}
}
// The implementation is copied and modified from `std::collections::linked_list`
impl<T> LinkedList<T> {
fn new() -> Self {
LinkedList {
len: 0,
front: None,
back: None,
_marker: PhantomData,
}
}
#[allow(unused)]
unsafe fn push_front_node(&mut self, node: NonNull<Node<T>>) {
unsafe {
(*node.as_ptr()).next = self.front;
(*node.as_ptr()).prev = None;
let node = Some(node);
match self.front {
None => self.back = node,
Some(front) => (*front.as_ptr()).prev = node,
}
self.front = node;
self.len += 1;
}
}
#[allow(unused)]
unsafe fn push_back_node(&mut self, node: NonNull<Node<T>>) {
unsafe {
(*node.as_ptr()).next = None;
(*node.as_ptr()).prev = self.back;
let node = Some(node);
match self.back {
None => self.front = node,
Some(back) => (*back.as_ptr()).next = node,
}
self.back = node;
self.len += 1;
}
}
fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
self.front.map(|node| unsafe {
let node = Box::from_raw(node.as_ptr());
self.front = node.next;
match self.front {
None => self.back = None,
Some(front) => (*front.as_ptr()).prev = None,
}
self.len -= 1;
node
})
}
#[allow(unused)]
fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
self.back.map(|node| unsafe {
let node = Box::from_raw(node.as_ptr());
self.back = node.prev;
match self.back {
None => self.front = None,
Some(back) => (*back.as_ptr()).next = None,
}
self.len -= 1;
node
})
}
/// # Safety
/// see reason from the below method
unsafe fn move_node_into_back(&mut self, node: NodePtr<T>) {
unsafe { self.unlink_node(node) };
self.push_back_node(node.clone());
}
unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
let node = unsafe { node.as_mut() };
match node.prev {
Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
None => self.front = node.next,
};
match node.next {
Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
None => self.back = node.prev,
};
self.len -= 1;
}
fn create_node_ptr(val: T) -> NodePtr<T> {
let node = Box::leak(Box::new(Node::new(val)));
NonNull::new(node).unwrap()
}
}
impl<T> Node<T> {
fn new(val: T) -> Self {
Node { val, prev: None, next: None }
}
}
#[cfg(test)]
mod cache_tests{
use crate::LRUCache;
#[test]
fn test_01(){
let mut cache = LRUCache::new(2);
cache.put(1,1);
cache.put(2,2);
assert_eq!(cache.get(&1),Some(1));
cache.put(3,3);
assert_eq!(cache.get(&2),None);
cache.put(4,4);
assert_eq!(cache.get(&1),None);
assert_eq!(cache.get(&3),Some(3));
assert_eq!(cache.get(&4),Some(4));
}
#[test]
fn test_02(){
let mut cache = LRUCache::new(2);
cache.put(1,1);
cache.put(2,2);
assert_eq!(cache.get(&1),Some(1));
cache.put(2,3);
assert_eq!(cache.get(&2),Some(3));
cache.put(2,3);
}
}