Альтернатива словарю для быстрого поиска ключей?

Question

Я сталкиваюсь с ситуациями, когда мне нужно отслеживать, если я обработал определенное значение. В этих случаях я использую Dictionary(Of TKey, TValue), чтобы отслеживать значения, которые я обработал. В принципе, по мере обработки каждого значения я вставляю обработанное значение в ключ в словарь. Когда я хочу увидеть, обработал ли я это значение, я использую метод ContainsKey, чтобы узнать, существует ли значение в коллекции.

Это хорошо работает, но мне нужно вставить что-то в сторону значения пары ключ-значение. Я бы просто использовал List(Of T), но я хочу, чтобы производительность поиска хеш-таблицы выполнялась в словаре. Есть ли сбор данных в .Net, который более подходит для этой цели?

Answer 1

Я предлагаю HashSet<T>. Вы можете просто ввести ключ, если все, что вам нужно знать, это то, что ключ уже используется.

Это действительно просто, тоже:

if (myHashSet.Add(key)) 
{ 
    // item wasn't in the hash set, so process it. 
} 

Add, как "добавить, если не существует." Он возвращает true, если элемент был добавлен. Он возвращает false, если элемент уже был в коллекции.

Или, вы можете использовать Contains для тестирования, а затем Add для добавления.

Answer 2

Возможно, вы можете использовать System.Collections.Specialized.StringCollection, но я не уверен, что он так же эффективен, как и словарь, и требует, чтобы вы вводили ключи в строки.

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

Public Class KeyDictionary(Of T) 
    Inherits Dictionary(Of T, Boolean) 

    Public Overloads Sub Add(key As T) 
     MyBase.Add(key, False) 
    End Sub 
End Class 

затем объявить экземпляр и добавить значение:

Dim cKeys As New KeyDictionary(Of Integer) 

    If Not cKeys.ContainsKey(1) Then 
     cKeys.Add(1) 
    End If 

И в C#:

public class KeyDictionary<T> : Dictionary<T, bool> 
{ 
    public void Add(T key) 
    { 
     base.Add(key, false); 
    } 
} 

, чтобы объявить экземпляр и добавить a Значение:

 var cKeys = new KeyDictionary<int>(); 

     if (!(cKeys.ContainsKey(1))) 
     { 
      cKeys.Add(1); 
     } 

Answer 3

На .NET 3.5 или новее вы n используйте для этой цели HashSet. Необходимые методы называются Add и Contains. Обе операции имеют временную сложность O (log n), в отличие от O (n) для List.