Re: [CPROG] Hash tabel - erklæring og initialisering ??

[Per Vognsen <sslug@sslug>]

At 18:39 05-11-00 +0100, Lamer wrote:
>Er der nogle, der kan fortælle mig, hvordan man opretter en hashtabel og
>indsætter værdier d.v.s. hele syntaksen omkring hashtabeller. En henvisning
>til en internetside ville også kunne bruges.

Der er ingen indbyggede hashtabeller i C. I C++ er der dog nogle STL
containere der tilbyder ordbogsfunktionalitet (map og hashmap - den sidste
er ikke inkluderet i alle STL distributioner). Det burde dog ikke være et
problem at skrive kode og strukturer til din egen hashtabel implementering.

Det er lettest at bruge ekstern kædning: Du har et array af hægtede lister.
Du har en hash funktion der returnerer en værdi (baseret på en nøgle) som
du bruger som indeks, modulo størrelsen af dit array. Så løber du din
hægtede liste igennem indtil du har fundet elementet med den rigtige nøgle.
Det største problem er at finde en hash funktion der giver god spredning.
Hvis du bare ønsker at bruge strenge som nøgler er der dog nogle ok og
lette måder. Prøv at søge på Google.

Hvis du stadig er i tvivl så prøv at kigge i en god bog om algoritmer og
data strukturer. Jeg kan anbefale "Introduction to Algorithms" af Cormen,
Rivest, et al. Pseudokoden i denne bog er relativ simpel at oversætte
direkte til C / C++.

Med venlig hilsen
Per Vognsen