如何在C#中实现QueueDictionary，即队列和字典的组合？

Question

基本上，我想要的数据结构将镜像 MSMQ，但将存储在内存中，因为它仅在一个进程中使用。通过镜像 MSMQ，我的意思是您可以将对象加入队列，然后使用键获取或者出队对象。以下是我的初步尝试。我对此尝试的主要问题是，按 ID 获取将经常被使用，因此队列最终会有很多“死”对象。

public class QueueDictionary<TKey, TValue>
{
    private readonly Queue _queue = new Queue();
    private readonly Dictionary<TKey, TValue> _dictionary = new Dictionary<TKey, TValue>();
    private readonly object _syncRoot = new object();

    public TValue Dequeue()
    {
        lock (_syncRoot)
        {
            TKey key = (TKey)_queue.Dequeue();
            while (!_dictionary.ContainsKey(key))
                key = (TKey)_queue.Dequeue();
            return _dictionary[key];
        }
    }

    public TValue Get(TKey key)
    {
        lock (_syncRoot)
        {
            TValue result = _dictionary[key];
            _dictionary.Remove(key);
            return result;
        }
    }

    public void Enqueue(TKey key, TValue value)
    {
        lock (_syncRoot)
        {
            _dictionary.Add(key, value);
            _queue.Enqueue(key);
        }
    }
}

- Tim Carter

---

队列最终会有很多“死”对象，那就不算是一个真正的队列了... - Mitch Wheat

为什么会得到“死”对象？您似乎没有在 获取 中删除任何内容...而且如果您不欺骗它，您似乎不需要while循环... 顺便说一下，这个循环应该保护自己免受空队列的影响。 - Marc Gravell

@Marc - 我认为 Get 方法是 OP 寻求帮助的内容，因为你无法从队列中删除任意项。 - Josh

那么，Get 的意图是从队列中删除对象吗？还是仅仅是一个“查看”接口？ - Marc Gravell

好问题 - 我假设他想要能够通过关键字从队列中删除一个项目。 - Josh

感谢您的评论。我确实打算在Get中删除。我已经修复了上面的代码。 - Tim Carter

Answer 1

相比使用队列，您可以使用链表。在字典中存储键和LinkedListNode。然后从字典中删除项目时，可以将LinkedListNode与链接列表取消链接。当然，您会失去队列的局部性，但是获得了随机访问的性能。

以下是一个快速而简单的示例，未经测试，敬请谅解任何错误并且没有错误检查。例如，您应该检查队列是否为空，确保字典中没有相同键的项等。

public class QueueDictionary<TKey, TValue>
{
  private readonly LinkedList<Tuple<TKey, TValue>> _queue =
    new LinkedList<Tuple<TKey, TValue>>();

  private readonly Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>> 
    _dictionary = new Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>>();

  private readonly object _syncRoot = new object();

  public TValue Dequeue()
  {
    lock (_syncRoot)
    {
      Tuple<TKey, TValue> item = _queue.First();
      _queue.RemoveFirst();
      _dictionary.Remove(item.Item1);
      return item.Item2;
    }
  }

  public TValue Dequeue(TKey key)
  {
    lock (_syncRoot)
    {
      LinkedListNode<Tuple<TKey, TValue>> node = _dictionary[key];
      _dictionary.Remove(key);
      _queue.Remove(node);
      return node.Value.Item2;
    }
  }

  public void Enqueue(TKey key, TValue value)
  {
    lock (_syncRoot)
    {
      LinkedListNode<Tuple<TKey, TValue>> node = 
        _queue.AddLast(new Tuple<TKey, TValue>(key, value));
      _dictionary.Add(key, node);
    }
  }
}

- Chris Taylor

---

这个应该能很好地工作。我也希望在Dequeue(TKey key)方法中加入"_dictionary.Remove(key);"。 - Tim Carter

Answer 2

你的对象可以像队列一样运作，而不必实际使用Queue类作为其内部存储。根据你计划保留的项目数量，只维护一个LinkedList(T)可能更容易，而不是在LinkedList(T)和Dictionary(K,V)中都存储该项。

但基本上，你可以使用LinkedList(T)代替内部使用Queue，只需将新项添加到列表末尾并从列表前面出列即可。当你需要按键查找时，只需扫描匹配键的列表，或者如果项目数量使其性能不佳，则可以使用Dictionary(K, LinkedListNode(T))来双倍存储，并使用字典进行键查找。

- Josh

Answer 3

如果您使用双向链表作为队列，那么您可以完全控制Enqueue、Dequeue和特别的Get方法。因此，在Get方法中，您可以简单地从双向链表中删除键。

- Xint0