Lær dine grundlæggende kodning: de vigtigste forskelle mellem sæt og arrays

Et spørgsmål, jeg får meget af mine CS-studerende på The Forge, er, hvorfor jeg ofte bruger sæt i stedet for almindelige gamle arrays i interviewproblemer.

For at besvare dette spørgsmål er vi nødt til at forstå de grundlæggende forskelle mellem et sæt og et array.

Hvis du er en visuel elev og foretrækker en videoforklaring, her er en 3 minutters video, der forklarer svaret (omend i mindre dybde).

Arrays var en af ​​de første datastrukturer, jeg lærte at bruge.

Ikke kun er de en grundlæggende datastruktur, der bruges i næsten alle kodningsapplikationer, men de er også ret lette at forstå.

Det var først langt senere i min softwarekarriere, at jeg blev introduceret til arrayets mærkelige, men magiske fætter:

Sættet.

Sæt er som arrays ... bortset fra at de ikke er det.

Lad os hurtigt minde os om, hvordan en matrix fungerer

Arrays:

  • Er bestilt
  • Har indekser, der starter ved 0
  • Kan indeholde duplikatelementer
  • Få et O (n) opslagstid, når du søger efter et element

Sæt opfører sig dog lidt anderledes

Sæt:

  • Er uordnet (på næsten alle sprog)
  • Har hashede indekser
  • Kan IKKE indeholde duplikatelementer
  • Få en O (1) opslagstid, når du søger efter et element

Lad os tage et mere dybtgående kig.

1. Sæt Indsæt ved Hashing

Elementerne i et sæt er gemt helt anderledes end et array.

Den måde, et sæt opbevarer sine elementer på, er ved Hashing.

Lad os sige, at du vil gemme tegnet "A" i et sæt og et array.

Arrayet ville simpelthen finde det næste tilgængelige indeks, medmindre andet er angivet, og placere elementet i det indeks.

Med hashing ser tingene dog lidt anderledes ud.

Sådan fungerer Hashing

Hashing er handlingen ved at tage input (x) ind, forvride det med en bestemt hash-funktion (h) og få en endelig output (y).

Dybest set h (x) = (y)

Ser lidt forvirrende ud, ikke?

Bare rolig! Dette skal rydde op.

Et let eksempel på en hashing-funktion (h) kan være at tilføje "asdf" i slutningen af ​​dit input (x).

Hvis (x) er "A" og tilføjelse "asdf" er (h), vil output (y) simpelthen være som følger:

“A” + “asdf” → “Aasdf”

Så "Aasdf" ville være vores (y).

Så hvordan bruger et sæt Hashing?

Et sæt bruger hashing til at bestemme, hvor dit input (x) skal gemmes.

I en nøddeskal tager et sæt dit input, hasher det og gemmer det på det indeks, der matcher det hashede input, AKA output (y).

Dette er grunden til, at sæt ikke er ordnet på de fleste sprog.

Arrayindeksering er let, 0 til n, så du nemt kan huske, hvad der kommer næste gang.

Men med de komplekse hashing-funktioner, som de fleste compilere bruger, kan rækkefølgen, som elementerne blev indsat i, ikke findes, medmindre du har en sekundær indekseringsmekanisme.

2. Sæt kan ikke indeholde duplikater

Det er rigtigt!

Et sæt kan kun indeholde unikke elementer.

I modsætning til hvordan det lyder, kan dette faktisk være yderst nyttigt i mange situationer, herunder Google Interview-spørgsmål.

Hvorfor gør det det, spørger du?

Nå, på grund af hashing!

Da min hashing-funktion (h) forbliver konsistent, når mit program kører, vil indtastning af det samme (x) altid give dig det samme (y).

Det betyder, at hvis jeg forsøgte at indsætte et andet "A", ville min hashing-funktion sende den samme adresse som den første "A", og den ville simpelthen overskrive den!

Med en matrix tilføjede den simpelthen det andet “A” til det næste tilgængelige indeks.

3. Sæt har en O (1) opslagstid

Lad os sige, at du har en række af n- elementer, hvor n er et stort tal, og du ville se, om "A" eksisterede i den matrix.

Nå, i værste fald, “A” findes ikke.

Og for at finde ud af, ville du nødt til at gentage, gennem alle n af de elementer!

Det giver en Array en tidskompleksitet på O (n), når det kommer til at slå et element op.

Vi kan spare meget tid med et sæt

Hvis vi ville finde ud af, om der findes et element i vores sæt, er alt, hvad vi skal gøre, hash det element og kontrollere indekset!

Husk: Det indeks, et element er gemt i, er forbundet med selve elementet.

Derfor, hvis vi ønskede at se, om “A” eksisterede i vores sæt, skulle vi bare hash det (+ “asdf”) og kontrollere dette indeks!

Da denne proces altid vil tage en konstant mængde operationer, uanset hvor stort sættet er, har det en konstant tidskompleksitet.

Det betyder, at et sæt har en tidskompleksitet på O (1), når det kommer til at slå et element op ... Hvilket er en enorm forbedring!

Kan du tænke på nogen situationer, hvor dette er nyttigt?

Hvis du ikke kan, skal du tjekke dette Google Interview-spørgsmål, hvor et sæt gør hele forskellen!

Tak for læsningen!

.en

PS - For flere datastrukturer og tutorials til algoritmer og interviewforberedelse, se www.TheForge.ca!

Vi hjælper studerende og nye grads med at få deres drømme-softwarejob!