HASHING Flashcards
Hva vil “kollisjon” si innen hashing?
At to nøkler peker på samme verdi
Hva kan definere en funksjon?
At samme input gir samme output HVER gang
Hashing: Hva er “Separate Chaining”?
En ide for kollisjonshåndtering.
Hver plass i arrayet peker på en “bøtte”
Hver “bøtte” er ofte en lenket liste, men man kan også bruke andre datastrukturer, som et binært søketre.
Hashing: Hva er “Linear Probing”?
En ide for kollisjonshåndtering. Bruker kun arrayet. Ved kollisjon ser man etter neste ledige plass i arrayet. Forholdsvis enkelt, men kan være utfordrende å slette elementer.
Hashing: Hva kan skje dersom vi glemmer å tette hullet etter sletting med Linear probing?
Siden alle algoritmene på linear probing terminerer ved en null-verdi, risikerer vi å miste mange elementer
Hva er load factor?
(Størrelsen på arrayet)/(Antall elementer i hashmappen)
Hva er den idelle load factor?
Mellom 0.5 og 0.75. Hashmappen bør dermed bare være litt over halvfull.
Hva er rehashing?
Lage et større/mindre array og sette inn alle elementene fra det forrige dersom arrayet blir for fullt/tomt (load factor)
Hva er O-notasjonen til alle operasjonene på hashmaps?
O(n) (verstetilfellet)
