Hashmap tidskompleksitet og C ++

“Tidskompleksitet er den relative kjøretiden til litt koding. Før han diskuterer tidskompleksiteten til et hashmap, må leseren kjenne rollen som en hasjfunksjon i et hasjkart.

I teorien vil en hasjfunksjon konvertere data av alle størrelser (enhver stor tekst) til et helt tall som er større eller lik null. Ulike store tekster konverteres til forskjellige tall. Interessen for denne artikkelen er ikke å konvertere stor tekst til et heltall. Interessen for denne artikkelen er å kartlegge data i alle størrelser til et helt tall. Dette inkluderer muligheten for å kartlegge (konvertere) et enkelt tall til et annet enkelt tall.

Data (til venstre) som skal kartlegges kalles nøkler. Så hver tast konverteres til et helt tall som er lik eller større enn null. Se for deg at det er fem nøkler som er konvertert til tall: 0, 1, 2, 3 og 4. Hvis disse nøklene er indeksene for en matrise som har fem verdier av samme type, er disse tastene blitt kartlagt til fem forskjellige verdier.

Og så, hva er et hashmap (hashkart)? Et hashmap er en datastruktur som består av nøkkel/verdipar, der hver tast er kartlagt til en verdi. Egentlig er hver tast blitt hasjet inn i en rekke av en matrise, og den tilsvarende arraycellen er å holde en verdi. I hashmap -emnet kalles stedet for cellen til hver matriseindeks en bøtte.”

Kollisjonsproblem og oppløsning

I praksis kan forskjellige nøkler kartlegges til mer enn en verdi. Vurder tilfellet med ti nøkler for en rekke lengde 5, med 5 bøtter. I dette tilfellet ville en struktur som en array-of-garrays bli konstruert. Hver bøtte ville faktisk være en rekke lengde 2. To nøkler ville dele den samme bøtta. I denne delingen vil den første tasten kartlegge til det første matriseelementet for bøtta, og den andre tasten ville kartlegge til det andre arrayelementet for samme bøtte. Denne ordningen løser kollisjonsproblemet, og ti nøkler er kartlagt til 10 verdier, som forventet.

Forsøk en hashmap med kollisjonsproblemet for resten av denne artikkelen. Målet med denne artikkelen er å gi tidskompleksiteten til kodingen for innsetting i et hashmap, koding for sletting i et hashmap, og kode for å søke i et hashmap. Tidskompleksiteten for hashmap er beskrevet med disse tre funksjonene. Hash-kartlegging for C ++ er også adressert i denne artikkelen.

Nøkkel/verdi par og verdi_type

Se for deg et hashmap av navn på mennesker mot telefonnumre for en telefonkatalog. Navnene på telefonbrukere er av datatype, tekst (streng). Verdiene for telefonnumre er av datatype og tekst, forutsatt at mellomrom og/eller bindestreker er tillatt i et telefonnummer. Brukernavnene er nøklene, og telefonnumrene er verdiene. Ikke glem at tastene internt konverteres til matriseindekser i datastrukturen. Så nøkkeltypen er tekst, og verdypen er fremdeles tekst.

Verditype betyr nøkkel/verdiparet som et element. I C ++ er hvert element (par) pekt på av en iterator. Så i C ++ er det også iterator/par -kartlegging. Et par (nøkkel og verdien) blir referert til som en verditype.

Tidskompleksitet for hashmap -innsetting

Tidskompleksiteten for et hashmap refererer ikke til tiden det tar å lage hashmap. Det refererer til tiden det tar å sette inn, slette eller søke etter en verdi basert på en gitt nøkkel. Tidskompleksitet er normalt skrevet ved hjelp av Big-O-notasjonen. Big-O-notasjonen består av O i store bokstaver, etterfulgt av parenteser. I parentesene er variabler og tall, som gir den relative kjøretiden for et stykke kode og ikke nødvendigvis hele programmet. Med hashmap betyr k antall nøkler, og n betyr antall bøtter. Husk at med noen hashmaps kan en bøtte ha mer enn én verdi for tilsvarende forskjellige nøkler. I dette tilfellet blir mer enn en nøkkel hasjet inn i samme bøtteindeks. Et godt hashmap løser denne kollisjonen.

Innsetting

Gitt en ny nøkkel, er gjennomsnittlig sakens tidskompleksitet som har nøkkelen og den tilsvarende verdien satt inn i en hashmap-datastruktur:

O (1 + n/k)

Hvor n er antall bøtter og k er antall nøkler. For eksempel n kanskje 10, og k kanskje 5. I denne spesielle situasjonen er noen bøtter tomme (har ingen verdi). Så antall operasjoner vil være, 1 + 10/5 = 1 + 2 = 3. Det vil si at det ville være 3 kodingsoperasjoner for å sette inn et nøkkel-/verdiparelement (gitt nøkkelen). Gitt en ny nøkkel og verdi, er den verste tidskompleksiteten til å ha nøkkelen og den tilsvarende verdien satt inn i en hashmap-datastruktur:

På)

Der N er antall bøtter for N -operasjoner, hvis hashmap tar mer enn en verdi per bøtte for mer enn en nøkkel, er det ubetydelig og forsømt å sette inn en ytterligere verdi i samme bøtte og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt og forsømt.

Sletting

Gitt en nøkkel som allerede er i hashmap -datastrukturen, sletter sletting av nøkkelen/verdiparelementet. Gjennomsnittlig tidskompleksitet for sletting er:

O (1 + n/k)

Hvor n er antall bøtter og k er antall nøkler. For eksempel n kanskje 10, og k kanskje 5. I denne spesielle situasjonen er noen bøtter tomme (har ingen verdi). Så antallet operasjoner for slettingskoden, ville være, 1 + 10/5 = 1 + 2 = 3. Så her ville det være 3 kodingsoperasjoner for å slette et nøkkel/verdiparelement, gitt nøkkelen.

Den verste tidskompleksiteten for sletting, gitt en nøkkel, er:

På)

Der N er antall bøtter, så hvis det er N -bøtter for hashmap -datastrukturen, vil det være 10 operasjoner å slette et nøkkel-/verdiparelement i Hashmap.

Søker

Å søke betyr å finne nøkkelen/verdiparelementet som har den gitte nøkkelen, som allerede skal være i hashmap. Gjennomsnittlig tidskompleksitet for dette er:

O (1 + n/k)

Med argumentene som har samme betydning som ovenfor. Den verste tidskompleksiteten for dette er:

På)

Med argumentet som har samme betydning som ovenfor.

C ++ 20

Har C ++ 20 en hashmap -klasse? - Vel, ja, men ikke med navnet, hashmap. C ++ 20 har fire uordnede assosiative containere, som er forskjellige former for hashmap -klasser. Containerne er: uordnede_map, uordnede_multimap, uordnede_set og uordnede_multiset. Disse assosiative containerne er i C ++ 20 standardbibliotek. Den assosiative beholderen som skal vurderes i denne artikkelen er uordnede_map. UnorDeD_map bruker en standard hasjfunksjon levert av C ++ standardbiblioteket.

For å inkludere uordnede_map -overskriften til et program, bruk direktivet,

#inkludere

Ikke bruk #include, som vil omfatte ordre_map. C ++ tar ikke #include . UNORDERED_MAP -overskriften bringer den uordnede_map -klassen inn i C ++ -programmet.

Sett inn med c++

Følgende kodesegment i C ++ hovedfunksjonen vil sette inn et nøkkel/verdiparelement (navn og telefonnummer) i det uordnede_map -objektet, UMP:

#inkludere
uordnede_map ump;
ump.Sett inn ("John Rambo", "555-5555");

Slett med c++

Syntaksen for å slette et nøkkel/verdiparelement fra et uordnede_map -objekt, gitt nøkkelen, k, er:

en.Slett (k)

Hvor "A" er det uordnede_map -objektet (for eksempel UMP ovenfor), og Erase () er den uordnede_map -medlemsfunksjonen.

Søker

Syntaksen for å søke på et nøkkel-/verdiparelement i et uordnede_map -objekt, gitt nøkkelen K, som allerede skal være i det uordnede_map, er:

b.finn (k)

Hvor B er det uordnede_map -objektet (for eksempel UMP ovenfor), og finn () er den uordnede_map -medlemsfunksjonen.

Konklusjon

Tidskompleksitet betyr relativ kjøretid for litt kode. Selv om tidskompleksiteten for å lage et hashmap kan bestemmes, er tidskompleksiteten for å sette inn, slette og søke oppgaver når man arbeider med hashmap. Gjennomsnittlig og verre casetidskompleksitet for en veldefinert hashmap-innsats er:

O (1 + n/k)
På)

Gjennomsnittlig og dårligere casetidskompleksitet for en veldefinert hashmap-sletting er:

O (1 + n/k)
På)

Gjennomsnittlig og verre casetidskompleksitet for et veldefinert hashmap-søk er:

O (1 + n/k)
På)