Bygg en hashtabell i C#

Så fungerar det

En hashtabell behöver en array med buckets. Vid separate chaining innehåller varje bucket noll eller fler poster. Varje post sparar både nyckel och värde. Vid Put beräknas index, befintlig nyckel jämförs och posten uppdateras eller läggs till. TryGetValue och Remove behöver bara undersöka den aktuella bucketen.

Vår nedladdningsbara EducationalHashMap<TKey,TValue> implementerar Put, TryGetValue, Remove, Count och automatisk omallokering. Den använder IEqualityComparer<TKey>, hanterar negativa hashkoder och omhashar poster när beläggningen växer. Den är medvetet enklare än .NET:s produktions-Dictionary. Läs källkoden och följ varje operation.

Exempel i C# och C++

// EducationalHashMap.cs must be in the same .NET project.
var scores = new EducationalHashMap<string, int>(5);
scores.Put("Ada", 10);
scores.Put("Grace", 20);
scores.Put("Ada", 15); // replace by equal key, not duplicate
if (scores.TryGetValue("Ada", out int value))
    Console.WriteLine(value); // 15
Console.WriteLine(scores.Remove("Grace")); // True
Console.WriteLine(scores.Count); // 1

#include <unordered_map>
#include <string>
#include <iostream>

// C++ standard-library map, NOT a port of EducationalHashMap.
std::unordered_map<std::string, int> scores;
scores["Ada"] = 10;
scores["Grace"] = 20;
scores["Ada"] = 15; // update an existing key
if (auto it = scores.find("Ada"); it != scores.end())
    std::cout << it->second << '\n'; // 15
std::cout << scores.erase("Grace") << '\n'; // 1
std::cout << scores.size() << '\n'; // 1

När, varför och vanliga fallgropar

Följ koden: Beräkna index med jämförarens hashkod, jämför nycklar i bucketen, kontrollera beläggning före en ny post och fördela om alla poster vid resizing. Normal förväntad kostnad är O(1) med bra hashning; i värsta fall kan det bli O(n). Öva: Ändra startstorlek och bekräfta att uppslag fungerar efter resizing.

Ladda ned fullständig EducationalHashMap.cs

Klassen är pedagogisk kod, inte en ersättning för Dictionary<TKey,TValue> i produktionssystem.

Interaktiv hashtabell · HashSet och Dictionary