En introduktion til Java.util.Hashtable-klasse
1. Oversigt
Hashtable er den ældste implementering af en hash-tabel datastruktur i Java. Det HashMap er den anden implementering, der blev introduceret i JDK 1.2.
Begge klasser giver lignende funktionalitet, men der er også små forskelle, som vi vil undersøge i denne vejledning.
2. Hvornår skal du bruge det? Hashtable
Lad os sige, at vi har en ordbog, hvor hvert ord har sin definition. Vi er også nødt til hurtigt at hente, indsætte og fjerne ord fra ordbogen.
Derfor, Hashtable (eller HashMap) giver mening. Ord vil være nøglerne i Hashtable, da de formodes at være unikke. Definitioner vil derimod være værdierne.
3. Eksempel på brug
Lad os fortsætte med ordbogseksemplet. Vi modellerer Ord som en nøgle:
offentlig klasse Word {privat strengnavn; offentligt ord (strengnavn) {dette.navn = navn; } // ...}Lad os sige, at værdierne er Strenge. Nu kan vi oprette en Hashtable:
Hashtable-tabel = ny Hashtable ();Lad os først tilføje en post:
Ordord = nyt ord ("kat"); table.put (ord, "et dyr");Også for at få en post:
Strengdefinition = tabel.get (ord);Lad os endelig fjerne en post:
definition = tabel. fjern (ord);Der er mange flere metoder i klassen, og vi beskriver nogle af dem senere.
Men lad os først tale om nogle krav til nøgleobjektet.
4. Betydningen af hashCode ()
Anvendes som nøgle i en Hashtable, må objektet ikke krænke hashCode () kontrakt. Kort sagt skal lige objekter returnere den samme kode. For at forstå hvorfor lad os se på, hvordan hashtabellen er organiseret.
Hashtable bruger en matrix. Hver position i arrayet er en "bucket", som enten kan være nul eller indeholde et eller flere nøgleværdipar. Indekset for hvert par beregnes.
Men hvorfor ikke gemme elementer sekventielt og tilføje nye elementer til slutningen af arrayet?
Pointen er, at det er meget hurtigere at finde et element efter indeks end at gentage elementerne med sammenligningen sekventielt. Derfor har vi brug for en funktion, der kortlægger nøgler til indekser.
4.1. Direkte adressetabel
Det enkleste eksempel på en sådan kortlægning er tabellen med direkte adresser. Her bruges taster som indekser:
indeks (k) = k, hvor k er en nøgleNøgler er unikke, det vil sige at hver spand indeholder et nøgleværdipar. Denne teknik fungerer godt for heltalstaster, når det mulige interval af dem er rimeligt lille.
Men vi har to problemer her:
- For det første er vores nøgler ikke heltal, men Ord genstande
- For det andet, hvis de var heltal, ville ingen garantere, at de var små. Forestil dig, at tasterne er 1, 2 og 1000000. Vi har et stort udvalg af størrelse 1000000 med kun tre elementer, og resten vil være et spildt rum
hashCode () metode løser det første problem.
Logikken for datamanipulation i Hashtable løser det andet problem.
Lad os diskutere dette i dybden.
4.2. hashCode () Metode
Ethvert Java-objekt arver hashCode () metode, der returnerer en int værdi. Denne værdi beregnes ud fra objektets interne hukommelsesadresse. Som standard hashCode () returnerer forskellige heltal for forskellige objekter.
Dermed ethvert nøgleobjekt kan konverteres til et heltal ved hjælp af hashCode (). Men dette heltal kan være stort.
4.3. Reducere rækkevidden
få(), sætte() og fjerne() metoder indeholder koden, der løser det andet problem - reducerer rækkevidden af mulige heltal.
Formlen beregner et indeks for nøglen:
int index = (hash & 0x7FFFFFFF)% tab.length;Hvor tab.længde er arraystørrelsen, og hash er et nummer, der returneres af nøglerne hashCode () metode.
Som vi kan se indeks er en påmindelse om divisionen hash efter matrixstørrelse. Bemærk, at lige hash-koder producerer det samme indeks.
4.4. Kollisioner
Desuden selv forskellige hash-koder kan producere det samme indeks. Vi henviser til dette som en kollision. For at løse kollisioner Hashtable butikker a LinkedList af nøgleværdipar.
En sådan datastruktur kaldes en hash-tabel med kæde.
4.5. Belastningsfaktor
Det er let at gætte, at kollisioner bremser operationer med elementer. For at få en post er det ikke nok at kende dets indeks, men vi er nødt til at gå gennem listen og udføre en sammenligning med hvert element.
Derfor er det vigtigt at reducere antallet af kollisioner. Jo større en matrix er, jo mindre er chancen for en kollision. Belastningsfaktoren bestemmer balancen mellem arraystørrelse og ydeevne. Som standard er det 0,75, hvilket betyder, at arraystørrelsen fordobles, når 75% af skovlene ikke bliver tomme. Denne operation udføres af genvask () metode.
Men lad os vende tilbage til nøglerne.
4.6. Tilsidesættelse er lig med () og hashCode ()
Når vi lægger en post i en Hashtable og få det ud af det, forventer vi, at værdien ikke kun kan opnås med samme forekomst af nøglen, men også med en lige nøgle:
Ordord = nyt ord ("kat"); table.put (ord, "et dyr"); Streng ekstraheret = table.get (nyt Word ("kat"));For at indstille reglerne for lighed, tilsidesætter vi nøglen lige med() metode:
offentlige boolske er lig med (Objekt o) {hvis (o == dette) returnerer sandt; hvis (! (o eksempel af Word)) returnerer falsk; Ordord = (Ord) o; return word.getName (). er lig med (this.name); }Men hvis vi ikke tilsidesætter hashCode () når det tilsidesættes lige med() så kan to lige nøgler muligvis ende i de forskellige spande, fordi Hashtable beregner nøgleindekset ved hjælp af dets hash-kode.
Lad os se nærmere på ovenstående eksempel. Hvad sker der, hvis vi ikke tilsidesætter hashCode ()?
- To tilfælde af Ord er involveret her - det første er at sætte posten, og det andet er at få posten. Selvom disse forekomster er ens, er deres hashCode () metode returnerer forskellige tal
- Indekset for hver nøgle beregnes efter formlen fra afsnit 4.3. I henhold til denne formel kan forskellige hash-koder producere forskellige indekser
- Det betyder, at vi lægger posten i den ene spand og derefter prøver at få den ud af den anden spand. Sådan logik går i stykker Hashtable
Lige taster skal returnere lige hash-koder, det er derfor, vi tilsidesætter hashCode () metode:
public int hashCode () {return name.hashCode (); }Noter det det anbefales også at lade ikke lige taster returnere forskellige hash-koder, ellers ender de i samme spand. Dette vil ramme præstationen og dermed miste nogle af fordelene ved a Hashtable.
Bemærk også, at vi ikke er ligeglade med nøglerne til Snor, Heltal, Lang eller en anden indpakningstype. Begge lige() og hashCode () metoder er allerede tilsidesat i indpakningsklasser.
5. Iterering Hashtables
Der er et par måder at gentage Hashtables. I dette afsnit skal du snakke godt om dem og forklare nogle af konsekvenserne.
5.1. Fejler hurtigt: Iteration
Fejlhurtig iteration betyder, at hvis en Hashtable er ændret efter dens Iterator er oprettet, så bliver ConcurrentModificationException vil blive kastet. Lad os demonstrere dette.
Først opretter vi en Hashtable og tilføj poster til det:
Hashtable-tabel = ny Hashtable (); table.put (nyt ord ("kat"), "et dyr"); table.put (nyt ord ("hund"), "et andet dyr");For det andet opretter vi en Iterator:
Iterator it = tabel.keySet (). Iterator ();Og for det tredje ændrer vi tabellen:
table.remove (nyt ord ("hund"));Hvis vi nu prøver at gentage gennem tabellen, får vi en ConcurrentModificationException:
mens (it.hasNext ()) {Word-nøgle = it.next (); }java.util.ConcurrentModificationException på java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)ConcurrentModificationException hjælper med at finde fejl og dermed undgå uforudsigelig opførsel, når for eksempel en tråd gentager sig gennem bordet, og en anden prøver at ændre det på samme tid.
5.2. Ikke mislykkes hurtigt: Optælling
Optælling i en Hashtable er ikke fail-fast. Lad os se på et eksempel.
Lad os først oprette en Hashtable og tilføj poster til det:
Hashtable-tabel = ny Hashtable (); table.put (nyt ord ("1"), "en"); table.put (nyt ord ("2"), "to");For det andet, lad os oprette en Optælling:
Enumeration enumKey = table.keys ();For det tredje, lad os ændre tabellen:
table.remove (nyt ord ("1"));Nu hvis vi gentager gennem tabellen, kaster det ikke en undtagelse:
mens (enumKey.hasMoreElements ()) {Word-nøgle = enumKey.nextElement (); }5.3. Uforudsigelig gentagelsesordre
Bemærk også, at iterationsrækkefølgen i a Hashtable er uforudsigelig og stemmer ikke overens med rækkefølgen, hvor posterne blev tilføjet.
Dette er forståeligt, da det beregner hvert indeks ved hjælp af nøglens hash-kode. Desuden finder genopvaskning sted fra tid til anden og omarrangerer rækkefølgen af datastrukturen.
Lad os derfor tilføje nogle poster og kontrollere output:
Hashtable-tabel = ny Hashtable (); table.put (nyt ord ("1"), "en"); table.put (nyt ord ("2"), "to"); // ... table.put (nyt Word ("8"), "otte"); Iterator it = table.entrySet (). iterator (); while (it.hasNext ()) {Map.Entry entry = it.next (); // ...}} fem fire tre to en otte syv6. Hashtable vs. HashMap
Hashtable og HashMap giver meget lignende funktionalitet.
Begge giver:
- Fejlhurtig iteration
- Uforudsigelig iterationsrækkefølge
Men der er også nogle forskelle:
- HashMap giver ikke noget Tælling, mens Hashtable giver ikke fail-fast Optælling
- Hashtable tillader ikke nul taster og nul værdier, mens HashMap tillader en nul nøgle og et vilkårligt antal nul værdier
- Hashtable'S metoder synkroniseres mens HashMaps'S metoder er ikke
7. Hashtable API i Java 8
Java 8 har introduceret nye metoder, der hjælper med at gøre vores kode renere. Især kan vi slippe af med nogle hvis blokke. Lad os demonstrere dette.
7.1. getOrDefault ()
Lad os sige, at vi er nødt til at få definitionen af ordet "hund” og tildel den til variablen, hvis den er på bordet. Ellers tildel "ikke fundet" til variablen.
Før Java 8:
Ordnøgle = nyt ord ("hund"); Streng definition; if (table.containsKey (key)) {definition = table.get (key); } andet {definition = "ikke fundet"; }Efter Java 8:
definition = tabel.getOrDefault (nøgle, "ikke fundet");7.2. putIfAbsent ()
Lad os sige, at vi skal sætte et ord “kat“ kun hvis det ikke er i ordbogen endnu.
Før Java 8:
if (! table.containsKey (new Word ("cat"))) {table.put (new Word ("cat"), definition); }Efter Java 8:
table.putIfAbsent (nyt ord ("kat"), definition);7.3. fjern boolsk ()
Lad os sige, at vi skal fjerne ordet "kat", men kun hvis definitionen er "et dyr".
Før Java 8:
hvis (tabel.get (nyt ord ("kat")). er lig med ("et dyr")) {tabel. fjern (nyt ord ("kat")); }Efter Java 8:
boolsk resultat = table.remove (nyt ord ("kat"), "et dyr");Endelig, mens den er gammel fjerne() metode returnerer værdien, den nye metode returnerer boolsk.
7.4. erstatte()
Lad os sige, at vi er nødt til at erstatte en definition af "kat", men kun hvis dens gamle definition er "et lille tæmmet kødædende pattedyr".
Før Java 8:
if (table.containsKey (new Word ("cat")) && table.get (new Word ("cat")). er lig med ("et lille tamme kødædende pattedyr")) {table.put (new Word ("cat" ), definition); }Efter Java 8:
table.replace (nyt ord ("kat"), "et lille tamme kødædende pattedyr", definition);7.5. computeIfAbsent ()
Denne metode svarer til putIfabsent (). Men putIfabsent () tager værdien direkte, og computeIfAbsent () tager en kortlægningsfunktion. Den beregner først værdien, når den kontrollerer nøglen, og dette er mere effektivt, især hvis værdien er vanskelig at få.
table.computeIfAbsent (nyt ord ("kat"), nøgle -> "et dyr");Derfor svarer ovenstående linje til:
if (! table.containsKey (cat)) {String definition = "et dyr"; // bemærk, at beregninger finder sted inde, hvis block table.put (nyt Word ("kat"), definition); }7.6. computeIfPresent ()
Denne metode svarer til erstatte() metode. Men igen, erstatte() tager værdien direkte, og computeIfPresent () tager en kortlægningsfunktion. Den beregner værdien inde i hvis blokere, det er derfor det er mere effektivt.
Lad os sige, at vi skal ændre definitionen:
table.computeIfPresent (cat, (key, value) -> key.getName () + "-" + value);Derfor svarer ovenstående linje til:
if (table.containsKey (cat)) {String concatination = cat.getName () + "-" + table.get (cat); table.put (kat, konkatination); }7.7. beregne ()
Nu løser vi en anden opgave. Lad os sige, at vi har en række Snor, hvor elementerne ikke er unikke. Lad os også beregne, hvor mange forekomster af en streng, vi kan få i arrayet. Her er arrayet:
Streng [] dyr = {"kat", "hund", "hund", "kat", "fugl", "mus", "mus"};Vi ønsker også at oprette en Hashtable som indeholder et dyr som en nøgle og antallet af dets forekomster som en værdi.
Her er en løsning:
Hashtable-tabel = ny Hashtable (); for (String animal: animals) {table.compute (animal, (key, value) -> (value == null? 1: value + 1)); }Lad os endelig sørge for, at bordet indeholder to katte, to hunde, en fugl og to mus:
assertThat (table.values (), hasItems (2, 2, 2, 1));7.8. fusionere()
Der er en anden måde at løse ovenstående opgave på:
for (String animal: animals) {tabel.merge (animal, 1, (oldValue, value) -> (oldValue + value)); }Det andet argument, 1, er den værdi, der er tilknyttet nøglen, hvis nøglen endnu ikke er på bordet. Hvis nøglen allerede er i tabellen, beregner vi den som oldValue + 1.
7.9. for hver()
Dette er en ny måde at gentage gennem posterne. Lad os udskrive alle poster:
table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)7.10. erstatteAlle ()
Derudover kan vi erstatte alle værdier uden iteration:
table.replaceAll ((k, v) -> k.getName () + "-" + v);8. Konklusion
I denne artikel har vi beskrevet formålet med hash-tabelstrukturen og vist, hvordan man komplicerer en direkte-adressetabelstruktur for at få den.
Derudover har vi dækket, hvad kollisioner er, og hvad en belastningsfaktor er i en Hashtable. Vi har også lært, hvorfor vi tilsidesætter lige med() og hashCode () til nøgleobjekter.
Endelig har vi talt om Hashtable'S egenskaber og Java 8-specifik API.
Som sædvanlig er den komplette kildekode tilgængelig på Github.
