Datastrukturer och algoritmer Hashfunktioner
Hej,
Jag skulle uppskatta hjälp med en deluppgift som jag inte tycks kunna lösa. Frågan lyder:
och det är deluppgift B som jag behöver hjälp med. I den deluppgiften är rätt svar: 5, 8, 4.
I kursen har jag lärt mig att följande gäller,
Linjär sondering: h(k, i) = (k + i) mod m
Kvadratisk sondering: h(k, i) = (k + i2 ) mod m
Dubbel hashning: h(k, i) = h1(k) + i * h2(k) mod m
Jag har försökt lösa uppgiften själv men får fel index för k=24 (där får jag index=3 när det ska vara 8) så jag fortsatte ej.
Hur löser jag B)?
Du har gjort nästan allt rätt, felet är att du har "+1" utanför uttrycket du multiplicerar med i.
h1(k)+i*h2(k)
Det ska alltså vara:
(k mod 13) + i * (k mod 5 + 1)
Enklast är att göra en tabell med k, (k mod 13) och (k mod 5 + 1). När man ser att (k mod 13) leder till krock multiplicerar man (k mod 5 + 1) med 1, 2, osv tills man får ett ett ledigt index.
Programmeraren skrev:Du har gjort nästan allt rätt, felet är att du har "+1" utanför uttrycket du multiplicerar med i.
h1(k)+i*h2(k)
Det ska alltså vara:
(k mod 13) + i * (k mod 5 + 1)
Enklast är att göra en tabell med k, (k mod 13) och (k mod 5 + 1). När man ser att (k mod 13) leder till krock multiplicerar man (k mod 5 + 1) med 1, 2, osv tills man får ett ett ledigt index.
Tack så mycket för hjälpen!
