Rust中实现LRU

在Rust中实现LRU算法和其他语言中基本一样，代码如下。

use std::cell::RefCell;
use std::hash::{DefaultHasher, Hash, Hasher};
use std::rc::Rc;

struct Node<K, V> {
    key: K,
    value: V,
    hash_prev: Option<Rc<RefCell<Node<K, V>>>>,
    hash_next: Option<Rc<RefCell<Node<K, V>>>>,
    list_prev: Option<Rc<RefCell<Node<K, V>>>>,
    list_next: Option<Rc<RefCell<Node<K, V>>>>,
}

impl<K, V> Node<K, V> {
    fn new(key: K, value: V) -> Self {
        Self {
            key,
            value,
            hash_prev: None,
            hash_next: None,
            list_prev: None,
            list_next: None,
        }
    }
}

struct LRUCache<K, V, const H: usize = 128> {
    total: usize,
    max_size: usize,
    list_head: Option<Rc<RefCell<Node<K, V>>>>,
    list_tail: Option<Rc<RefCell<Node<K, V>>>>,
    hash_indices: [Option<Rc<RefCell<Node<K, V>>>>; H],
}

impl<K: Hash + PartialEq, V, const H: usize> LRUCache<K, V, H> {
    pub fn new(max_size: usize) -> Self {
        Self {
            total: 0,
            max_size,
            list_head: None,
            list_tail: None,
            hash_indices: [const { None }; H],
        }
    }

    pub fn get(&mut self, key: &K) -> Option<V>
    where
        V: Clone,
    {
        let node = self.find_by_hash(key)?;

        let value = node.borrow().value.clone();
        self.move_node_list_head(node);

        Some(value)
    }

    pub fn set(&mut self, key: K, value: V) {
        let node = self.find_by_hash(&key);
        if let Some(node) = node {
            node.borrow_mut().value = value;
            self.move_node_list_head(node);
        } else {
            let index = self.get_hash(&key);
            let node = Rc::new(RefCell::new(Node::new(key, value)));

            node.borrow_mut().list_next = self.list_head.clone();
            if let Some(list_head) = self.list_head.as_deref() {
                list_head.borrow_mut().list_prev = Some(node.clone());
            }
            self.list_head = Some(node.clone());

            let hash_head = self.hash_indices[index].clone();
            node.borrow_mut().hash_next = hash_head.clone();
            if let Some(hash_head) = hash_head.as_deref() {
                hash_head.borrow_mut().hash_prev = Some(node.clone());
            }
            self.hash_indices[index] = Some(node);

            if self.total >= self.max_size {
                self.delete_tail();
            } else {
                self.total += 1;
            }
        }
    }

    fn delete_tail(&mut self) {
        if let Some(list_tail) = self.list_tail.clone() {
            let list_prev = list_tail.borrow().list_prev.clone();
            if let Some(list_prev) = list_prev.clone() {
                list_prev.borrow_mut().list_next = None;
            }

            let hash_prev = list_tail.borrow().hash_prev.clone();
            let hash_next = list_tail.borrow().hash_next.clone();
            if let Some(hash_prev) = hash_prev.as_deref() {
                hash_prev.borrow_mut().hash_next = hash_next.clone();
            } else {
                let index = self.get_hash(&list_tail.borrow().key);
                self.hash_indices[index] = hash_next.clone();
            }
            if let Some(hash_next) = hash_next.as_deref() {
                hash_next.borrow_mut().hash_prev = hash_prev.clone();
            }

            self.list_tail = list_prev;
        }
    }

    fn move_node_list_head(&mut self, node: Rc<RefCell<Node<K, V>>>) {
        let prev = node.borrow().list_prev.clone();
        let next = node.borrow().list_next.clone();

        if let Some(prev) = prev.as_deref() {
            prev.borrow_mut().list_next = next.clone();
        }
        if let Some(next) = next.as_deref() {
            next.borrow_mut().list_prev = prev.clone();
        }

        node.borrow_mut().list_next = self.list_head.clone();
        node.borrow_mut().list_prev = None;
        self.list_head = Some(node);
    }

    fn find_by_hash(&self, k: &K) -> Option<Rc<RefCell<Node<K, V>>>> {
        let index = self.get_hash(k);
        let mut ptr = self.hash_indices[index].clone();

        while let Some(p) = ptr {
            if p.borrow().key == *k {
                return Some(p.clone());
            }
            ptr = p.borrow().hash_next.clone();
        }
        None
    }

    fn get_hash(&self, k: &K) -> usize {
        let mut hasher = DefaultHasher::new();
        k.hash(&mut hasher);
        hasher.finish() as usize % H
    }
}

编写测试代码：

fn main() {
    let mut cache: LRUCache<&str, &str> = LRUCache::new(100);
    cache.set("a", "apple");
    cache.set("b", "banana");

    if let Some(v) = cache.get(&"a") {
        println!("{}", v);
    }

    if let Some(v) = cache.get(&"b") {
        println!("{}", v);
    }

    println!("{:?}", cache.total);
}

测试一下，结果如下：

apple
banana
2

赏

非常感谢,我会继续努力的！

支付宝

微信

• 本文作者： killf
• 本文链接： https://www.killf.info/编程语言/Rust/Rust中实现LRU/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！