c# - 我将如何在 C# 中实现 QueueDictionary，它是 Queue 和 Dictionary 的组合？

Question

基本上，我想要的数据结构会镜像一个 MSMQ，但会在内存中，因为它正在一个进程中使用。通过镜像 MSMQ，我的意思是您可以使对象入队，然后您可以使对象出队或使用键检索它们。这是我的初步尝试。这种尝试的主要问题是 Get by 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);
        }
    }
}

Answer 1

您可以使用 LinkedList，而不是在内部使用 Queue。然后在 Dictionary 中可以存储 Key 和 LinkedListNode。然后，当您从 Dictionary 中删除该项目时，您可以从链表中取消 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);
    }
  }
}