ConcurrentHashQueue in C# The ConcurrentHashQueue data structure is a FIFO queue that at the same time allows look-ups of items based on a key in O(1) like a dictionary. It can be used as a cache when the number of cached items is a constant and the eviction strategy is FIFO. This makes sense when the cost of computing/creating an evicted item is not so high to justify the book-keeping costs of a LRU cache.

This implementation is also intended to be thread-safe.

internal class ConcurrentHashQueue&lt;TKey, TValue&gt;
{
    private readonly object _syncRoot = new object();
    private readonly int _capacity;
    private readonly Dictionary&lt;TKey, TValue&gt; _map;
    private readonly Queue&lt;TKey&gt; _queue;

    public ConcurrentHashQueue(int capacity)
    {
        _capacity = capacity;
        _map = new Dictionary&lt;TKey, TValue&gt;(capacity);
        _queue = new Queue&lt;TKey&gt;(capacity);
    }

    public TValue GetOrAdd(TKey key, Func&lt;TValue&gt; createValue)
    {
        TValue value;
        // first try to get the value without locking
        // ReSharper disable once InconsistentlySynchronizedField
        if (_map.TryGetValue(key, out value))
        {
            return value;
        }

        // the value needs to be created and added
        lock (_syncRoot)
        {
            // recheck existence within critical section to avoid racing conditions
            if (_map.TryGetValue(key, out value))
            {
                return value;
            }
            value = createValue();
            Add(key, value);
        }
        return value;
    }

    private void Add(TKey key, TValue value)
    {
        if (_map.Count == _capacity) // capacity reached
        {
            RemoveFirst();
        }
        _map.Add(key, value);
        _queue.Enqueue(key);
        Debug.Assert(_map.Count == _queue.Count, "The count of the queue should always equal to the count of the map.");
        Debug.Assert(_map.Count &lt;= _capacity, "The count of items should never exceed the capacity.");
    }

    private void RemoveFirst()
    {
        TKey first = _queue.Dequeue();
        _map.Remove(first);
    }
}
When you create a List, are you forced to provide a capacity? No you're not. I think it should be the same concerning your data structure. There are several occasions where you just don't know how many objects you'll have. Since the underlying Queue and Dictionary can very well adapt to increase your capacity, your data structure has nothing to fear by offering a default empty constructor.

I'm wondering why GetOrAdd exists. When you Get an object from a Queue, you should remove that object, IMO. So you should implement some kind of Exists method, and the client of your object will deal with the scenario where you could want to add an object if it doesn't exist already.

Finally, there is one terrible side effect in your code :

if (_map.Count == _capacity) // capacity reached
{
    RemoveFirst();
}


If you reach capacity, you should either expand your capacity, or throw an exception. Removing the first object is just a way to hide the problem. But if I use your class, I would never expect this situation if the queue was full.