Hva er forskjellen mellom en matrise og en hasjetabell i et programmeringsspråk?


Svar 1:

Hash-tabeller bruker matriser. Arrays har en viktig egenskap for hashing: du kan få tilgang til ethvert element i en konstant tid hvis du vet om indeksen.

Du kan bruke matriser til bøtter. La oss si at du ville at du skulle telle opp hvor mange av hver bokstav i en tekst, si for å designe noe som Morse-kode. Du lager en matrise med 26 oppføringer (for det enkle uaksenterte romerske alfabetet). Når du ser en bokstav, beregner du indeksen og går til den oppføringen i matrisen.

Hash-tabeller utvider dette for vilkårlige lange nøkler. Du beregner en hasj av nøkkelen og går til den indeksen. Problemet er når flere taster har samme hasj. Det er forskjellige måter å håndtere dette på, hvorav noen beseirer hasjens formål (men er enkle å implementere). Noen av dem opprettholder ikke egenskapen konstant tid, minst i gjennomsnitt.

Det beste jeg har sett er at add-the-hash-omvaskingen, som hvis minnet tjener fra flere tiår siden, Gonnet og Munroe viste seg å ha et gjennomsnitt på litt mer enn 4 tilganger med en belastningsfaktor på 50%, uavhengig av størrelsen på hasjbord. Dette krever imidlertid bruk av primtall, og dette gjør det vanskelig å implementere. Du må finne primetallene på en eller annen måte. Heldigvis blir ikke hasjbord så stort at dette blir latterlig.