Hashtabeller

Snabböversikt

En hashtabell använder en hashfunktion som bestämmer var en nyckel ska lagras. Sökning, insättning och borttagning tar i genomsnitt O(1) tid i en välfungerande tabell, men kollisioner kan påverka kostnaden.

Prova en enkel hashfunktion

Vi använder id % antalBuckets. Med fem buckets hamnar exempelvis både 6 och 11 i bucket 1.

INTERACTIVE / LIVE

Simulera en hashtabell

Ändra antal buckets, sätt in nya ID:n och se var kollisionerna hamnar.

Live demo

Kollisionsstrategi

Visa C#-logiken bakom steget

Utmaning: kan du förutsäga en bucket?

Räkna ut 19 % 5 för hand. Varför skulle sökning efter 29 börja i samma bucket, men kunna misslyckas?

Visa förklaringen

Svar: både 19 och 29 ger rest 4. Hashning pekar bara på kandidater; den garanterar inte att nyckeln finns.

Illustration av hashtabell där nycklar placeras i buckets

Två metoder för kollisioner

Separat kedjning lagrar flera poster i samma bucket, exempelvis i en lista. Öppen adressering söker efter en annan ledig plats i tabellen. Efter hashningen måste själva nycklarna ändå jämföras.

Beläggningsgrad och omfördelning

Ju fler nycklar som delar på få buckets, desto större blir risken för kollisioner. Många implementationer växer därför när tabellen blir för full och hashfunktionerna används igen för att placera ut nycklarna.

Operation	Genomsnitt	Sämsta fall
Sökning	`O(1)`	`O(n)`
Insättning	`O(1)`	`O(n)`
Borttagning	`O(1)`	`O(n)`

var ages = new Dictionary<string, int>();
ages["Alex"] = 24;
if (ages.TryGetValue("Alex", out int age))
    Console.WriteLine(age);

#include <unordered_map>
#include <string>
#include <iostream>
std::unordered_map<std::string, int> ages;
ages["Alex"] = 24;
if (auto it = ages.find("Alex"); it != ages.end())
    std::cout << it->second << '\n';

Likhet är en del av hashing

En hashkod pekar mot en möjlig bucket men bevisar inte att två nycklar är lika. En korrekt hashtabell jämför nycklarna efter att den hittat möjliga kandidater. Lika nycklar måste ge samma hashkod enligt jämförelsereglerna, medan olika nycklar får kollidera.

Vad händer när tabellen växer?

När fler objekt läggs till ökar belastningen. En vanlig implementation kan skapa fler buckets och fördela om nycklarna. Den enskilda omfördelningen kan kosta O(n) även om insättningar i genomsnitt är konstanta över många operationer.

Välj stabila nycklar

Ändra inte värden som påverkar hashkod eller likhetsjämförelse för en nyckel som redan används i en dictionary. Då kan efterföljande uppslagningar sluta fungera.

Fördjupning: så bygger du en hashtabell

Följ varje steg, från bucketindex och likhet till kollisioner, kod, borttagning och resize. Öva med simulatorn ovan innan du läser implementationen.

Läs vidare

Extern referensGeeksforGeeks: Hashing in Data StructuresÖppna en extern referens med fler exempel.Relaterad lektionArrayerFortsätt med ett närliggande ämne och fler exempel.