Извлечение ключа из хэш-таблицы C#

Question

У меня есть хеш-таблица, содержащая значения a^j. j - это ключ, a^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**** 
    } 

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

Answer 1

Edit:Изменено использовать 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, вы могли бы использовать 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 2

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

    return null; 
} 

Answer 3

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

Answer 4

Во-первых, вы должны абсолютно использовать 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 (п) операции.

Если вы хотите сделать это эффективно, вы должны иметь два словаря - один из a к a^j и один из a^j в a. Когда вы добавляете запись, добавьте ее в оба конца. Где-то в переполнении стека У меня есть образец кода класса, который делает это для вас, но я сомневаюсь, что смогу найти его легко. EDIT: есть один, который справляется с несколькими сопоставлениями here; версия «единого сопоставления» находится в ответе ниже этого.

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

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