Find from a hashtable using the value

Question

I have a following hash table:

private Hashtable Sid2Pid = new Hashtable();

Sid2Pid.Add(1,10);
Sid2Pid.Add(2,20);
Sid2Pid.Add(3,20);
Sid2Pid.Add(4,30);

Now how to get the list of keys from the above hashtable that has a value of 20 using LinQ

Answer 1

A HashTable is IEnumerable of DictionaryEntry, with a little casting this can be converted into something the LINQ operators can work on:

var res = from kv in myHash.Cast<DictionaryEntry>
          where (int)kv.Value = targetValue
          select (int)kv.Key;

NB. This will throw an exception if you pass different types.

Answer 2

Use a Dictionary<int, int> instead of a Hashtable (see here for why) then do the following:

var keys = Sid2Pid.Where(kvp => kvp.Value == 20)
                  .Select(kvp => kvp.Key);

Answer 3

I know your question wasn't exactly this, but why don't you also store an 'inverted' index of sorts?

Something like

Dictionary <int, List<int>> invertedIndex;

where the key here is the value and the entry is the list of keys in your original hash table.

So your add will be:

private Dictionary<int, List<int>> invertedIndex = new Dictionary<int, List<int>>();

Add(int a, int b)
{
    Sid2Pid.Add(a,b);

    List <int> keys;
    if (invertedIndex.TryGetValue(b, out keys))
    {
        keys.Add(a);
    }
    else
    {
        keys = new List<int>();
        keys.Add(a);
        invertedIndex[b] = keys;
    }
}

Now if you want the keys, all you need is to lookup the inverted index and get the list.

If space is not important, but time is, this could come in useful. Without something like this, you will have to walk the entire hashtable (LINQ or not, see the other answers) and that might make it slow if done frequently enough.

A possible problem with the above extra Dictionary solution is maintaining consistency when exceptions are thrown. For instance if the Sid2Pid.Add throws an exception you might have to handle it etc.