Beläggningsgrad, resizing och prestanda

Så fungerar det

Beläggningsgrad är ofta antal / antalBuckets vid chaining eller upptagna platser / kapacitet vid open addressing. När beläggningen ökar kan kollisionerna ta mer tid. Resizing skapar en större array och hashar om posterna eftersom modulus ändras. Ett enskilt bygge kan ta O(n), men med geometrisk kapacitetsökning blir många insättningar ofta amorterat O(1).

Hashkoder måste följa regeln: om Equals(a,b) är sann måste samma hashfunktion ge samma hashkod. Olika nycklar får kollidera. Använd stabila likhetsfält för nycklar och förlita dig inte på att hashkoder är identiska mellan .NET-processer eller versioner.

Exempel i C# och C++

C#

C# | Example.cs

using System;
using System.Collections.Generic;

var names = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
names.Add("ALICE");
Console.WriteLine(names.Contains("alice")); // True

// Choose the comparer at collection creation time, not per lookup.

C++

C++ | Example.cpp

#include <unordered_set>
#include <string>
#include <iostream>

std::unordered_set<std::string> names;
names.insert("ALICE");
std::cout << names.contains("ALICE") << '\n'; // 1
std::cout << names.contains("alice") << '\n'; // 0
// Default C++ string equality is case-sensitive.
// For case-insensitive keys, define matching hash and equality functors.

När, varför och vanliga fallgropar

Prestanda: Skilj mellan genomsnitt, förväntad, amorterad och värsta fall. Med svåra kollisioner kan ett uppslag bli linjärt i antalet nycklar. Öva: Ändra bucketantal från 5 till 7 i simulatorn och se hur alla ID:n flyttas.

Interaktiv hashtabell · HashSet och Dictionary

Språkskillnad: StringComparer.OrdinalIgnoreCase gör C#-uppslagningen skiftlägesokänslig. std::unordered_set<std::string> i C++ är normalt skiftlägeskänslig och behöver egna matchande hash- och likhetsfunktioner för samma beteende.