[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.