Bijective Dictionary /Map in C#

Question

Is there a bijective dictionary in.NET that efficiently stores Key/Values pairs, where both keys and values are distinct, so a bijective mapping (i.e. TryGetValue/TryGetKey) is possible? The naive approach would be to have two internal dictionaries: A key-value and a value-key dictionary, but this is not efficient in terms of memory.

Answer 1

Why is this not effecient in terms of memory? Unless you have only 64MB RAM, it wont be an issue for most (and even large tables). If it gets too big, then you should really look into using a proper database engine instead.

Answer 2

I don't believe there's one in .NET. Depending on the key/value types, I'm not sure that using two dictionaries is likely to cause that much of an efficiency loss: it's what I'd do until I saw a problem, based on the fact that it's simple.

In fact, it's very simple as I've already implemented it in another Stack Overflow answer. I'll see if I can find it...

EDIT: I found two:

• One of mine
• Another based on mine, but more fully developed with Remove etc.

Answer 3

If the values stored in the dictionaries are object types the only memory overhead will be that of the Dictionary object itself.

Answer 4

Essentially you want 2 Sets that reference the same binary element. You will always have the overhead of the references to both elements, but you'd have that either way. Each set would need a different comparer, but that's little overhead. Since you referencing the same element, in both set, you don't have 2 copies.

HashSet HashSet Methods/Members

Answer 5

It's easy to "flip" the keys and values.

var source = GetSomeDictionary();
var opposite = source.ToDictionary(x => x.Value, x => x.Key)

this is not efficient in terms of memory

Well, if you find that you truly cannot hold the second dictionary... then you can generate it when needed. This has the additional benefit of not needing to maintain both dictionaries.

But most likely, you can hold the second dictionary - and want to in order to save time.