Retrieving the key of a value from a hash table c#

Question

I have a hash table that contains values of a^j. j is the key and a^j is the value. I am now calculating another value a^m. I basically want to see if a^m is in the hash table. I used the ContainsValue fn. to find the value. How would i go about finding out the key of the value?

Here is a little snippet of where i want to implement the search for the value.

    Dictionary<BigInteger, BigInteger> b = new Dictionary<BigInteger, BigInteger>();
     ***add a bunch of BigIntegers into b***
    for(int j=0; j < n; j++)
    {
       z =  q* BigInteger.ModPow(temp,j,mod);
       ***I want to implement to search for z in b here****
    }

Does this change anything? the fact that i am searching while inside a for loop?

Answer 1

The fastest way is probably to iterate through the hashtable's DictionaryEntry items to find the value, which in turn gives you the key. I don't see how else to do it.

Answer 2

Firstly, you should absolutely be using Dictionary<TKey, TValue> instead of Hashtable - if you're using BigInteger from .NET 4, there's no reason not to use generic collections everywhere you can. Chances are for the most part you'd see no difference in how it's used - just create it with:

Dictionary<BigInteger, BigInteger> map = 
    new Dictionary<BigInteger, BigInteger>();

to start with. One thing to watch out for is that the indexer will throw an exception if the key isn't present in the map - use TryGetValue to fetch the value if it exists and a bool to say whether or not it did exist.

As for finding the key by value - there's no way to do that efficiently from a Dictionary. You can search all the entries, which is most easily done with LINQ:

var key = map.Where(pair => pair.Value == value)
             .Select(pair => pair.Key)
             .First();

but that will iterate over the whole dictionary until it finds a match, so it's an O(n) operation.

If you want to do this efficiently, you should keep two dictionaries - one from a to a^j and one from a^j to a. When you add an entry, add it both ways round. Somewhere on Stack Overflow I've got some sample code of a class which does this for you, but I doubt I'd be able to find it easily. EDIT: There's one which copes with multiple mappings here; the "single mapping" version is in the answer beneath that one.

Anyway, once you've got two dictionaries, one in each direction, it's easy - obviously you'd just lookup a^m as a key in the second dictionary to find the original value which created it.

Note that you'll need to consider whether it's possible for two original keys to end up with the same value - at that point you obviously wouldn't be able to have both mappings in one reverse dictionary (unless it was a Dictionary<BigInteger, List<BigInteger>> or something similar).

Answer 3

private object GetKeyByValue(object searchValue)
{
    foreach (DictionaryEntry entry in myHashTable)
    {
        if (entry.Value.Equals(searchValue))
        {
            return entry.Key;
        }
    }

    return null;
}

Answer 4

Edit: Changed to use Dictionary<TKey, TValue>

Dictionary<TKey, TValue> is an IEnumerable<KeyValuePair<TKey, TValue>>. If you do a foreach over it directly, you can get both the key and value for each entry.

class SomeType
{
    public int SomeData = 5;

    public override string ToString()
    {
        return SomeData.ToString();
    }
}

// ...

var blah = new Dictionary<string, SomeType>();
blah.Add("test", new SomeType() { SomeData = 6 });

foreach (KeyValuePair<string, SomeType> item in blah)
{
    if(e.Value.SomeData == 6)
    {
        Console.WriteLine("Key: {0}, Value: {1}", item.Key, item.Value);
    }
}

If you have a newer version of the .Net framework, you could use Linq to find your matches, and place them in their own collection. Here's a code sample showing a little bit of Linq syntax:

using System;
using System.Collections;
using System.Linq;

class SomeType
{
    public int SomeData = 5;

    public override string ToString()
    {
        return SomeData.ToString();
    }
}

class Program
{
    static void Main(string[] args)
    {
        var blah = new Dictionary<string, SomeType>();
        blah.Add("test", new SomeType() { SomeData = 6 });

        // Build an enumeration of just matches:

        var entriesThatMatchValue = blah
            .Where(e => e.Value.SomeData == 6);

        foreach (KeyValuePair<string, SomeType> item in entriesThatMatchValue)
        {
            Console.WriteLine("Key: {0}, Value: {1}", item.Key, item.Value);
        }

        // or: ...

        // Build a sub-enumeration of just keys from matches:

        var keysThatMatchValue = entriesThatMatchValue.Select(e => e.Key);

        // Build a list of keys from matches in-line, using method chaining:

        List<string> matchingKeys = blah
            .Where(e => e.Value.SomeData == 6)
            .Select(e => e.Key)
            .ToList();
    }
}