LruMap

一组安全的最少最近使用（LRU）缓存类型，旨在提供灵活的类似映射的结构，当达到其容量时自动删除最少的最近使用键和值。

安全性

此包包括 #![forbid(unsafe)]。要实现 LruHashMap 和 LruBTreeMap 类型，每个条目的 Key 类型都存储两次，这需要 Key 类型实现 Clone。如果 Key 类型难以克隆，请考虑将其包装在 Rc 或 Arc 中，或者考虑使用 unsafe 的 LRU 实现以避免此要求。

LRU 实现方法

此包使用了一种“竞技场”样式的链表实现，其中链表的所有节点都存储在 Vec 中。不是使用节点指针，而是通过 Vec 中的索引来引用链表中的每个节点。

这允许所有 LRU 列表操作都在常数时间内完成，并保持非常高效。此包中的每个实现都使用此内部 LRU 链表实现。

LruHashMap

LruHashMap 类型是一个 LRU 实现，它内部使用 HashMap 来跟踪键。其性能特征将与底层的哈希表和哈希实现相似。

对于大多数用户来说，此类型将是最佳选择。

这个crate默认没有启用任何功能，但可以透明地切换到hashbrown及其默认哈希器，通过启用功能hashbrown。

use lrumap::{LruHashMap, Removed};

let mut lru = LruHashMap::new(3);
lru.push(1, "one");
lru.push(2, "two");
lru.push(3, "three");

// The cache is now full. The next push will evict the least recently touched entry.
let removed = lru.push(4, "four");
assert_eq!(removed, Some(Removed::Evicted(1, "one")));

LruBTreeMap

LruBTreeMap类型是一个LRU实现，内部使用BTreeMap来跟踪键。它的性能特征将与底层容器实现相似。

通过使用BTreeMap来跟踪键，这个类型可以启用高效的基于范围的查询

use lrumap::LruBTreeMap;

let mut lru = LruBTreeMap::new(5);
lru.extend([(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &4);

// Change the order by retrieving key 2.
lru.get(&2);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &2);

为什么还需要另一个LRU crate？

对于Nebari，我们需要在StdFileManager中引入一个LRU缓存来关闭最近未使用的文件。每个文件可以有多个读者，这会导致需要扫描LRU映射来查找所有匹配特定文件的值。最终，@ecton决定使用一个BTreeMap而不是HashMap的LRU实现，通过提供most_recent_in_range(key)函数来解决此问题。似乎没有现有的crate提供此功能。

开源许可

这个项目，就像Khonsu Labs的所有项目一样，是开源的。这个存储库可以在MIT许可证或Apache许可证2.0下使用。

要了解更多关于贡献的信息，请参阅CONTRIBUTING.md。