Lage god hash-funksjon

[Lily]

Jeg skal lage en hash-funksjon for ord (ordliste). Arrayet disse legges i skal være 10 ganger så langt som antall ord (15000/150000). Hvordan skal jeg få til dette uten at flere ord kan gi samme verdi? Jeg skal i tillegg kunne søke opp igjen ordet v.h.a. hash-verdi etterpå, så det hjelper ikke å bare lete etter tomme plasser i arrayet heller...

 

Help..!

Endret 21. september 2006 av Lily

[FJERNET111]

De ordene du har i arrayet har jo, hvis de er strenger, allerede en innebygget hash-funksjon i seg.

 

F.eks.

 

streng.hashCode()

 

Og hvorfor skal arrayet være ti ganger så stort som antall ord? Skal du lage en ny hashcode på bakgrunn av plassering i arrayet eller? Ellers høres det vitterlig ut som sløsing av plass og minne.

 

Er heller ikke noe problem å traversere hele arrayet med en for-løkke der input-verdien er hashcoden til ordet du vil søke opp. Det tar selvfølgelig en del tid å gjøre det på denne måten da (O(n) tid hvis jeg ikke tar feil og det kan ta sin tid hvis du har så store arrays).

 

Hvorfor ikke bare søke etter selve ordet i arrayet i stedet for å bruke en hashcode? Hvordan vet du på forhånd hvilken hashcode du skal søke etter (pleier ikke akkurat være så enormt intuitive de tallene der)?