LRU-K 是一种缓存淘汰算法，旨在改进传统的LRU（Least Recently Used，最近最少使用）算法的性能。将其中高频的数据达到K次访问移入到另一个队列进行保护。
K次队列中。普通队列中。普通队列中的页面满了，根据一定的缓存策略（如FIFO、LRU、LFU）进行淘汰。K次队列中。K次队列中的页面再次被访问时，会重新排序。普通队列，因此内存消耗会比LRU多。综上所述，LRU-K通过引入“最近使用过K次”的判断标准，有效地解决了LRU算法中的“缓存污染”问题，提高了缓存的命中率。然而，它也需要更多的内存和CPU资源来维护历史队列和进行排序操作。
与Lru的结构类似，K与V均用指针方式保存，避免在使用过程中出现Copy或者Clone的可能，提高性能。
注:该方法用了指针会相应的出现许多unsafe的代码，因为在Rsut中，访问指针都被认为是unsafe。我们也可以使用数组坐标模拟指针的方式来模拟。
相对普通的Lru节点，我们需要额外存储次数数据。
/// LruK节点数据
struct LruKEntry<K, V> {
pub key: mem::MaybeUninit<K>,
pub val: mem::MaybeUninit<V>,
pub times: usize,
pub prev: *mut LruKEntry<K, V>,
pub next: *mut LruKEntry<K, V>,
}
由于有K次的列表，所以需要维护两个列表，在空间占用上会比Lru多一些，主要多一个字段访问次数的维护
pub struct LruKCache<K, V, S> {
map: HashMap<KeyRef<K>, NonNull<LruKEntry<K, V>>, S>,
cap: usize,
/// 触发K次数，默认为2
times: usize,
/// K次的队列
head_times: *mut LruKEntry<K, V>,
tail_times: *mut LruKEntry<K, V>,
/// 普通队列
head: *mut LruKEntry<K, V>,
tail: *mut LruKEntry<K, V>,
/// 普通队列的长度
lru_count: usize,
}
首先初始化对象，初始化map及空的双向链表：
impl<K, V, S> LruCache<K, V, S> {
/// 提供hash函数
pub fn with_hasher(cap: usize, times: usize, hash_builder: S) -> LruKCache<K, V, S> {
let cap = cap.max(1);
let map = HashMap::with_capacity_and_hasher(cap, hash_builder);
let head = Box::into_raw(Box::new(LruKEntry::new_empty()));
let tail = Box::into_raw(Box::new(LruKEntry::new_empty()));
unsafe {
(*head).next = tail;
(*tail).prev = head;
}
let head_times = Box::into_raw(Box::new(LruKEntry::new_empty()));
let tail_times = Box::into_raw(Box::new(LruKEntry::new_empty()));
unsafe {
(*head_times).next = tail_times;
(*tail_times).prev = head_times;
}
Self {
map,
cap,
times,
head_times,
tail_times,
head,
tail,
lru_count: 0,
}
}
}
插入对象，分已在缓存内和不在缓存内：
pub fn capture_insert(&mut self, k: K, mut v: V) -> Option<(K, V, bool)> {
let key = KeyRef::new(&k);
match self.map.get_mut(&key) {
Some(entry) => {
let entry_ptr = entry.as_ptr();
unsafe {
mem::swap(&mut *(*entry_ptr).val.as_mut_ptr(), &mut v);
}
self.detach(entry_ptr);
self.attach(entry_ptr);
Some((k, v, true))
}
None => {
let (val, entry) = self.replace_or_create_node(k, v);
let entry_ptr = entry.as_ptr();
self.attach(entry_ptr);
unsafe {
self.map
.insert(KeyRef::new((*entry_ptr).key.as_ptr()), entry);
}
val.map(|(k, v)| (k, v, false))
}
}
}
pub fn remove<Q>(&mut self, k: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
match self.map.remove(KeyWrapper::from_ref(k)) {
Some(l) => unsafe {
self.detach(l.as_ptr());
let node = *Box::from_raw(l.as_ptr());
Some((node.key.assume_init(), node.val.assume_init()))
},
None => None,
}
}
与Lru的操作方式类似，但是主要集中在attach及detach因为有两个队列，需要正确的附着在正确的队列之上。
/// 加到队列中
fn attach(&mut self, entry: *mut LruKEntry<K, V>) {
unsafe {
(*entry).times = (*entry).times.saturating_add(1);
if (*entry).times < self.times {
self.lru_count += 1;
(*entry).next = (*self.head).next;
(*(*entry).next).prev = entry;
(*entry).prev = self.head;
(*self.head).next = entry;
} else {
(*entry).next = (*self.head_times).next;
(*(*entry).next).prev = entry;
(*entry).prev = self.head_times;
(*self.head_times).next = entry;
}
}
}
在加入到队列的时候，需将访问次数+1，然后判断是否达到K次的次数，如果达到将其加入到head_times队列中。
其中使用了saturating_add，这里说个Rust与其它语言的差别。
因为在Rust中不像c语言，如果在c语言中，定义一个uchar类型
uchar times = 255;
times += 1; //此时times为0，不会有任何异常
但是在Rust中
let mut times: u8 = 255;
times = times.overflowing_add(1); // 此时times为0，因为上溢出了
times = times.saturating_add(1); // 此时times为255，因为达到了最大值
times += 1; // 此时将会发生panic
此时这函数的效率基本上等同于Lru的，相对仅仅是多维护times字段及lru_count字段。
fn detach(&mut self, entry: *mut LruKEntry<K, V>) {
unsafe {
(*(*entry).prev).next = (*entry).next;
(*(*entry).next).prev = (*entry).prev;
if (*entry).times < self.times {
self.lru_count -= 1;
}
}
}
与Lru中的类似，仅仅如果次数在k次以下的时候维护lru_count，效率基本一致。
fn replace_or_create_node(&mut self, k: K, v: V) -> (Option<(K, V)>, NonNull<LruKEntry<K, V>>) {
if self.len() == self.cap {
let old_key = if self.lru_count > 0 {
KeyRef {
k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
}
} else {
KeyRef {
k: unsafe { &(*(*(*self.tail_times).prev).key.as_ptr()) },
}
};
let old_node = self.map.remove(&old_key).unwrap();
let node_ptr: *mut LruKEntry<K, V> = old_node.as_ptr();
unsafe {
(*node_ptr).times = 0;
}
let replaced = unsafe {
(
mem::replace(&mut (*node_ptr).key, mem::MaybeUninit::new(k)).assume_init(),
mem::replace(&mut (*node_ptr).val, mem::MaybeUninit::new(v)).assume_init(),
)
};
self.detach(node_ptr);
(Some(replaced), old_node)
} else {
(None, unsafe {
NonNull::new_unchecked(Box::into_raw(Box::new(LruKEntry::new(k, v))))
})
}
淘汰数据，优先淘汰普通队列的数据，如果普通队列为空，将进入淘汰K次队列。区别就是在于淘汰时多选择一次数据。效率上也基本上可以忽略不计。
pop移除栈顶上的数据，最近使用的pop_last移除栈尾上的数据，最久未被使用的contains_key判断是否包含key值raw_get直接获取key的值，不会触发双向链表的维护get获取key的值，并维护双向链表get_mut获取key的值，并可以根据需要改变val的值retain 根据函数保留符合条件的元素get_or_insert_default 获取或者插入默认参数get_or_insert_mut 获取或者插入对象，可变数据在cargo.toml中添加
[dependencies]
algorithm = "0.1"
use algorithm::LruKCache;
fn main() {
let mut lru = LruKCache::with_times(3, 3);
lru.insert("this", "lru");
for _ in 0..3 {
let _ = lru.get("this");
}
lru.insert("hello", "algorithm");
lru.insert("auth", "tickbh");
assert!(lru.len() == 3);
lru.insert("auth1", "tickbh");
assert_eq!(lru.get("this"), Some(&"lru"));
assert_eq!(lru.get("hello"), None);
assert!(lru.len() == 3);
}
https://github.com/tickbh/algorithm-rs
Lru-k与lru的区别在于多维护一个队列，及每个元素多维护一个次数选项，对于性能的影响不大，仅仅多耗一点cpu，但是可以相应的提高命中率，下一章将介绍LFU按频次的淘汰机制。