Получение ключа значения из хеш-таблицы c #

Question

У меня есть хеш-таблица, содержащая значения ^ j. j является ключом, а ^ j является значением. Я теперь вычисляю другое значение a ^ m. Я в основном хочу посмотреть, есть ли ^ х в хэш-таблице. Я использовал ContainsValue fn. чтобы найти значение. Как мне узнать ключ значения?

Вот небольшой фрагмент, где я хочу реализовать поиск значения.

    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****
    }

Это что-то меняет? тот факт, что я ищу внутри цикла?

Answer 1

Самый быстрый способ - это, вероятно, перебрать элементы DictionaryEntry в хеш-таблице, чтобы найти значение, которое, в свою очередь, дает вам ключ. Я не вижу, как еще это сделать.

Answer 2

Во-первых, вы обязательно должны использовать Dictionary<TKey, TValue> вместо Hashtable - если вы используете BigInteger из .NET 4, нет причин не использовать универсальные коллекции везде , которые вы можете использовать. Скорее всего, по большей части вы не увидите никакой разницы в том, как он используется - просто создайте его с помощью:

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

для начала. Следует обратить внимание на то, что индексатор выдаст исключение, если ключ отсутствует на карте - используйте TryGetValue, чтобы получить значение, если оно существует, и bool, чтобы сказать, или нет существовал .

Что касается поиска ключа по значению - нет способа сделать это эффективно из Dictionary. Вы можете искать все записи, что проще всего сделать с помощью LINQ:

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

но он будет перебирать весь словарь, пока не найдет совпадение, поэтому это операция O (n).

Если вы хотите сделать это эффективно, вам следует сохранить два словаря - один от a до a^j и один от a^j до a. Когда вы добавляете запись, добавьте ее в обе стороны. Где-то в переполнении стека у меня есть пример кода класса, который делает это для вас, но я сомневаюсь, что смогу найти его легко. РЕДАКТИРОВАТЬ: есть один, который справляется с несколькими сопоставлениями здесь ; версия «с одним отображением» находится в ответе под этим.

В любом случае, если у вас есть два словаря, по одному в каждом направлении, это легко - очевидно, вы просто посмотрите a^m как ключ во втором словаре, чтобы найти исходное значение, которое его создало.

Обратите внимание, что вам нужно подумать, возможно ли, чтобы два исходных ключа имели одно и то же значение - в этот момент вы, очевидно, не сможете иметь оба отображения в одном обратном словаре (если это не было Dictionary<BigInteger, List<BigInteger>> или что-то подобное).

Answer 3

Редактировать: Изменено для использования Dictionary<TKey, TValue>

Dictionary<TKey, TValue> является IEnumerable<KeyValuePair<TKey, TValue>>.Если вы сделаете foreach непосредственно над ним, вы можете получить ключ и значение для каждой записи.

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);
    }
}

Если у вас есть более новая версия .Net framework, вы можете использовать Linq для поискасвои спички и поместите их в свою коллекцию.Вот пример кода, показывающий немного синтаксиса Linq:

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();
    }
}

Answer 4

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

    return null;
}