Getting multiple keys of specified value of a generic Dictionary?

Question

It's easy to get the value of a key from a .NET generic Dictionary:

Dictionary greek = new Dictionary();
greek.Add(1, "Alpha");
greek.Add(2, "Beta");
string secondGreek = greek[2];  // Beta

But trying to get the keys given a value is not as straightforward because there could be multiple keys:

int[] betaKeys = greek.WhatDoIPutHere("Beta");  // expecting single 2

user_22656 · Answer

Okay, here's the multiple bidirectional version:

using System;
using System.Collections.Generic;
using System.Text;

class BiDictionary
{
    IDictionary> firstToSecond = new Dictionary>();
    IDictionary> secondToFirst = new Dictionary>();

    private static IList EmptyFirstList = new TFirst[0];
    private static IList EmptySecondList = new TSecond[0];

    public void Add(TFirst first, TSecond second)
    {
        IList firsts;
        IList seconds;
        if (!firstToSecond.TryGetValue(first, out seconds))
        {
            seconds = new List();
            firstToSecond[first] = seconds;
        }
        if (!secondToFirst.TryGetValue(second, out firsts))
        {
            firsts = new List();
            secondToFirst[second] = firsts;
        }
        seconds.Add(second);
        firsts.Add(first);
    }

    // Note potential ambiguity using indexers (e.g. mapping from int to int)
    // Hence the methods as well...
    public IList this[TFirst first]
    {
        get { return GetByFirst(first); }
    }

    public IList this[TSecond second]
    {
        get { return GetBySecond(second); }
    }

    public IList GetByFirst(TFirst first)
    {
        IList list;
        if (!firstToSecond.TryGetValue(first, out list))
        {
            return EmptySecondList;
        }
        return new List(list); // Create a copy for sanity
    }

    public IList GetBySecond(TSecond second)
    {
        IList list;
        if (!secondToFirst.TryGetValue(second, out list))
        {
            return EmptyFirstList;
        }
        return new List(list); // Create a copy for sanity
    }
}

class Test
{
    static void Main()
    {
        BiDictionary greek = new BiDictionary();
        greek.Add(1, "Alpha");
        greek.Add(2, "Beta");
        greek.Add(5, "Beta");
        ShowEntries(greek, "Alpha");
        ShowEntries(greek, "Beta");
        ShowEntries(greek, "Gamma");
    }

    static void ShowEntries(BiDictionary dict, string key)
    {
        IList values = dict[key];
        StringBuilder builder = new StringBuilder();
        foreach (int value in values)
        {
            if (builder.Length != 0)
            {
                builder.Append(", ");
            }
            builder.Append(value);
        }
        Console.WriteLine("{0}: [{1}]", key, builder);
    }
}

user_22656 · Answer

As everyone else has said, there's no mapping within a dictionary from value to key.

I've just noticed you wanted to map to from value to multiple keys - I'm leaving this solution here for the single value version, but I'll then add another answer for a multi-entry bidirectional map.

The normal approach to take here is to have two dictionaries - one mapping one way and one the other. Encapsulate them in a separate class, and work out what you want to do when you have duplicate key or value (e.g. throw an exception, overwrite the existing entry, or ignore the new entry). Personally I'd probably go for throwing an exception - it makes the success behaviour easier to define. Something like this:

using System;
using System.Collections.Generic;

class BiDictionary
{
    IDictionary firstToSecond = new Dictionary();
    IDictionary secondToFirst = new Dictionary();

    public void Add(TFirst first, TSecond second)
    {
        if (firstToSecond.ContainsKey(first) ||
            secondToFirst.ContainsKey(second))
        {
            throw new ArgumentException("Duplicate first or second");
        }
        firstToSecond.Add(first, second);
        secondToFirst.Add(second, first);
    }

    public bool TryGetByFirst(TFirst first, out TSecond second)
    {
        return firstToSecond.TryGetValue(first, out second);
    }

    public bool TryGetBySecond(TSecond second, out TFirst first)
    {
        return secondToFirst.TryGetValue(second, out first);
    }
}

class Test
{
    static void Main()
    {
        BiDictionary greek = new BiDictionary();
        greek.Add(1, "Alpha");
        greek.Add(2, "Beta");
        int x;
        greek.TryGetBySecond("Beta", out x);
        Console.WriteLine(x);
    }
}

user_3191 · Answer

Dictionaries aren't really meant to work like this, because while uniqueness of keys is guaranteed, uniqueness of values isn't. So e.g. if you had

var greek = new Dictionary { { 1, "Alpha" }, { 2, "Alpha" } };

What would you expect to get for greek.WhatDoIPutHere("Alpha")?

Therefore you can't expect something like this to be rolled into the framework. You'd need your own method for your own unique uses---do you want to return an array (or IEnumerable)? Do you want to throw an exception if there are multiple keys with the given value? What about if there are none?

Personally I'd go for an enumerable, like so:

IEnumerable KeysFromValue(this Dictionary dict, TValue val)
{
    if (dict == null)
    {
        throw new ArgumentNullException("dict");
    }
    return dict.Keys.Where(k => dict[k] == val);
}

var keys = greek.KeysFromValue("Beta");
int exceptionIfNotExactlyOne = greek.KeysFromValue("Beta").Single();

CMS_5445 · Answer

Maybe the easiest way to do it, without Linq, can be to loop over the pairs:

int betaKey; 
foreach (KeyValuePair pair in lookup)
{
    if (pair.Value == value)
    {
        betaKey = pair.Key; // Found
        break;
    }
}
betaKey = -1; // Not found

If you had Linq, it could have done easily this way:

int betaKey = greek.SingleOrDefault(x => x.Value == "Beta").Key;

user_12950 · Answer

A dictionary doesn't keep an hash of the values, only the keys, so any search over it using a value is going to take at least linear time. Your best bet is to simply iterate over the elements in the dictionary and keep track of the matching keys or switch to a different data structure, perhaps maintain two dictionary mapping key->value and value->List_of_keys. If you do the latter you will trade storage for look up speed. It wouldn't take much to turn @Cybis example into such a data structure.

user_6406263 · Answer

As I wanted a full fledged BiDirectional Dictionary (and not only a Map), I added the missing functions to make it an IDictionary compatible class. This is based on the version with unique Key-Value Pairs. Here's the file if desired (Most work was the XMLDoc through):

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Common
{
    /// Represents a bidirectional collection of keys and values.
    /// The type of the keys in the dictionary
    /// The type of the values in the dictionary
    [System.Runtime.InteropServices.ComVisible(false)]
    [System.Diagnostics.DebuggerDisplay("Count = {Count}")]
    //[System.Diagnostics.DebuggerTypeProxy(typeof(System.Collections.Generic.Mscorlib_DictionaryDebugView<,>))]
    //[System.Reflection.DefaultMember("Item")]
    public class BiDictionary : Dictionary
    {
        IDictionary _ValueKey = new Dictionary();
        ///  PropertyAccessor for Iterator over KeyValue-Relation 
        public IDictionary KeyValue => this;
        ///  PropertyAccessor for Iterator over ValueKey-Relation 
        public IDictionary ValueKey => _ValueKey;

        #region Implemented members

        /// Gets or sets the value associated with the specified key.
        /// The key of the value to get or set.
        /// The value associated with the specified key. If the specified key is not found,
        ///      a get operation throws a , and
        ///      a set operation creates a new element with the specified key.
        ///  is null.
        /// 
        /// The property is retrieved and  does not exist in the collection.
        ///  An element with the same key already
        /// exists in the  .
        public new TSecond this[TFirst key]
        {
            get { return base[key]; }
            set { _ValueKey.Remove(base[key]); base[key] = value; _ValueKey.Add(value, key); }
        }

        /// Gets or sets the key associated with the specified value.
        /// The value of the key to get or set.
        /// The key associated with the specified value. If the specified value is not found,
        ///      a get operation throws a , and
        ///      a set operation creates a new element with the specified value.
        ///  is null.
        /// 
        /// The property is retrieved and  does not exist in the collection.
        ///  An element with the same value already
        /// exists in the  .
        public TFirst this[TSecond val]
        {
            get { return _ValueKey[val]; }
            set { base.Remove(_ValueKey[val]); _ValueKey[val] = value; base.Add(value, val); }
        }

        /// Adds the specified key and value to the dictionary.
        /// The key of the element to add.
        /// The value of the element to add.
        ///  or  is null.
        /// An element with the same key or value already exists in the .
        public new void Add(TFirst key, TSecond value) {
            base.Add(key, value);
            _ValueKey.Add(value, key);
        }

        /// Removes all keys and values from the .
        public new void Clear() { base.Clear(); _ValueKey.Clear(); }

        /// Determines whether the  contains the specified
        ///      KeyValuePair.
        /// The KeyValuePair to locate in the .
        /// true if the  contains an element with
        ///      the specified key which links to the specified value; otherwise, false.
        ///  is null.
        public bool Contains(KeyValuePair item) => base.ContainsKey(item.Key) & _ValueKey.ContainsKey(item.Value);

        /// Removes the specified KeyValuePair from the .
        /// The KeyValuePair to remove.
        /// true if the KeyValuePair is successfully found and removed; otherwise, false. This
        ///      method returns false if  is not found in the .
        ///  is null.
        public bool Remove(KeyValuePair item) => base.Remove(item.Key) & _ValueKey.Remove(item.Value);

        /// Removes the value with the specified key from the .
        /// The key of the element to remove.
        /// true if the element is successfully found and removed; otherwise, false. This
        ///      method returns false if  is not found in the .
        ///  is null.
        public new bool Remove(TFirst key) => _ValueKey.Remove(base[key]) & base.Remove(key);

        /// Gets the key associated with the specified value.
        /// The value of the key to get.
        /// When this method returns, contains the key associated with the specified value,
        ///      if the value is found; otherwise, the default value for the type of the key parameter.
        ///      This parameter is passed uninitialized.
        /// true if  contains an element with the specified value; 
        ///      otherwise, false.
        ///  is null.
        public bool TryGetValue(TSecond value, out TFirst key) => _ValueKey.TryGetValue(value, out key);
        #endregion
    }
}

dove_30913 · Answer

revised: okay to have some kind of find you would need something other than dictionary, since if you think about it dictionary are one way keys. that is, the values might not be unique

that said it looks like you're using c#3.0 so you might not have to resort to looping and could use something like:

var key = (from k in yourDictionary where string.Compare(k.Value, "yourValue", true)  == 0 select k.Key).FirstOrDefault();

user_838 · Answer

Dictionary class is not optimized for this case, but if you really wanted to do it (in C# 2.0), you can do:

public List GetKeysFromValue(Dictionary dict, TVal val)
{
   List ks = new List();
   foreach(TKey k in dict.Keys)
   {
      if (dict[k] == val) { ks.Add(k); }
   }
   return ks;
}

I prefer the LINQ solution for elegance, but this is the 2.0 way.

Cybis_32998 · Answer

Can't you create a subclass of Dictionary which has that functionality?


    public class MyDict < TKey, TValue > : Dictionary < TKey, TValue >
    {
        private Dictionary < TValue, TKey > _keys;

        public TValue this[TKey key]
        {
            get
            {
                return base[key];
            }
            set 
            { 
                base[key] = value;
                _keys[value] = key;
            }
        }

        public MyDict()
        {
            _keys = new Dictionary < TValue, TKey >();
        }

        public TKey GetKeyFromValue(TValue value)
        {
            return _keys[value];
        }
    }

EDIT: Sorry, didn't get code right first time.

user_5151441 · Answer

Many of these answers are now outdated, here is a modern C# approach, using LINQ

Since values aren't necessarily unique, you may get multiple results. You can return an IEnumerable>:

var betaKeys = greek.Where(x => x.Value == "beta");

To transform this into an IEnumerable type, just use .Select():

var betaKeys = greek.Where(x => x.Value == "beta").Select(x => x.Key);

user_3389585 · Answer

Then layman's solution

A function similar to the one below could be written to make such a dictionary:

    public Dictionary Invert(Dictionary dict) {
    Dictionary ret = new Dictionary();
    foreach (var kvp in dict) {ret[kvp.value] = kvp.key;} return ret; }

user_10846531 · Answer

Probably, you need a bidirectional dictionary. In my mind, BidirectionalDictionary is the best realization of a bidirectional dictionary. It just provides access to an inverse O(1) dictionary.

var biDictionary = new BidirectionalDictionary { ... };

This realization, for example, has no indexations problems when TKey equals TValue:

var capital = countryCapitalDictionary["Italy"]; // "Rome"
var country = countryCapitalDictionary.Inverse["Rome"]; // "Italy"

Changing the dictionary causes the reverse dictionary to be changed safely (as well as vice versa):

countryCapitalDictionary.Clear(); // equals countryCapitalDictionary.Inverse.Clear();

var containsCapital = countryCapitalDictionary.ContainsKey("Italy"); // false
var containsCountry = countryCapitalDictionary.Inverse.ContainsKey("Rome"); // false

Also, this library supports a read-only bidirectional dictionary:

var readOnlyBiDictionary = new ReadOnlyBidurectionalDictionary(biDictionary);

You can use it via the package.

Getting multiple keys of specified value of a generic Dictionary?

16 Answers

Then layman's solution