Hashfunktioner, buckets och kollisioner

Så fungerar det

För icke-negativa heltal kan vi börja med bucket = id % bucketCount. För värdena 1, 6, 11, 14, 19, 21, 27, 34 och fem buckets hamnar 1,6,11,21 i bucket 1, 14,19,34 i bucket 4 och 27 i bucket 2; bucket 0 och 3 är tomma. Kollisioner är väntade, inte ett fel.

En hashkod är inte ett unikt ID. Olika nycklar kan ha samma hashkod, och olika hashkoder kan ge samma bucketindex. Kollisionshanteringen måste jämföra nycklar med rätt likhetsregler.

Exempel i C# och C++

C#

C# | Example.cs

static int BucketIndex(int id, int bucketCount)
{
    if (bucketCount <= 0) throw new ArgumentOutOfRangeException(nameof(bucketCount));
    // Maps negative IDs into 0..bucketCount-1 as well.
    return ((id % bucketCount) + bucketCount) % bucketCount;
}
Console.WriteLine(BucketIndex(19, 5)); // 4
Console.WriteLine(BucketIndex(29, 5)); // 4; not necessarily present

C++

C++ | Example.cpp

#include <iostream>
#include <stdexcept>

int bucketIndex(int id, int bucketCount) {
    if (bucketCount <= 0) throw std::invalid_argument("bucketCount");
    return (id % bucketCount + bucketCount) % bucketCount;
}
// The same bucket can contain several different keys.
std::cout << bucketIndex(19, 5) << '\n'; // 4
std::cout << bucketIndex(29, 5) << '\n'; // 4

När, varför och vanliga fallgropar

Uppslag: 19 % 5 = 4; undersök bucket 4 och jämför varje nyckel. Även 29 % 5 = 4, men saknas 29 misslyckas sökningen. Borttagning: jämför nycklarna och ta bara bort den matchande posten. Fallgrop: Anta aldrig att lika hashkod betyder lika nyckel.

Interaktiv hashtabell · HashSet och Dictionary