[NOISE].
Før dykking i hash tabeller, la oss
først gjennom fordeler og ulemper av noen
enklere datastrukturer, som starter med
arrays.
Husker at arrays tillate oss å lagre
elementer av en enkelt datatype
contiguously i minnet.
Fordi hvert element er forbundet med
en indeks, eller plassering,
Vi har direkte tilgang til alle
elementer i en matrise.
Med andre ord, kan vi få tilgang til noe element
i et enkelt trinn ved å indeksere inn i det
array.
Dette er en stor avtale, fordi algoritmer
som binære søk avhenge av tilfeldig
tilgang.
En ulempe av matriser er at deres størrelse
er fast.
Fordi arrays lagre data contiguously i
minne, må du angi en rekke størrelse
når du erklærer matrisen.
Du er effektivt å spørre drifts
system for å reservere det aktuelle beløpet
minne for tabellens elementer.
Det er ingen garanti for at mer minne,
ved siden av din array, vil være tilgjengelig
for senere bruk.
Så arrays kan ikke lett vokse.
Husker at vi også lært om koblede
lister, som kan vokse fordi deres
elementer er ikke sammenhengende i minnet.
Hver node i en lenket liste inneholder
element som vi ønsker å oppbevare, samt
en peker til den etterfølgende element i
listen.
Dessverre, den prisen vi har betalt for
dynamisk størrelse er tilfeldig tilgang til
elementer.
For å få tilgang til et visst element,
det er nødvendig å traversere hele
listen inntil det ønskede element er
nådd.
Så, hvis jeg leter etter antall 9, hadde jeg
følg pekere fra node til node,
sjekke om verdien av hver node
er lik 9.
Som sådan, i verste fall, slå opp er
O (n), som er langt fra effektiv.
Kan vi gjøre det bedre enn O (n) mens de fortsatt
slik at vår datastruktur for å vokse over
tid?
Hash tabeller tilby en løsning.
Hash tabeller brukes når rask
innsetting, sletting, og oppslag av
elementene er prioritert.
I teorien, innsetting, sletting, og oppslag
kan til og med bli oppnådd i konstant
tid.
Så, hva er en hash table likevel?
En hash table er bare en matrise kombinert
med en funksjon, som vi vil kalle den hash
funksjon.
Hash-funksjonen tar en bit av data
som input, vil vi kalle dette en nøkkel, og
sender ut et helt tall, ofte referert til
som en hash-verdi.
Hash-verdi kartene våre nøkkelen til en
Særlig indeksen i hash table.
Du ville i utgangspunktet bruke hash-funksjon for å
bestemme hvor i hash tabellen til
lagre en gitt nøkkel.
Senere vil du bruke den samme hash-funksjon
å bestemme hvor i hash tabellen til
søke etter en gitt nøkkel.
Av denne grunn er det avgjørende at en hash
funksjon oppfører seg konsekvent og utganger
samme hash-verdi for identiske nøkler.
Vet at hash tabeller kan brukes til
lagre data av alle typer.
Men for å forenkle ting, vil vi fokusere på
strenger for nå.
Her er en enkel hash-funksjon for strenger.
Denne hash-funksjon beregner en hash
funksjon basert på den første bokstaven i
tasten.
"Apple" begynner med bokstaven "A", så det er
kartlagt til indeks 0 i hash tabellen.
Tilsvarende er "banan" kartlagt å indeksere en,
og "cat" er kartlagt til å indeksere to.
Hvis en venn spør om ordet "hund" er i
bordet, vil vi input "hund" i hash
funksjon, som vil sende ut en hash-verdi
av tre.
Siden "hund" ikke lagres på indeks 3, vi
kan trygt si at "hunden" er ikke
i tabellen
selv om vi har bare sjekket en av de
hash tabellen 26 indekser.
Tid for å kaste en nøkkel inn i ting.
Hva hvis vi ønsker å lagre "maur" inn i
tabellen også?
"Ant" hasher til indeks 0, akkurat som "eple" gjorde.
Dette er et eksempel på en kollisjon, er
produktet av to nøkler hashing til samme
indeks.
Selv om din hash tabellen er større enn
loggeren med, og du har valgt en god
hash-funksjon,
du fortsatt trenger en plan for å håndtere
kollisjoner, hvis og når de oppstår.
La oss diskutere fordeler og ulemper med to
vanlige metoder for å løse kollisjoner:
lineær sondering og separat kjeding.
Med lineær sondering, hvis en nøkkel hashes til
samme indeks som den tidligere lagret
nøkkel, er det tildelt den neste tilgjengelige
spalte i tabellen.
Så, er "maur" nå lagret på index 3, siden
indekser 0, 1 og 2 allerede var i bruk.
Og hvis vi prøver å lagre et tredje ord som
starter med bokstaven "A", er det tildelt
å index 4, ettersom indekser 0, 1, 2 og 3.
er full.
Som du kan se selv fra denne enkle
eksempel når det oppstår en kollisjon, du
betydelig øke sjansene for at
en annen kollisjon vil skje i samme
området.
Dette kalles clustering, og det er en
alvorlig ulempe til lineær sondering.
Videre worst-case innsetting, sletting,
og oppslags ganger har delegert til O (n),
som den neste tilgjengelige sporet kan ha
potensielt vært den siste spalte i tabellen.
Kanskje separat kjeding vil tilby en mer
overbevisende løsning.
I separat kjeding modell, hash
Tabellen er faktisk en rekke pekere til
lenkede lister.
Når det oppstår en kollisjon, kan nøkkelen bli
innsatt i konstant tid på hodet av
riktig lenket liste.
Hva skjer nå når vi søker etter "apple"
i hash table?
I verste fall må vi traversere
Hele lenket liste, starter på indeksen 0.
Den verst tenkelige oppslag tid for en hash
tabell som bruker separat kjeding er
Derfor O (n / k), der k er
Størrelsen på hash-tabellen.
Vent litt, er k en konstant.
Så O (n / k) er egentlig bare O (n),
som var det verst tenkelige oppslag tid for
en lenket liste.
Har vi virkelig gått gjennom alle
bryet med å lære om hash tabeller
bare for å ende opp tilbake der vi startet?
Det kan være tilfelle fra en teoretisk
perspektiv, men i den virkelige verden,
O (n / k) kan være en stor forbedring i forhold til
O (n).
Tenk på det på denne måten: anta at k er
10 - ville du heller vente 100 sekunder
eller 100 / k?
10 sekunder fra Microsoft Word til å fullføre
stavekontroll dokumentet.
Som du nettopp så, løse kollisjoner
innebærer en form for lineær søk eller
en annen, noe som bremser ned ting
betraktelig.
Derfor, vil du ønsker å velge en hash
funksjon som minimerer sjansen for
kollisjoner oppstår i første omgang.
Her er noen egenskaper ved god hash
funksjoner for å huske på.
En god hash-funksjon bør gjøre bruk av
all informasjon gitt av en gitt nøkkel
for å maksimere antallet
mulige hash verdier.
For eksempel, hvis vi hadde to strenger, "katt"
og "caterpillar", ville vi vil ha dem til hasj
til forskjellige steder på bordet.
Hvis en hash-funksjon bare tok hensyn
den første en, to, eller tre bokstaver
av strengene, vil en kollisjon oppstår
siden begge ord starter med den samme
tre bokstaver.
Hash verdier skal fordeles jevnt
over hash tabellen.
Dette vil redusere lengden på koblede
listene bør kollisjoner oppstår.
Det er også et godt tegn hvis hash-verdi
er i stand til å generere svært forskjellige
hash verdier for tilsvarende tastene,
gjør kollisjoner mye mindre sannsynlig.
Vårt mål er rask innsetting, sletting,
og oppslag.
Hash-funksjon spiller en avgjørende rolle i
hver av disse prosesser og vil bli
kalles veldig ofte.
Derfor, sørg for at den sysselsetter bare veldig
enkle, raske operasjoner for å minimere løp
tid.
Jeg håper du har hatt glede av denne korte
introduksjon til hasj tabeller.
Mitt navn er Lauren, og dette er CS50.