Najczęściej programiści korzystają z klasy Dictionary ale warto rozważyć dwie inne kolekcje. ListDictionary przechowuje dane na liście jednokierunkowej. Dla słowników z kilkoma kluczami <10 zwykle jest to szybsze niż standardowy hash table, wykorzystywany w Dictionary. Szybciej jest po prostu przejść przez 10 elementów, niż liczyć skomplikowaną funkcję haszującą. W przypadku hash table, również należy zwrócić uwagę na konflikty – sytuacje gdy funkcja haszująca zwróciła ten sam skrót, dla dwóch różnych kluczy.
Operacje mają złożoność O ( n ) dla ListDictionary ponieważ trzeba za każdym razem przejść przez całą listę. HybridDictionary to hybryda dwóch rozwiązań. Jeśli liczba kluczy jest niska, wykorzystywana jest lista jednokierunkowa. W przeciwnym wypadku, tworzony jest hash table.
Napiszmy prosty benchmark:
class Program { static void Main(string[] args) { const int n = 30; string[] keys = GetKeys(n).ToArray(); var hybridDictResults = RunTests((i) => new HybridDictionary(i), n, keys); var listDictionaryResults = RunTests((i) => new ListDictionary(), n, keys); } private static double[] RunTests(Func<int, IDictionary> dictionaryFactory, int n, string[] keys) { double[] results = new double[n]; const int tests = 100; for (int i = 1; i <= n; i++) { var subKeys = keys.Take(i).ToArray(); var hybridDictionary = PopulateDictionary(dictionaryFactory(i), subKeys); double averageTicks = 0; for (int test = 0; test < tests; test++) { Stopwatch stopwatch = Stopwatch.StartNew(); foreach (string key in subKeys) { var value = hybridDictionary[key]; } long ticks = stopwatch.ElapsedTicks; averageTicks += ticks; } results[i - 1] = (double)averageTicks/tests; } return results; } static IDictionary PopulateDictionary(IDictionary dictionary, IEnumerable<string> keys) { foreach (var key in keys) dictionary.Add(key, true); return dictionary; } static IEnumerable<string> GetKeys(int n) { for (int i = 0; i < n; i++) { yield return Path.GetRandomFileName(); } } }
Wartości dla pierwszych 30 próbek przedstawiają się następująco:
Jak widać, powyższej 10-15 próbek, ListDictionary jest kompletnie nieopłacalny. Z tego względu dużo bezpieczniej jest użyć HybridDictionay lub po prostu Dictionary. Istnieją jednak przypadki, gdzie ListDictionary jest dobrym rozwiązaniem. Jeśli kluczami są np. cyfry w systemie dziesiętnym wtedy ograniczenie liczby kluczy do 10 jest oczywiście naturalne i poprawne.