c# - C# 中的 CircularBuffer IDictionary？

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

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

谢谢

最佳答案

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

O(1) enqueue (to back)

O(n) 插入违反添加顺序(因为您必须保持数组最新)；反正你可能永远不需要这个

O(1) 出队(从前面)

O(1) 或 O(log n) 键控查找

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

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

抛出异常(如果从来没有重复的键，那么插入两次只是一个错误)

移回:检查字典的 Count，然后使用 this[key] 索引器插入键。如果大小增加，则检查列表是否已经具有最大容量，从列表和字典中删除前面的项目并将新项目添加到后面。如果字典的大小没有增加，请将项目从列表中的现有位置移动到列表的后面。

Overwrite without move: 和上一个项目一样，但是你不必把列表弄乱。

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

关于c# - C# 中的 CircularBuffer IDictionary？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1239858/