C++及Rust实现LRUCache

算法

LRU 缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
• 当插入时将节点插入靠近头部的位置,并存储到map中,如果到达容量上限则移除靠近链表尾部的节点同时在map中删除该键值对
• 当获取时返回节点值并将节点移动到靠近链表头部的位置

LRU缓存C++简单实现

// LRU缓存C++简单实现
#include <unordered_map>

/**节点类（构建双向链表）*/
class DLinkedNode {
	int key, value;
	DLinkedNode* prev;
	DLinkedNode* next;
	DLinkedNode(int key_, int value_) : key(key_), value(value_), prev(nullptr), next(nullptr) {}

	friend class LRUCache;
};

/**缓存类*/
class LRUCache {
public:
	LRUCache(int capacity_) :capacity(capacity_), size(0) {
		//为方便操作的伪头部
		head = new DLinkedNode(0, 0);
		//为方便操作的伪尾部
		tail = new DLinkedNode(0, 0);
		head->next = tail;
		tail->prev = head;
		//头尾都不实际加入cache中
	}

	~LRUCache() {
		delete head;
		delete tail;
	}

	int get(int key) {
		if (!cache.count(key)) {
			return -1;//key不存在
		}
		// 如果 key 存在，先通过哈希表定位，再移到头部
		DLinkedNode* node = cache[key];
		moveToHead(node);
		return node->value;
	}

	void put(int key, int value) {
		if (!cache.count(key)) {
			// 如果 key 不存在，创建一个新的节点
			DLinkedNode* node = new DLinkedNode(key, value);
			// 添加进哈希表
			cache[key] = node;
			// 添加至双向链表的头部
			addToHead(node);
			++size;
			if (size > capacity) {
				// 如果超出容量，删除双向链表的尾部节点
				DLinkedNode* removed = removeTail();
				// 删除哈希表中对应的项
				cache.erase(removed->key);
				// 删除对象
				delete removed;
				--size;
			}
		}
		else {
			// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
			DLinkedNode* node = cache[key];
			node->value = value;
			moveToHead(node);
		}
	}

private:
	std::unordered_map<int, DLinkedNode*> cache;
	DLinkedNode* head;
	DLinkedNode* tail;
	int size, capacity;

	void addToHead(DLinkedNode* node) {
		node->prev = head;
		node->next = head->next;
		head->next->prev = node;
		head->next = node;
	}

	void removeNode(DLinkedNode* node) {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}

	void moveToHead(DLinkedNode* node) {
		removeNode(node);
		addToHead(node);
	}

	DLinkedNode* removeTail() {
		DLinkedNode* node = tail->prev;
		removeNode(node);
		return node;
	}
};

LRU缓存Rust简单实现

//LRU缓存Rust简单实现
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

struct Node {
    key: i32, value: i32,
    prev: Option<Rc<RefCell<Node>>>,
    next: Option<Rc<RefCell<Node>>>
}

impl Node {
    fn new(key: i32, value: i32) -> Self {
        Node {
            key, value,
            prev: None, next: None
        }
    }
}

struct LRUCache {
    //hash缓存，便于查找
    cache: HashMap<i32,Rc<RefCell<Node>>>,
    //伪头尾，便于操作节点时不用关心其前后节点是否存在
    head: Rc<RefCell<Node>>, tail: Rc<RefCell<Node>>,
    //大小<=容量
    size: usize, capacity: usize
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        let capacity = match capacity < 1 {
            true => 1 as usize,
            false => capacity as usize
        };
        let head = Rc::from(RefCell::from(Node::new(-1,-1)));
        let tail = Rc::new(RefCell::new(Node::new(-2,-2)));
        head.borrow_mut().next = Option::from(tail.clone());
        tail.borrow_mut().prev = Some(head.clone());
        Self {
            cache: HashMap::with_capacity(capacity),
            head, tail,
            size: 0 as usize, capacity,
        }
    }

    ///以key获取value
    fn get(&mut self, key: i32) -> i32 {
        if let Some(node_ref) = self.cache.get(&key) {
            self.move_to_head(node_ref);
            return node_ref.borrow().value;
        }
        -1
    }

    ///插入key-value
    fn put(&mut self, key: i32, value: i32) {
        match self.cache.get(&key) {
            // 如果 key 不存在，创建一个新的节点
            None => {
                //到达容量上限，则先清除最老的数据
                if self.size == self.capacity {
                    self.size -= 1;
                    if let Some(node) = self.remove_tail() {
                        self.cache.remove(&node.borrow().key);
                    }
                }
                self.size += 1;
                let node = Rc::new(RefCell::new(Node::new(key,value)));
                self.cache.insert(key,node.clone());
                self.move_to_head(&node);
            }
            // 存在则移动到头部并改写其值
            Some(node_ref) => {
                node_ref.borrow_mut().value = value;
                self.move_to_head(node_ref);
            }
        }
    }

    fn move_to_head(&self, node: &Rc<RefCell<Node>>){
        Self::remove_node(node);
        self.add_to_head(node);
    }

    ///将节点添加到头部
    fn add_to_head(&self, node: &Rc<RefCell<Node>>) {
        //当前节点的prev指向head
        node.borrow_mut().prev.replace(self.head.clone());
        //原头部节点
        if let Some(head_next_ref) = &self.head.borrow().next {
            //当前节点的next指向head的next，完成自身移动到头部
            node.borrow_mut().next.replace(head_next_ref.clone());
            //原来头节点next的prev指向当前节点
            head_next_ref.borrow_mut().prev.replace(node.clone());
        }
        //原来头节点的next指向将当前节点，完成原来的头部后移为第二位
        self.head.borrow_mut().next.replace(node.clone());
    }

    ///从链表中删除尾节点，并返回该节点
    fn remove_tail(&mut self) -> Option<Rc<RefCell<Node>>> {
        if let Some(node) = &self.tail.borrow().prev {
            let node = Self::remove_node(&node);
            return Some(node.clone());
        }
        None
    }

    ///由于需要同时持有node的可变借用,使用unsafe
    unsafe fn remove_node_unsafe(node: &Rc<RefCell<Node>>) -> Rc<RefCell<Node>>{
        if let Some(prev) = &node.borrow().prev {
            if let Some(next) = &node.borrow().next {
                //将前一节点的后置节点指向当前节点的后置节点
                prev.borrow_mut().next.replace(next.clone());
                //预先克隆并返回克隆值,避免返回当前节点处在尾部时下一步操作将其内部Node改变为操作后的尾部
                let node = node.clone();
                //将后一节点的前置节点指向当前节点的前置节点,当移除最老节点时这个操作对于tail而言改变了尾部节点
                (*next.as_ptr()).prev = Some(prev.clone());//这里的裸指针就是使用usafe的原因(next.borrow_mut()将报错:already borrowed: BorrowMutError)
                //(*node.as_ptr()).prev = None;
                //(*node.as_ptr()).next = None;
                return node;
            }
        }
        node.clone()
    }

    //将节点从链表中移除
    fn remove_node(node: &Rc<RefCell<Node>>)  -> Rc<RefCell<Node>>{
        unsafe {
            return Self::remove_node_unsafe(node);
        }

    }
}

///测试
fn main() {
    let mut cache = LRUCache::new(2);
    cache.put(1,11);
    cache.put(2,22);
    println!("get 1 {}  1",cache.get(1));
    cache.put(3,33);
    println!("get 2 {}  -1",cache.get(2));
    cache.put(4,44);
    cache.put(3,333);
    println!("get 1 {}  -1",cache.get(1));
    println!("get 3 {}  3",cache.get(3));
    println!("get 4 {}  4",cache.get(4));
}
/*
get 1 11  1
get 2 -1  -1
get 1 -1  -1
get 3 333  3
get 4 44  4
*/

C++循环链表实现

// LRU缓存C++简单实现(循环链表+哈希表)
#include <unordered_map>

/**节点类（构建循环双向链表）*/
class DLinkedNode {
	int key, value;
	DLinkedNode* prev;
	DLinkedNode* next;
	DLinkedNode(int key_, int value_) : key(key_), value(value_), prev(nullptr), next(nullptr) {}

	friend class LRUCache;
};

/**缓存类*/
class LRUCache {
public:
	LRUCache(int capacity_) :capacity(capacity_), size(0) {
		//初始化标记节点,也可以直接用put的首节点做标记节点,代价是每次put都要判空
		mark = new DLinkedNode(0, 0);
		mark->next = mark;
		mark->prev = mark;
		//初始化标记不实际加入cache中
	}

	~LRUCache() {
		delete mark;
	}

	int get(int key) {
		if (!cache.count(key)) {
			return -1;//key不存在
		}
		// 如果 key 存在，先通过哈希表定位，再移到头部
		DLinkedNode* node = cache[key];
		moveToHead(node);
		return node->value;
	}

	void put(int key, int value) {
		if (!cache.count(key)) {
			removeTailBeforePut();
			// 如果 key 不存在，创建一个新的节点
			DLinkedNode* node = new DLinkedNode(key, value);
			// 添加进哈希表
			cache[key] = node;
			// 添加至双向链表的头部
			addToHead(node);
			++size;
		}
		else {
			// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
			DLinkedNode* node = cache[key];
			node->value = value;
			moveToHead(node);
		}
	}

private:
	std::unordered_map<int, DLinkedNode*> cache;
	//标记节点,他的next是首节点,prev是尾节点
	DLinkedNode* mark;
	int size, capacity;

	void removeTailBeforePut() {
		if (size >= capacity) {
			// 如果超出容量，删除双向链表的尾部节点
			DLinkedNode* removed = removeTail();
			// 删除哈希表中对应的项
			cache.erase(removed->key);
			// 删除对象
			delete removed;
			--size;
			removeTailBeforePut();
		}
	}

	void addToHead(DLinkedNode* node) {
		DLinkedNode* lastHead = mark->next;
		node->prev = mark;
		node->next = lastHead;
		mark->next->prev = node;
		mark->next = node;
	}

	void removeNode(DLinkedNode* node) {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}

	void moveToHead(DLinkedNode* node) {
		removeNode(node);
		addToHead(node);
	}

	DLinkedNode* removeTail() {
		DLinkedNode* node = mark->prev;
		removeNode(node);
		return node;
	}
};

Rust循环链表实现

// LRU缓存Rust简单实现(循环链表+哈希表)
use std::collections::HashMap;
use std::rc::Rc;
use std::rc::Weak;
use std::cell::RefCell;

struct ListNode {
    key: i32,
    val: i32,
    prev: Option<Weak<RefCell<ListNode>>>,//弱引用以避免使用unsafe
    next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {

    #[inline]
    fn new(key:i32, val: i32) -> Self {
        ListNode{
            key,val,
            prev: None,
            next: None,
        }
    }

    #[inline]
    fn new_rc(key:i32, val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self::new(key,val)))
    }

    fn insert_after(node: Rc<RefCell<Self>>, head: Rc<RefCell<Self>>) {
        let mut next = head.borrow_mut().next.take();
        next.as_mut().unwrap().borrow_mut().prev = Some(Rc::downgrade(&node));
        node.borrow_mut().next = next;
        node.borrow_mut().prev = Some(Rc::downgrade(&head));
        head.borrow_mut().next = Some(node);
    }

    fn pop(node: Rc<RefCell<Self>>) -> Rc<RefCell<Self>> {
        let next = node.borrow_mut().next.take().unwrap();
        let prev = node.borrow_mut().prev.as_ref().unwrap().upgrade().unwrap();
        prev.borrow_mut().next = Some(Rc::clone(&next));
        next.borrow_mut().prev = Some(Rc::downgrade(&prev));
        node.borrow_mut().prev = None;
        node
    }

}

struct LRUCache {
    map: HashMap<i32, Rc<RefCell<ListNode>>>,
    //标记节点,他的next是首节点,prev是尾节点
    mark: Rc<RefCell<ListNode>>,
    capacity: usize,
}

impl LRUCache {

    fn new(capacity: i32) -> Self {
        let capacity= match capacity.le(&0) {
            true => 1 as usize,
            false => capacity as usize
        };
        let mark = ListNode::new_rc(0, 0);
        mark.borrow_mut().next = Some(Rc::clone(&mark));
        mark.borrow_mut().prev = Some(Rc::downgrade(&mark));

        LRUCache {map: HashMap::with_capacity(capacity),mark,capacity}
    }

    #[inline]
    fn get(&self, key: i32) -> i32 {
        self.get_node(key).0
    }

    fn get_node(&self, key: i32) -> (i32, Option<Rc<RefCell<ListNode>>>) {
        match self.map.get(&key) {
            None => {
                (-1, None)
            }
            Some(x) => {
                let node_rc = ListNode::pop(Rc::clone(x));
                let ret = node_rc.borrow().val;
                let ret_node = Some(Rc::clone(&node_rc));
                self.insert_after_head(node_rc);
                (ret, ret_node)
            }
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        let (ret, ret_node) = self.get_node(key);
        if  ret != -1 {
            ret_node.unwrap().borrow_mut().val = value;
        } else{
            self.rm_surplus_tail_before_put();
            let new = ListNode::new_rc(key, value);
            self.map.insert(key, new.clone());
            self.insert_after_head(new);
        }
    }

    #[inline]
    fn insert_after_head(&self,new: Rc<RefCell<ListNode>>) {
        ListNode::insert_after(new, Rc::clone(&self.mark));
    }

    fn rm_surplus_tail_before_put(&mut self) {
        if self.map.len().ge(&(self.capacity as usize)) {
            let to_rm = Rc::clone(&self.mark.as_ref().borrow().prev.as_ref().unwrap().upgrade().unwrap());
            let to_rm = ListNode::pop(to_rm);
            self.map.remove(&to_rm.borrow().key);
            self.rm_surplus_tail_before_put();
        }
    }
}