ConcurrentHashQueue in C#
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.