Vad är skillnaden mellan en matris och en hashtabell i ett programmeringsspråk?


Svar 1:

Hashtabeller använder matriser. Arrays har en viktig egenskap för hashing: du kan komma åt alla element i en konstant tid om du känner till dess index.

Du kan använda matriser för hinkar. Låt oss säga att du ville att du skulle räkna upp hur många av varje bokstav i en text, säg, för att designa något som Morse-kod. Du skapar en matris med 26 poster (för det enkla okaccenterade romerska alfabetet). När du ser en bokstav beräknar du indexet och går till den posten i matrisen.

Hashtabeller förlänger detta för godtyckligt långa nycklar. Du beräknar en hash av nyckeln och går till det indexet. Problemet är när flera tangenter har samma hash. Det finns olika sätt att hantera detta, av vilka några besegra hashens syfte (men är lätta att genomföra). Vissa av dem inte och upprätthåller den konstant tid egendom, åtminstone i genomsnitt.

Det bästa jag har sett är att add-the-hash-omväxlingen, som om minnet fungerar från decennier sedan visade sig att Gonnet och Munroe visade sig ha i genomsnitt lite mer än fyra åtkomster med en lastfaktor på 50%, oavsett storlek på hashbord. Detta kräver dock användning av primtal och det gör det svårt att genomföra. Du måste hitta de främsta siffrorna på något sätt. Lyckligtvis blir hashbord inte så stora att det blir löjligt.