IN2010 Gruppe 4

Uke 9

Hashing!

Er en nyttig teknikk, som vi kan bruke for å lage effektive mengder.

Brukes f.eks. i hashmaps, og er hovedgrunnen til at disse er så raske.

Hashing!

Vi ønsker å ha god kjøretidskompleksitet for:

• innsetting
• oppslag
• sletting

Hashing!

Hashing er tredelt:

1. Gjøre om verdier av forskjellige slag til tallverdier
2. Håndtering av når forskjellige verdier får tildelt samme tallverdi
3. Passe på å balansere størrelsen på arrayet vårt, for å minimere kjøretidstap

Del 1: Hashfunksjoner

• MÅ gi samme output hver gang den får samme input
• Dvs. må kun avhenge av inputverdien(e), og ikke av noe annet
• Får en nøkkel k, og et heltall N som input
• N representerer hvor stor array du har underliggende, vil endre seg når man gjør rehashing
• Returnerer et heltall mellom 0 og N (en indeks)
• En god hashfunksjon gir ikke ofte samme svar for to forskjellige inputs (men kan ikke helt unngå å gjøre dette)
• Må lages for enhver datatype du ønsker å hashe

Del 2: Håndtere kollisjoner

To metoder vi skal se på:

• Separate chaining
• Hver indeks av arrayet vårt har en lenket liste bak seg, hvor vi setter elementer som får lik hashfunksjon-output.
• Linear probing
• Bruker kun selve arrayet - om en plass er full, må man sette inn på neste ledige plass (Dette har konsekvenser man må tenke på)

Separate chaining

Linear probing eksempel

2

2

Del 3: Balansering og effektivitet

Viktig å ha en ‘god’ størrelse på arrayet vårt for å sikre effektivitet

Hvordan vet vi hva som er godt?

Load factor sier noe om hvor fullt arrayet vårt er

• antall elementer delt på antall plasser i arrayet (n/N)
• Som regel ønsker vi et sted mellom ½ og ¾ som load factor

​

Balansering: Rehashing

Må gjøres en gang i blant når vi får så mange elementer at kollisjoner blir vanlige

Består av å lage et helt nytt array med en ny størrelse, og å flytte alle elementene inn i dette

Lineær tid

​

Amortisert tid

Iblant når vi gjør en insetting må vi også gjøre rehashing (O(n))

Dette fører til at verste-tilfelle kjøretid for innsetting blir lineær tid!

MEN dette vil jo ikke være tilfellet for de fleste av innsettingene! - derfor har vi uttrykket amortisert tid.

Det vil si at vi aksepterer at det en gang iblant blir verre kjøretid, men dette er jo på grunn av at vi har gjort veldig mange tidligere (raske) innsettinger! Hvis vi tenker at disse raske innsettingene ‘betaler’ litt av denne tidskostnaden, får vi det vi kaller amortisert tid.

Vi sier derfor at Hashmaps har amortisert konstant tid på innsetting.