Öppen adressering och linjär probing

Så fungerar det

Vid separate chaining delar kolliderande nycklar en bucket med flera poster. Vid open addressing ligger varje nyckel i en plats i själva arrayen. Om den första platsen är upptagen testar linjär probing (index + 1) % capacity, därefter (index + 2) % capacity och så vidare tills den hittar nyckeln eller en ledig plats.

Uppslag måste följa samma probsekvens som insättning. Borttagning är knepig: gör man en mellanliggande plats tom kan sökningar stoppa för tidigt. Riktiga implementationer använder tombstones eller lämplig förflyttning. Tabellen måste ha ledig kapacitet; om den är full går det inte att lägga till fler.

Exempel i C# och C++

C#

C# | Example.cs

int[] slots = new int[11];
bool[] used = new bool[11];
int key = 19;
int start = key % slots.Length;
for (int step = 0; step < slots.Length; step++)
{
    int i = (start + step) % slots.Length;
    if (!used[i]) { slots[i] = key; used[i] = true; break; }
}
// This insertion-only example omits lookup/deletion and resizing.

C++

C++ | Example.cpp

#include <vector>
std::vector<int> slots(11);
std::vector<bool> used(11, false);
int key = 19;
int start = key % static_cast<int>(slots.size());
for (int step = 0; step < static_cast<int>(slots.size()); ++step) {
    int i = (start + step) % static_cast<int>(slots.size());
    if (!used[i]) { slots[i] = key; used[i] = true; break; }
}
// Insertion only: deletion needs tombstones or back-shifting.

När, varför och vanliga fallgropar

Jämför: Chaining kan lagra flera värden i samma bucket. Linjär probing kan ge bra minneslokalitet men också klustring. Fallgrop: Att radera genom att sätta used[i] = false är inte en korrekt generell lösning efter kollisioner. Öva: Sätt in 1,12,23 med kapacitet 11 och rita varje probsteg.

Interaktiv hashtabell · HashSet och Dictionary