Click here to Skip to main content
15,667,885 members
Please Sign up or sign in to vote.
5.00/5 (10 votes)
See more:
I guess that there isn't such a data structure in the .NET Framework? What should do the trick? Two Dictionaries, or Two Hashtables? What would you recommend. In General, I need something Map<t1,t2>, that can find efficiently both key by value and value by key (The match is between a connection ID to a client ID, so its an injective function for the mathematicians among us...)
Sergey Alexandrovich Kryukov 25-Oct-11 2:49am    
Good question, my 5.
BillWoodruff 25-Oct-11 3:14am    
Can we assume that each key has a unique value ? If not, what would you want to return if querying by value and there were multiple key matches: a collection of Keys ? the first Key that matched the Value only ?
BillWoodruff 25-Oct-11 4:05am    
Unfortunately you are dealing with someone whose swimming in math was limited to the shallow end of the pool, but I am going to interpret your comment as indicating that at any one time the case of multiple keys sharing the same value ... in which case the 'mirror dictionary' ... where values are now keys has a potential duplicate-key error possible ... does not arise. But, I have done a lot of experimenting with .NET dictionaries, including "dual" matching dictionaries of the type SAK mentions here.
BillWoodruff 25-Oct-11 5:00am    
Question+= 5; Very stimulating, thanks.

Yes, the simplest way to achieve that is two dictionaries: System.Collections.Generic.Dictionary<ConnectionId, ClientId> and System.Collections.Generic.Dictionary<ClientId, ConnectionId> (assuming your two type for those IDs are different), see[^].

Of course, encapsulate them in one class and make the dictionaries themselves non-accessible, only expose methods implemented on both dictionary fields: Add, Remove, Get, TryGet by both keys, etc.

And of course this approach will be only valid for an injective functions as dictionary preserves uniqueness by a key, and you need search by key in both directions.

You will have search algorithm of O(1) for big collections, which is effective enough :-) Perhaps you also could achieve some better memory overhead for such two-way dictionary, but only if you created the algorithm from scratch.

Share this answer
Sergey Alexandrovich Kryukov 25-Oct-11 3:38am    
No problem at all.
Good luck, call again.
BobJanova 25-Oct-11 4:37am    
Not at all, it is obvious once it is shown to you but it was a good question.
Sergey Alexandrovich Kryukov 25-Oct-11 10:49am    
Thank you, Bob.
That's why I voted my 5 for the question.
Kuthuparakkal 22-Feb-15 17:21pm    
my 5+
Sergey Alexandrovich Kryukov 22-Feb-15 17:23pm    
Thank you. I'm curious how such an old answer came up.
28/10/11: minor edit for clarity, and to fix a missing CRLF in the code sample that made the List declaration part of a comment.

My sense is that SAK has definitively answered this question, but I will add a corollary: back when I was experimenting with such 'mirrored' dual dictionaries, I found myself questioning if the same task (lookup by key or value) could be just as efficiently done using generic Lists with some possible strategic additional value: using two Lists, eliminates the possible errors of having duplicate keys in the 'mirror' dictionary.

An example (from pre-Linq days):
// note: duplicates used deliberately
List<int> theKeys = new List<int>() { 3, 4, 7, 1, 2, 5, 6, 2 };
List<string> theValues = new List<string>() { "three", "four", "seven", "one", "two", "five", "six", "two" };

private string findByKey(int theKey)
    return theKeys.Contains(theKey) ? theValues[theKeys.IndexOf(theKey)] : null;

private int? findByValue(string theValue)
    // note the hack here in order
    // to be able to return null
    // in the case of a 'fail
    int? result = null;

    if (theValues.Contains(theValue)) result = theKeys[theValues.IndexOf(theValue)];

    return result;
A sample test for out-of-bounds values (verify nulls are being returned):
string theString = findByKey(77);
int? theInt = findByValue("magic");
Now that we are smothered in Linq's glory, I will, someday, re-visit this experiment, looking at using Linq to implement select first, last, multiples, etc.

Now the "cost" of using this type of solution, of course, has to include filling the 'mirrored' Lists properly. I still really enjoy messing around with .NET Dictionaries !
Share this answer
BobJanova 25-Oct-11 4:40am    
Isn't looking up by IndexOf in a list less efficient than looking up in a Dictionary by key?

Also, IndexOf returns -1 if it's not found, so you don't need to do the Contains check (which will search the whole list again), you can do

int p = theKeys.IndexOf(theKey);
return p >= 0 ? theKeys[p] : null;
BillWoodruff 25-Oct-11 4:57am    
All I know of the efficiency of IndexOf is what MSDN says: "This method performs a linear search; therefore, this method is an O( n) operation, where n is Count."

My motivation for experimenting with this form, as an alternative to 'mirrored' dictionaries, was, as I recall, to explore the cases of duplicate "values" that, could not be handled by said mirrored-dictionaries.

Excellent corrections, Bob ! thanks. I forget why I was so focused on making null a result of the look-up functions, but I think there was a reason ... back then.
Sergey Alexandrovich Kryukov 25-Oct-11 10:52am    
The storage of the dictionary is well-known; it's based on buckets, could be easily estimated. You always need redundancy to achieve speed. Very reasonable trade-off in very many situations, I would say.
Kuthuparakkal 22-Feb-15 17:21pm    
good one!
BillWoodruff 23-Feb-15 7:55am    
I'm glad you found this interesting. One could implement "dual" HashTables to handle this scenario (multiple keys or values with the same value), but, of course, repeats of identical key/value pairs would produce "collisions." In practice, I use a generic dual-dictionary class I wrote. If you want to see that code, then ask a question here with the key words "generic dual dictionary." cheers, Bill

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900