En introduksjon til Java.util.Hashtable-klasse
1. Oversikt
Hashtable er den eldste implementeringen av en hash-tabell datastruktur i Java. De HashMap er den andre implementeringen, som ble introdusert i JDK 1.2.
Begge klassene gir lignende funksjonalitet, men det er også små forskjeller, som vi vil utforske i denne opplæringen.
2. Når skal du bruke Hashtable
La oss si at vi har en ordbok, der hvert ord har sin definisjon. Vi trenger også å hente, sette inn og fjerne ord fra ordboken raskt.
Derfor, Hashtable (eller HashMap) gir mening. Ord vil være nøklene i Hashtable, ettersom de skal være unike. Definisjoner vil derimot være verdiene.
3. Eksempel på bruk
La oss fortsette med ordbokeksemplet. Vi skal modellere Ord som en nøkkel:
offentlig klasse Word {privat strengnavn; public Word (String name) {this.name = name; } // ...}La oss si at verdiene er Strenger. Nå kan vi lage en Hashtable:
Hashtable-tabell = ny Hashtable ();La oss først legge til en oppføring:
Ordord = nytt ord ("katt"); table.put (ord, "et dyr");Også for å få en oppføring:
Strengdefinisjon = tabell.get (ord);Til slutt, la oss fjerne en oppføring:
definisjon = tabell. fjern (ord);Det er mange flere metoder i klassen, og vi vil beskrive noen av dem senere.
Men først, la oss snakke om noen krav til nøkkelobjektet.
4. Viktigheten av hashCode ()
Skal brukes som nøkkel i en Hashtable, objektet må ikke bryte med hashCode () kontrakt. Kort sagt, like objekter må returnere den samme koden. For å forstå hvorfor la oss se på hvordan hasjbordet er organisert.
Hashtable bruker en matrise. Hver posisjon i matrisen er en "bøtte" som enten kan være null eller inneholde ett eller flere nøkkelverdipar. Indeksen for hvert par beregnes.
Men hvorfor ikke lagre elementer sekvensielt, og legge til nye elementer på slutten av matrisen?
Poenget er at å finne et element etter indeks er mye raskere enn å gjenta elementene med sammenligningen sekvensielt. Derfor trenger vi en funksjon som tilordner nøkler til indekser.
4.1. Direkte adressetabell
Det enkleste eksempelet på slik kartlegging er direkteadressetabellen. Her brukes nøkler som indekser:
indeks (k) = k, hvor k er en nøkkelNøklene er unike, det vil si at hver bøtte inneholder ett nøkkelverdipar. Denne teknikken fungerer bra for heltallstaster når det mulige området for dem er ganske lite.
Men vi har to problemer her:
- For det første er nøklene våre ikke heltall, men Ord gjenstander
- For det andre, hvis de var heltall, ville ingen garantere at de var små. Tenk deg at tastene er 1, 2 og 1000000. Vi har et stort utvalg av størrelse 1000000 med bare tre elementer, og resten vil være bortkastet plass
hashCode () metoden løser det første problemet.
Logikken for datamanipulering i Hashtable løser det andre problemet.
La oss diskutere dette i dybden.
4.2. hashCode () Metode
Ethvert Java-objekt arver hashCode () metode som returnerer en int verdi. Denne verdien beregnes fra objektets interne minneadresse. Som standard hashCode () returnerer distinkte heltall for forskjellige objekter.
Og dermed ethvert nøkkelobjekt kan konverteres til et helt tall ved hjelp av hashCode (). Men dette heltallet kan være stort.
4.3. Redusere rekkevidden
få(), sette() og fjerne() metoder inneholder koden som løser det andre problemet - reduserer rekkevidden av mulige heltall.
Formelen beregner en indeks for nøkkelen:
int index = (hash & 0x7FFFFFFF)% tab.length;Hvor tab.length er matrisestørrelsen, og hasj er et nummer som returneres av nøkkelen hashCode () metode.
Som vi kan se indeks er en påminnelse om delingen hasj etter matrisestørrelse. Merk at like hash-koder gir samme indeks.
4.4. Kollisjoner
Videre til og med forskjellige hash-koder kan produsere den samme indeksen. Vi omtaler dette som en kollisjon. For å løse kollisjoner Hashtable butikker a LinkedList av nøkkelverdipar.
Slike datastrukturer kalles en hash-tabell med kjetting.
4.5. Lastfaktor
Det er lett å gjette at kollisjoner bremser operasjoner med elementer. For å få en oppføring er det ikke nok å kjenne indeksen, men vi må gå gjennom listen og utføre en sammenligning med hvert element.
Derfor er det viktig å redusere antall kollisjoner. Jo større er en matrise, jo mindre er sjansen for en kollisjon. Lastfaktoren bestemmer balansen mellom matrisestørrelse og ytelse. Som standard er det 0,75, noe som betyr at matrisestørrelsen dobles når 75% av skuffene ikke blir tomme. Denne operasjonen utføres av rehash () metode.
Men la oss gå tilbake til nøklene.
4.6. Overstyring er lik () og hashCode ()
Når vi legger inn en oppføring i en Hashtable og få det ut av det, forventer vi at verdien ikke bare kan oppnås med samme forekomst av nøkkelen, men også med en lik nøkkel:
Ordord = nytt ord ("katt"); table.put (ord, "et dyr"); Streng ekstrahert = table.get (nytt Word ("katt"));For å sette reglene for likhet overstyrer vi nøkkelen er lik() metode:
offentlig boolsk er lik (Objekt o) {hvis (o == dette) returnerer sant; hvis (! (o eksempel på Word)) returnerer falsk; Ordord = (Ord) o; return word.getName (). tilsvarer (this.name); }Men hvis vi ikke overstyrer hashCode () når overstyrende er lik() da kan to like nøkler havne i de forskjellige bøttene fordi Hashtable beregner nøkkelindeksen ved hjelp av hash-koden.
La oss se nærmere på eksemplet ovenfor. Hva skjer hvis vi ikke overstyrer hashCode ()?
- To forekomster av Ord er involvert her - den første er for å sette oppføringen og den andre er for å få oppføringen. Selv om disse tilfellene er like, er deres hashCode () metode returnerer forskjellige tall
- Indeksen for hver nøkkel beregnes med formelen fra avsnitt 4.3. I henhold til denne formelen kan forskjellige hash-koder produsere forskjellige indekser
- Dette betyr at vi legger innføringen i den ene bøtta og deretter prøver å få den ut fra den andre bøtta. Slik logikk går i stykker Hashtable
Like taster må returnere like hash-koder. Derfor overstyrer vi hashCode () metode:
public int hashCode () {return name.hashCode (); }Noter det Det anbefales også at ikke like taster returnerer forskjellige hash-koder, ellers havner de i samme bøtte. Dette vil treffe ytelsen, og dermed miste noen av fordelene med a Hashtable.
Vær også oppmerksom på at vi ikke bryr oss om nøklene til String, Heltall, Lang eller en annen innpakningstype. Både lik() og hashCode () metoder er allerede overstyrt i wrapper-klasser.
5. Iterering Hashtables
Det er noen måter å gjenta Hashtables. I denne delen snakk godt om dem og forklar noen av implikasjonene.
5.1. Mislykkes raskt: Iterasjon
Mislykket iterasjon betyr at hvis en Hashtable er endret etter Iterator er opprettet, så blir ConcurrentModificationException vil bli kastet. La oss demonstrere dette.
Først oppretter vi en Hashtable og legg til oppføringer i den:
Hashtable-tabell = ny Hashtable (); table.put (nytt ord ("katt"), "et dyr"); table.put (nytt ord ("hund"), "et annet dyr");For det andre lager vi en Iterator:
Iterator it = table.keySet (). Iterator ();Og for det tredje vil vi endre tabellen:
table.remove (nytt ord ("hund"));Nå hvis vi prøver å gjenta gjennom tabellen, får vi en ConcurrentModificationException:
mens (it.hasNext ()) {Word-nøkkel = it.next (); }java.util.ConcurrentModificationException på java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)ConcurrentModificationException hjelper til med å finne feil og dermed unngå uforutsigbar oppførsel, når for eksempel en tråd gjentar seg gjennom bordet, og en annen prøver å endre den samtidig.
5.2. Ikke mislykkes raskt: Oppregning
Oppregning i en Hashtable er ikke feilrask. La oss se på et eksempel.
La oss først lage en Hashtable og legg til oppføringer i den:
Hashtable-tabell = ny Hashtable (); table.put (nytt ord ("1"), "ett"); table.put (nytt ord ("2"), "to");For det andre, la oss lage en Oppregning:
Oppregning enumKey = table.keys ();For det tredje, la oss endre tabellen:
table.remove (nytt ord ("1"));Nå hvis vi gjentar oss gjennom tabellen, vil det ikke kaste et unntak:
while (enumKey.hasMoreElements ()) {Word key = enumKey.nextElement (); }5.3. Uforutsigbar Iterasjonsordre
Vær også oppmerksom på at iterasjonsrekkefølge i a Hashtable er uforutsigbar og samsvarer ikke med rekkefølgen oppføringene ble lagt til.
Dette er forståelig ettersom den beregner hver indeks ved hjelp av nøkkelens hash-kode. Videre skjer gjenvasking av og til, og omorganiserer rekkefølgen til datastrukturen.
La oss derfor legge til noen oppføringer og sjekke utdataene:
Hashtable-tabell = ny Hashtable (); table.put (nytt ord ("1"), "ett"); table.put (nytt ord ("2"), "to"); // ... table.put (nytt Word ("8"), "åtte"); Iterator it = table.entrySet (). iterator (); while (it.hasNext ()) {Map.Entry entry = it.next (); // ...}} fem fire tre to en åtte syv6. Hashtable vs. HashMap
Hashtable og HashMap gir veldig lignende funksjonalitet.
Begge gir:
- Mislykket iterasjon
- Uforutsigbar iterasjonsrekkefølge
Men det er også noen forskjeller:
- HashMap gir ikke noe Oppregning, mens Hashtable gir ikke feilsøk Oppregning
- Hashtable tillater ikke null nøkler og null verdier, mens HashMap tillater en null nøkkel og et hvilket som helst antall null verdier
- HashtableMetodene synkroniseres mens HashMaps‘S metoder er det ikke
7. Hashtable API i Java 8
Java 8 har introdusert nye metoder som hjelper oss med å gjøre koden renere. Spesielt kan vi kvitte oss med noen hvis blokker. La oss demonstrere dette.
7.1. getOrDefault ()
La oss si at vi må få definisjonen av ordet “hund” og tilordne den til variabelen hvis den er på bordet. Ellers kan du tildele variabelen “ikke funnet”.
Før Java 8:
Ordnøkkel = nytt ord ("hund"); Streng definisjon; hvis (table.containsKey (nøkkel)) {definisjon = table.get (nøkkel); } annet {definisjon = "ikke funnet"; }Etter Java 8:
definisjon = table.getOrDefault (nøkkel, "ikke funnet");7.2. putIfAbsent ()
La oss si at vi trenger å sette et ord “katt“ bare hvis det ikke er i ordboken ennå.
Før Java 8:
if (! table.containsKey (new Word ("cat"))) {table.put (new Word ("cat"), definisjon); }Etter Java 8:
table.putIfAbsent (nytt ord ("katt"), definisjon);7.3. boolsk fjern ()
La oss si at vi trenger å fjerne ordet "katt", men bare hvis definisjonen er "et dyr".
Før Java 8:
if (table.get (new Word ("cat")). tilsvarer ("an animal")) {table.remove (new Word ("cat")); }Etter Java 8:
boolsk resultat = table.remove (nytt ord ("katt"), "et dyr");Til slutt, mens du er gammel fjerne() metoden returnerer verdien, den nye metoden returnerer boolsk.
7.4. erstatte()
La oss si at vi trenger å erstatte en definisjon av "katt", men bare hvis den gamle definisjonen er "et lite tammet kjøttetende pattedyr".
Før Java 8:
if (table.containsKey (new Word ("cat")) && table.get (new Word ("cat")). tilsvarer ("et lite tamme kjøttetende pattedyr")) {table.put (nytt Word ("cat" ), definisjon); }Etter Java 8:
table.replace (nytt ord ("katt"), "et lite tammet kjøttetende pattedyr", definisjon);7.5. computeIfAbsent ()
Denne metoden ligner på putIfabsent (). Men putIfabsent () tar verdien direkte, og computeIfAbsent () tar en kartleggingsfunksjon. Den beregner verdien først etter at den har sjekket nøkkelen, og dette er mer effektivt, spesielt hvis verdien er vanskelig å oppnå.
table.computeIfAbsent (nytt ord ("katt"), nøkkel -> "et dyr");Derfor tilsvarer linjen ovenfor:
if (! table.containsKey (cat)) {Strengdefinisjon = "et dyr"; // merk at beregninger foregår inne hvis block table.put (nytt Word ("cat"), definisjon); }7.6. computeIfPresent ()
Denne metoden ligner på erstatte() metode. Men igjen, erstatte() tar verdien direkte, og computeIfPresent () tar en kartleggingsfunksjon. Den beregner verdien inne i hvis blokkere, det er derfor det er mer effektivt.
La oss si at vi må endre definisjonen:
table.computeIfPresent (cat, (key, value) -> key.getName () + "-" + value);Derfor tilsvarer linjen ovenfor:
if (table.containsKey (cat)) {String concatination = cat.getName () + "-" + table.get (cat); table.put (cat, concatination); }7.7. beregne ()
Nå løser vi en annen oppgave. La oss si at vi har en rekke String, der elementene ikke er unike. La oss også beregne hvor mange forekomster av en streng vi kan få i matrisen. Her er matrisen:
String [] animals = {"cat", "dog", "dog", "cat", "bird", "mouse", "mouse"};Vi ønsker også å lage en Hashtable som inneholder et dyr som en nøkkel og antall forekomster som en verdi.
Her er en løsning:
Hashtable-tabell = ny Hashtable (); for (Strengdyr: dyr) {table.compute (dyr, (nøkkel, verdi) -> (verdi == null? 1: verdi + 1)); }Til slutt, la oss forsikre oss om at bordet inneholder to katter, to hunder, en fugl og to mus:
assertThat (table.values (), hasItems (2, 2, 2, 1));7.8. slå sammen()
Det er en annen måte å løse oppgaven ovenfor:
for (Strengdyr: dyr) {table.merge (animal, 1, (oldValue, value) -> (oldValue + value)); }Det andre argumentet, 1, er verdien som er tilordnet nøkkelen hvis nøkkelen ennå ikke er på bordet. Hvis nøkkelen allerede er i tabellen, beregner vi den som oldValue + 1.
7.9. for hver()
Dette er en ny måte å gjenta gjennom oppføringene. La oss skrive ut alle oppføringene:
table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)7.10. erstatt alle ()
I tillegg kan vi erstatte alle verdiene uten iterasjon:
table.replaceAll ((k, v) -> k.getName () + "-" + v);8. Konklusjon
I denne artikkelen har vi beskrevet formålet med hash-tabellstrukturen og vist hvordan du kan komplisere en direkte-adressetabellstruktur for å få den.
I tillegg har vi dekket hva kollisjoner er og hva en belastningsfaktor er i en Hashtable. Vi har også lært hvorfor vi overstyrer er lik() og hashCode () for nøkkelobjekter.
Til slutt har vi snakket om HashtableEgenskaper og Java 8-spesifikk API.
Som vanlig er den komplette kildekoden tilgjengelig på Github.
