Interne detaljer i hashfunksjoner og kollisjonshåndtering
Forstå hvordan Python hasher objekter, hvordan open addressing og chaining løser kollisjoner, og hvorfor O(1) i gjennomsnitt kan forfalle til O(n).
Interne detaljer i hashfunksjoner og kollisjonshåndtering er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva er en hash map?
En hash map (ordbok i Python) kobler nøkler til verdier ved hjelp av en hashfunksjon som konverterer enhver nøkkel til en heltallsindeks i et underliggende array. En ideell hashfunksjon fordeler nøklene jevnt over arrayet, slik at oppslag, innsetting og sletting i gjennomsnitt kan utføres på O(1). Det underliggende arrayet kalles en hash-tabell eller et bøttearray.
I Python er dict en svært optimalisert hash map. Når De forstår hvordan den fungerer internt, blir det enklere å vurdere oppførsel i verste fall og velge passende nøkler.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Hashfunksjoner og __hash__-metoden
Python kaller __hash__(key) for å beregne et heltall fra nøkkelen og tar deretter dette heltallet modulo tabellstørrelsen for å finne bøtteindeksen. Innebygde typer som int, str og tuple har raske, innebygde hashimplementasjoner. list og dict kan ikke hashes (de er mutable, og endringer i dem ville gjort en lagret hash ugyldig).
En god hashfunksjon fordeler nøklene jevnt, er deterministisk og er rask å beregne. Pythons string-hash randomiseres mellom kjøringer (en sikkerhetsfunksjon) — bruk PYTHONHASHSEED=0 for å deaktivere dette når De trenger reproduserbare testresultater.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Kollisjoner: når to nøkler hashes til samme bøtte
En kollisjon oppstår når to ulike nøkler gir samme bøtteindeks. Kollisjoner er uunngåelige (dueprinsippet: uendelig mange nøkler, men et begrenset antall bøtter). To standardstrategier for å håndtere dette er lenking og åpen adressering. Python bruker en variant av åpen adressering med pseudotilfeldig probing.
Ved lenking lagres en lenket liste (eller et dynamisk array) i hver bøtte; alle nøkler som kolliderer i den bøtten, danner en lenke. Ved åpen adressering søkes den neste ledige bøtten i henhold til en probesekvens.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneÅpen adressering: lineær probing
Ved lineær probing undersøker map-en i+1, i+2, ... (med innrulling til starten) når det oppstår en kollisjon ved indeks i, helt til den finner en ledig plass. Oppslag må følge den samme sekvensen for å finne nøkkelen. Sletting krever en «gravstein»-markør i stedet for å tømme plassen, slik at probesekvensen ikke brytes.
Klyngedannelse er den største ulempen: Når det først har dannet seg en klynge av fylte plasser, utvider fremtidige innsettinger i dette området klyngen, og ytelsen nærmer seg O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Lastfaktor og endring av størrelse
Lastfaktoren er forholdet mellom antall lagrede oppføringer og total kapasitet: α = n/m. Når α øker, øker sannsynligheten for kollisjoner, og ytelsen blir dårligere. Python endrer størrelsen på dict (dobler kapasiteten) når lastfaktoren overstiger omtrent 2/3. Ved endring av størrelse hashes alle eksisterende oppføringer på nytt inn i den nye, større tabellen — en O(n)-operasjon som skjer sjelden, slik at den amortiserte kostnaden for insert forblir O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) i gjennomsnitt mot O(n) i verste fall
Med en god hashfunksjon er kollisjoner sjeldne, og den forventede lengden på lenkene er konstant uavhengig av n. Oppslag, innsetting og sletting er derfor O(1) i gjennomsnitt. En situasjon i verste fall — for eksempel et bevisst fiendtlig input som mapper alle nøkler til samme bøtte — reduserer imidlertid alle operasjoner til O(n). Pythons randomiserte hash-seed reduserer risikoen for dette angrepet, men fjerner ikke verste fall teoretisk sett.
I intervjuanalyser bør De si: «O(1) i gjennomsnitt, O(n) i verste fall på grunn av kollisjoner.»
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyPython dict kontra defaultdict og Counter
Python tilbyr tre hash map-varianter som det er verdt å kjenne til. dict er en map for generelle formål; tilgang til en manglende nøkkel utløser KeyError. defaultdict(factory) returnerer en standardverdi ved tilgang til en manglende nøkkel (nyttig når De samler elementer i lister eller teller). Counter er en spesialisert subklasse for telling av hashbare objekter; den støtter også aritmetiske operasjoner mellom tellere.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionHash map kontra hash-sett
Et hash-sett lagrer bare nøkler (ingen tilknyttede verdier) og støtter medlemskapstest, innsetting og sletting på O(1). Pythons set er et hash-sett. Bruk et sett når De bare trenger å svare på «finnes dette elementet?» uten å lagre tilknyttede data. Bruk en dict når De trenger å knytte verdier (antall, resultater og så videre) til nøkler.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementering av en hash map fra grunnen av (intervjuvariant)
Intervjuere ber Dem noen ganger om å implementere en enkel hash map. De viktigste komponentene er et array med bøtter i fast størrelse (bruk 16 eller 1024), der hver bøtte er en liste med (key, value)-par for lenking, en hashfunksjon (bruk Pythons innebygde hash % capacity), og endring av størrelse når lastfaktoren overstiger 0.7. Hvis De nevner endring av størrelse og lastfaktor på eget initiativ, viser det dybdekunnskap.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedNår hash maps mislykkes: nøkler som ikke kan hashes
Bare hashbare objekter kan brukes som nøkler i en dictionary. I Python er et objekt hashbart hvis det har en __hash__-metode og en __eq__-metode, og hashverdien ikke endres i løpet av objektets levetid. Lister, sett og dict-er er mutable og kan derfor ikke hashes. Tupler og frozensets er hashbare alternativer til lister og sett når de brukes som nøkler.
En vanlig intervjufelle: Når De grupperer anagrammer, må De bruke en sortert tuple (ikke en sortert liste) som dict-nøkkel.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Oppsummering: hash map-kompleksitet
Hash maps gir O(1) i gjennomsnitt for innsetting, sletting og oppslag — grunnlaget for mange optimale intervjuløsninger. De viktigste forutsetningene er at en god hashfunksjon fordeler nøklene jevnt, at lastfaktoren holdes begrenset (endring av størrelse opprettholder dette), og at nøkkelobjektene er uforanderlige og hashbare. Når disse forutsetningene holder, konverterer hash maps lineære O(n)-gjennomganger til oppslag på O(1), slik at løsninger som two-sum kan utføres på O(n) i stedet for O(n²).
Kort kontroll
Test forståelsen Deres av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De at en hash map mapper nøkler til bøtteindekser ved hjelp av en hashfunksjon og oppnår operasjoner på O(1) i gjennomsnitt, at kollisjoner håndteres med lenking (lenket liste per bøtte) eller åpen adressering (probing etter neste ledige plass), og at bare uforanderlige, hashbare objekter kan brukes som dictionary-nøkler — bruk tupler i stedet for lister når De trenger en sekvens som nøkkel. Neste tema er two-sum og de mange variantene som forekommer i intervjuer.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Interne detaljer i hashfunksjoner og kollisjonshåndtering» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Interne detaljer i hashfunksjoner og kollisjonshåndtering», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Interne detaljer i hashfunksjoner og kollisjonshåndtering»?
Forstå hvordan Python hasher objekter, hvordan open addressing og chaining løser kollisjoner, og hvorfor O(1) i gjennomsnitt kan forfalle til O(n). Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Interne detaljer i hashfunksjoner og kollisjonshåndtering»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Interne detaljer i hashfunksjoner og kollisjonshåndtering
- Two-Sum og de mange variantene
- Frekvenstelling og gruppering
- Lengste sammenhengende sekvens og LRU-cache