我如何在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.然后,当您从字典中删除该项时,您可以取消链接列表中的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);
    }
  }
}