c# - C# 中的 CircularBuffer IDictionary？

Question

我需要一个 CircularBuffer IDictionary。谁能给我指出一个好的开源实现。

因此 IDictionary 具有最大容量，比如配置为 100 个项目，当添加项目 101 时，原始的第一个项目将从字典中弹出/删除，从而确保项目计数永远不会超过 100。

谢谢

Answer 1

要保持 O(1) 插入(删除超过 100 的最旧项目)和 O(1) 查找，您需要一个实现 IDictionary 的类并且保持内部有序列表。如果内存更受关注，BST 实现如 SortedList可能更合适。无论如何，您的类(class)将同时包含 T[]和一个 Dictionary<T,K> (或 SortedList<T,K> )。做你自己的循环缓冲区索引(简单)，并在添加、删除等方法中保持两个集合的当前状态。你将拥有:

• O(1) 入队(返回)
• O(n) 的插入违反了添加的顺序(因为你必须保持数组是最新的)；无论如何你可能永远不需要这个
• O(1) 出队(从前面)
• O(1) 或 O(log n) 键控查找

使其通用并实现IDictionary<T,K>和 IDictionary因为没有理由不这样做，您将获得性能优势。

一个主要考虑因素:您如何处理重复键？我假设您实际上不能保留重复项，所以:

• 抛出异常(如果从来没有重复的键，那么插入两次只是一个错误)
• 向后移动:检查 Count字典，然后使用 this[key] 插入键索引器。如果大小增加，则检查列表是否已经具有最大容量，从列表和字典中删除前面的项目并将新项目添加到后面。如果字典的大小没有增加，则将该项目从其在列表中的现有位置移动到列表的后面。
• 覆盖而不移动:与上一项相同，但您不必弄乱列表。

最后，请注意内部列表保留键，而不是值。这是为了确保在超过列表容量时 O(1) 出队。