HASHING Flashcards
(9 cards)
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)
