Den kodeløse guide til hash- og hasjborde

Hvis du har programmeret før, er du sikker på at være stødt på hashing- og hash-tabeller. Mange udviklere har brugt hash-tabeller i en eller anden form, og nybegynderudviklere skal lære denne grundlæggende datastruktur. Der er kun et problem:

Alle de selvstudier, du støder på, diskuterer sikkert hashing- og hash-tabeller i JavaScript, Python eller et andet programmeringssprog.

Hvad dette betyder er, at du måske forstår lidt om, hvordan hashing fungerer, og hvordan man bruger en hash-tabel på [indsæt sprog her], men måske går glip af principperne for, hvordan det fungerer.

Ville det ikke være godt, hvis vi kunne lære om hash uden at kende noget bestemt sprog? Hvis du ved, hvordan hashing fungerer, og hvad en hash-tabel er, bør sproget ikke have noget at gøre.

Det er den kodeløse tilgang, og i dette indlæg vil jeg lære dig alt om hashing og hash-tabeller uanset hvilket programmeringssprog du bruger i øjeblikket. Uanset om du er junior eller seniorudvikler, vil alle lære noget af dette indlæg.

Så hvad er en Hash-funktion alligevel?

Før vi går ind på alle de smarte ting, lad mig fortælle dig, hvad hashing er. Lad os forestille os, at vi har en sort kasse for at gøre det let:

Denne sorte boks er speciel. Det kaldes en funktionsboks. Vi kalder det et funktionsfelt, fordi dette felt kortlægger en uafhængig variabel på indgangen til en afhængig variabel på udgangen (det lyder matt, men bær mig).

Vores funktionsboks fungerer sådan: hvis vi lægger et bogstav i kassen, får vi et tal ud. Da vores boks er en funktionsboks, kan der kun være en udgang for hver indgang i boksen.

Vores funktionsboks tager et bogstav fra AJ på input og output et tilsvarende antal fra 0 til 9 på output. Så hvis vi indtaster C, får vi 2 på udgangen.

Dette danner det grundlæggende i, hvad en hash-funktion er. Hashfunktionen tager det dog et skridt videre. Vi kortlægger data på input til en vis numerisk værdi på output, normalt en hexadecimal sekvens.

Så alt hvad hashing gør, er, at det bruger en funktion til at kortlægge data til en repræsentativ numerisk eller alfanumerisk værdi. For hash-funktionen, uanset størrelsen på input, forbliver output altid den samme.

Hvad med Hash-tabeller?

Så på dette tidspunkt undrer du dig måske over, hvad et hashbord er. Hash-tabeller bruger hashing til at danne en datastruktur.

Hash-tabeller bruger en associerende metode til at gemme data ved at bruge det, der er kendt som et nøgleværdisøgningssystem. Alt, hvad der betyder er, at nøglerne i en hash-tabel kortlægges til unikke værdier.

Dette system til organisering af data resulterer i en meget hurtig måde at finde data effektivt på. Dette skyldes, at da hver nøgle er kortlagt til en unik værdi - når vi først kender en nøgle, kan vi straks finde den tilknyttede værdi.

Hash-tabeller er ekstremt hurtige og har en tidskompleksitet, der er i rækkefølgen af ​​O (1).

Forvirret? Se på dette diagram, hvor vi har flere funktionsfelter, der genererer hash-værdier.

I dette scenarie har hvert tegn på input (hver er en nøgle) anvendt en hash-funktion, og hash-funktionen i funktionsboksen genererer hash-værdien. Denne resulterende værdi kortlægges derefter til et indeks i den underliggende sammenkædede liste eller det array, der bruges til at implementere hash-tabellen.

Den resulterende struktur vil se sådan ud:

Hash-kollisioner

Dette er et godt tidspunkt at tale om kollision i hash-funktioner og hash-tabeller.

En funktion i matematik er ideel, idet et element i inputet kortlægges til nøjagtigt et element i output.

I en hash-funktion er det dog ikke altid sådan. Nogle gange kan forskellige hash-værdier i input producere den samme hash-værdi i output. Når dette sker, får du det, der kaldes en hash-kollision.

Hash-kollisioner er ikke særlig almindelige i de fleste brugssager, da en lille ændring i input kan producere en dramatisk forskellig output. Men jo flere data du skal indtaste til hash-funktionen, jo mere sandsynligt er der en kollision.

I eksempelet hash-tabel, som vi leverede tidligere, antog vi, at en matrix blev brugt til at implementere hash-tabellen. Selvom dette er godt for enkle hash-tabeller, er disse i praksis ikke særlig gode til håndtering af kollisioner.

Som sådan anvendes en metode kendt som kæde. Hvis hash-tabellen returnerer den samme hash-værdi for flere elementer i sammenkædning, "kæder" vi blot elementerne sammen med de samme hash-værdier ved det samme indeks i hash-tabellen.  

I stedet for at blive implementeret som en matrix med et indeks implementerer vi hash-tabellen ved hjælp af en sammenkædet liste, hvor hvert element er en liste i stedet for blot at have en enkelt værdi tildelt.

Men når kædens længde øges, kan hash-bordets tidskompleksitet blive værre. En metode kendt som åben adressering anvendes også. I den findes alternative placeringer i den underliggende datastruktur, der implementerer hash-tabellen. Bare husk, at denne metode vil reducere hash-bordets effektivitet og har en dårligere tidskompleksitet.

Er Hashing det samme som kryptering eller kodning?

Mange mennesker har tendens til at forbinde hashing med kryptering eller kodning. Så er hashing-kryptering? Er det det samme som kodning?

Ser du, i kryptering forvirrer vi data, så kun en person med nøglen, der er nødvendig for at dekryptere dataene, har adgang til dem. Når vi bruger en krypteringskryptering, gør vi ikke kun dataene krypterede, men vi vil også dekryptere dataene på et eller andet tidspunkt. I kryptering ønsker vi at gendanne de originale data.

Hashing på den anden side tager data og producerer et output med det formål at bekræfte dataintegriteten. I hashing har vi ikke til hensigt at gendanne de originale data.

Kodning adskiller sig fra kryptering og hashing ved, at målet med kodning ikke er at skjule data til ethvert sikkerhedsformål, men blot at konvertere dataene til et format, som et andet system kan bruge.

Hvad kan jeg gøre med Hashing?

Hashes og hash-tabeller har mange anvendelser! Disse inkluderer:

  1. Kryptosystemer
  2. Cyklisk redundanskontrol
  3. Søgemaskiner
  4. Databaser
  5. Kompilatorer

Eller ethvert system, der har en kompleks opslagsproces.

Afslutter

I dette indlæg har vi dækket det grundlæggende med hashing, alt sammen uden at skrive en eneste linje kode! Dette var let, ikke? Den kodeløse tilgang er en meget lettere måde at lære om disse grundlæggende emner på.

Vi lærte, at hash-funktioner kan bruges til at konvertere objekter til en alfanumerisk output med fast længde. Vi lærte også, at hash-tabeller er nøgleværdisøgningssystemer, og selvom de fungerer godt, er de ikke perfekte og undertiden lider af kollisioner.

Ved afslutningen af ​​dette indlæg skal du kende forskellen mellem hashing, kryptering og kodning og også have en idé om, hvor hashes kan bruges.

Kunne du lide den kodeløse tilgang? Vil du gå videre?

Lær om hash-tabeller og andre datastrukturer og algoritmer i bogen "Kodeløse datastrukturer og algoritmer". Du får en udvidelse af det, der blev dækket i dette indlæg, og lær om mange flere emner, alt sammen uden at skrive en eneste linje kode!

Kodeløse datastrukturer og algoritmer - Lær DSA uden at skrive en enkelt kodelinje | Armstrong Subero | Apress Denne bog giver dig et nyt perspektiv på algoritmer og datastrukturer, helt kodefri. Lær om datastrukturalgoritmer (DSA'er) uden nogensinde at skulle åbne din kodeditor, bruge en compiler eller se på et integreret udviklingsmiljø (IDE) .... Armstrong Subero Søgemenu Indkøbskurv V Din indkøbskurv er i øjeblikket tom. Login konto Bogreol Login Apress Access