如何在C＃中实现QueueDictionary，Queue和Dictionary的组合？ [英] How would I implement a QueueDictionary, a combination of Queue and Dictionary in C#?

问题描述

基本上，我想要的数据结构将镜像一个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）; 
返回结果; 
} 
} 
 
 public void Enqueue（TKey key，TValue value）
 {
 lock（_syncRoot）
 {
 _dictionary.Add（key，value）; 
 _queue.Enqueue（key）; 
} 
} 
} 
  

解决方案

而不是在内部使用队列，您可以使用LinkedList。然后在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>>>（）; 
 
私有readonly对象_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）; 
} 
} 
} 
  

Basically the data structure I want would mirror a MSMQ but would be in memory, because it is being used in the one process. By mirroring MSMQ I mean you would enqueue objects, then you could either dequeue objects or retrieve them using a key. Here is me initial attempt. My main problem with this attempt is that the Get by id would be used frequently and therefore the queue would end up having a lot of "dead" objects in it.

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);
        }
    }
}

解决方案

Rather than using a Queue internally, you could use a LinkedList. Then in the Dictionary you can store the Key and the LinkedListNode. Then when you remove the item from the Dictionary, you can unlink the LinkedListNode from the linked list. Of course you loose the locality of the Queue, but gain the performance of the random access.

Here is a quick and dirty example, not tested so excuse any errors and no error checking. For example you should check if the queue is empty, make sure an item with the same key is not already in the dictionary etc.

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);
    }
  }
}

这篇关于如何在C＃中实现QueueDictionary，Queue和Dictionary的组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！