streamalism.org

1. Overzicht

Hashtable is de oudste implementatie van een hashtabel datastructuur in Java. De Hash kaart is de tweede implementatie, die werd geïntroduceerd in JDK 1.2.

Beide klassen bieden vergelijkbare functionaliteit, maar er zijn ook kleine verschillen, die we in deze tutorial zullen onderzoeken.

2. Wanneer te gebruiken Hashtable

Laten we zeggen dat we een woordenboek hebben, waarin elk woord zijn definitie heeft. We moeten ook snel woorden uit het woordenboek halen, invoegen en verwijderen.

Vandaar, Hashtable (of Hash kaart) klinkt logisch. Woorden zullen de sleutels zijn in de Hashtable, omdat ze uniek zouden moeten zijn. Definities zijn daarentegen de waarden.

3. Voorbeeld van gebruik

Laten we doorgaan met het woordenboekvoorbeeld. We zullen modelleren Woord als sleutel:

openbare klasse Woord {private String naam; openbaar woord (tekenreeksnaam) {this.name = naam; } // ...}

Laten we zeggen dat de waarden zijn Snaren. Nu kunnen we een Hashtable:

Hashtable table = nieuwe Hashtable ();

Laten we eerst een item toevoegen:

Woordwoord = nieuw woord ("kat"); table.put (woord, "een dier");

Om ook een vermelding te krijgen:

Stringdefinitie = table.get (word);

Laten we tot slot een item verwijderen:

definition = table.remove (word);

Er zijn veel meer methoden in de klas, en we zullen er later enkele beschrijven.

Maar laten we eerst enkele vereisten voor het hoofdobject bespreken.

4. Het belang van hashCode ()

Te gebruiken als sleutel in een Hashtable, mag het object de hashCode () contract. Kortom, gelijke objecten moeten dezelfde code retourneren. Om te begrijpen waarom, laten we eens kijken hoe de hashtabel is georganiseerd.

Hashtable gebruikt een array. Elke positie in de array is een "bucket" die null kan zijn of een of meer sleutelwaardeparen kan bevatten. De index van elk paar wordt berekend.

Maar waarom zouden we de elementen niet opeenvolgend opslaan en nieuwe elementen aan het einde van de array toevoegen?

Het punt is dat het vinden van een element op index veel sneller is dan het doorlopen van de elementen met de opeenvolgende vergelijking. Daarom hebben we een functie nodig die sleutels aan indexen toewijst.

4.1. Directe adrestabel

Het eenvoudigste voorbeeld van een dergelijke mapping is de direct-adrestabel. Hier worden sleutels gebruikt als indexen:

index (k) = k, waarbij k een sleutel is

Sleutels zijn uniek, dat wil zeggen dat elke bucket één sleutel / waarde-paar bevat. Deze techniek werkt goed voor integer-sleutels als het mogelijke bereik ervan redelijk klein is.

Maar we hebben hier twee problemen:

• Ten eerste zijn onze sleutels geen gehele getallen, maar Woord voorwerpen
• Ten tweede, als het gehele getallen waren, zou niemand garanderen dat ze klein waren. Stel je voor dat de sleutels 1, 2 en 1000000 zijn. We hebben een grote reeks van 1000000 met slechts drie elementen, en de rest is een verspilde ruimte

hashCode () methode lost het eerste probleem op.

De logica voor gegevensmanipulatie in het Hashtable lost het tweede probleem op.

Laten we dit uitgebreid bespreken.

4.2. hashCode () Methode

Elk Java-object erft het hashCode () methode die een int waarde. Deze waarde wordt berekend op basis van het interne geheugenadres van het object. Standaard hashCode () geeft unieke gehele getallen terug voor verschillende objecten.

Dus elk sleutelobject kan worden geconverteerd naar een geheel getal met hashCode (). Maar dit gehele getal kan groot zijn.

4.3. Het bereik verkleinen

krijgen(), leggen() en verwijderen() methodes bevatten de code die het tweede probleem oplost - het aantal mogelijke gehele getallen verkleinen.

De formule berekent een index voor de sleutel:

int index = (hash & 0x7FFFFFFF)% tab.length;

Waar tab.length is de array-grootte, en hash is een nummer dat wordt geretourneerd door de sleutel hashCode () methode.

Zoals we kunnen zien index is een herinnering aan de divisie hash door de matrixgrootte. Merk op dat gelijke hashcodes dezelfde index produceren.

4.4. Botsingen

Bovendien zelfs verschillende hashcodes kunnen dezelfde index produceren. Dit noemen we een aanrijding. Om botsingen op te lossen Hashtable slaat een LinkedList van sleutel / waarde-paren.

Een dergelijke datastructuur wordt een hashtabel met chaining genoemd.

4.5. Ladingsfactor

Het is gemakkelijk te raden dat botsingen bewerkingen met elementen vertragen. Om een ​​item te krijgen, is het niet voldoende om de index te kennen, maar we moeten de lijst doorlopen en een vergelijking maken met elk item.

Daarom is het belangrijk om het aantal botsingen te verminderen. Hoe groter een array is, hoe kleiner de kans op een botsing. De belastingsfactor bepaalt de balans tussen de array-grootte en de prestaties. Standaard is dit 0,75, wat betekent dat de array-grootte verdubbelt wanneer 75% van de buckets niet leeg raakt. Deze bewerking wordt uitgevoerd door rehash () methode.

Maar laten we terugkeren naar de sleutels.

4.6. Equals () en hashCode () overschrijven

Wanneer we een vermelding in een Hashtable en haal het eruit, we verwachten dat de waarde niet alleen kan worden verkregen met dezelfde instantie van de sleutel, maar ook met een gelijke sleutel:

Woordwoord = nieuw woord ("kat"); table.put (woord, "een dier"); String geëxtraheerd = table.get (nieuw woord ("kat"));

Om de regels van gelijkheid vast te stellen, overschrijven we de sleutels is gelijk aan () methode:

public boolean equals (Object o) {if (o == this) return true; if (! (o instanceof Word)) return false; Woordwoord = (Woord) o; retourneer word.getName (). is gelijk aan (this.name); }

Maar als we niet opheffen hashCode () bij overheersing is gelijk aan () dan kunnen twee gelijke sleutels in de verschillende emmers terecht komen omdat Hashtable berekent de index van de sleutel met behulp van de hashcode.

Laten we het bovenstaande voorbeeld eens nader bekijken. Wat gebeurt er als we niet opheffen? hashCode ()?

• Twee gevallen van Woord zijn hier bij betrokken - de eerste is voor het plaatsen van de invoer en de tweede is voor het verkrijgen van de invoer. Hoewel deze gevallen gelijk zijn, is hun hashCode () methode retourneert verschillende getallen
• De index voor elke sleutel wordt berekend met de formule uit paragraaf 4.3. Volgens deze formule kunnen verschillende hashcodes verschillende indexen produceren
• Dit betekent dat we het item in de ene emmer doen en vervolgens proberen het uit de andere emmer te halen. Dergelijke logica breekt Hashtable

Gelijke sleutels moeten gelijke hashcodes retourneren, daarom overschrijven we de hashCode () methode:

openbare int hashCode () {terugkeer naam.hashCode (); }

Let daar op Het wordt ook aanbevolen om niet-gelijke sleutels verschillende hashcodes te laten retourneren, anders komen ze in dezelfde emmer terecht. Dit zal de prestaties beïnvloeden, waardoor enkele voordelen van een Hashtable.

Houd er ook rekening mee dat we niet geven om de sleutels van Draad, Geheel getal, Lang of een ander wikkeltype. Beide Gelijk() en hashCode () methoden zijn al overschreven in wrapper-klassen.

5. Itereren Hashtables

Er zijn een paar manieren om te herhalen Hashtables. Praat er in dit gedeelte goed over en leg enkele implicaties uit.

5.1. Faal snel: Iteratie

Fail-fast iteratie betekent dat als a Hashtable wordt gewijzigd na zijn Iterator is gemaakt, dan is het ConcurrentModificationException zal worden gegooid. Laten we dit demonstreren.

Eerst maken we een Hashtable en voeg er vermeldingen aan toe:

Hashtable table = nieuwe Hashtable (); table.put (nieuw woord ("kat"), "een dier"); table.put (nieuw woord ("hond"), "een ander dier");

Ten tweede maken we een Iterator:

Iterator het = table.keySet (). Iterator ();

En ten derde zullen we de tabel aanpassen:

table.remove (nieuw woord ("hond"));

Als we nu proberen de tabel te herhalen, krijgen we een ConcurrentModificationException:

while (it.hasNext ()) {Woordsleutel = it.next (); }

java.util.ConcurrentModificationException op java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)

ConcurrentModificationException helpt om bugs te vinden en zo onvoorspelbaar gedrag te vermijden, wanneer bijvoorbeeld een thread door de tabel loopt en een andere deze tegelijkertijd probeert te wijzigen.

5.2. Niet snel falen: Opsomming

Opsomming in een Hashtable is niet faalvast. Laten we naar een voorbeeld kijken.

Laten we eerst een Hashtable en voeg er vermeldingen aan toe:

Hashtable table = nieuwe Hashtable (); table.put (nieuw woord ("1"), "een"); table.put (nieuw woord ("2"), "twee");

Ten tweede, laten we een Opsomming:

Opsomming enumKey = table.keys ();

Ten derde, laten we de tabel aanpassen:

table.remove (nieuw woord ("1"));

Als we nu door de tabel herhalen, wordt er geen uitzondering gegenereerd:

while (enumKey.hasMoreElements ()) {Woordsleutel = enumKey.nextElement (); }

5.3. Onvoorspelbare herhalingsvolgorde

Merk ook op dat de iteratievolgorde in een Hashtable is onvoorspelbaar en komt niet overeen met de volgorde waarin de vermeldingen zijn toegevoegd.

Dit is begrijpelijk omdat het elke index berekent met behulp van de hashcode van de sleutel. Bovendien vindt er van tijd tot tijd rehashing plaats, waarbij de volgorde van de datastructuur wordt herschikt.

Laten we daarom enkele vermeldingen toevoegen en de uitvoer controleren:

Hashtable table = nieuwe Hashtable (); table.put (nieuw woord ("1"), "een"); table.put (nieuw woord ("2"), "twee"); // ... table.put (nieuw woord ("8"), "acht"); Iterator het = table.entrySet (). iterator (); while (it.hasNext ()) {Map.Entry entry = it.next (); // ...}}

vijf vier drie twee een acht zeven

6. Hashtable vs. Hash kaart

Hashtable en Hash kaart bieden zeer vergelijkbare functionaliteit.

Beiden bieden:

• Faalsnelle iteratie
• Onvoorspelbare iteratievolgorde

Maar er zijn ook enkele verschillen:

• Hash kaart biedt geen Opsomming, terwijl Hashtable biedt niet fail-fast Opsomming
• Hashtable staat niet toe nul sleutels en nul waarden, terwijl Hash kaart sta er een toe nul sleutel en een willekeurig aantal nul waarden
• Hashtable‘S methoden worden gesynchroniseerd terwijl HashMaps‘S methoden zijn dat niet

7. Hashtable API in Java 8

Java 8 heeft nieuwe methoden geïntroduceerd die helpen onze code schoner te maken. In het bijzonder kunnen we er wat kwijtraken als blokken. Laten we dit demonstreren.

7.1. getOrDefault ()

Laten we zeggen dat we de definitie van het woord "hond" nodig hebben” en wijs het toe aan de variabele als het op tafel ligt. Wijs anders 'niet gevonden' toe aan de variabele.

Vóór Java 8:

Woordsleutel = nieuw woord ("hond"); String definitie; if (table.containsKey (key)) {definition = table.get (key); } else {definition = "niet gevonden"; }

Na Java 8:

definition = table.getOrDefault (sleutel, "niet gevonden");

7.2. putIfAbsent ()

Laten we zeggen dat we een woord "kat" moeten plaatsen“ alleen als het nog niet in het woordenboek staat.

Vóór Java 8:

if (! table.containsKey (nieuw woord ("kat"))) {table.put (nieuw woord ("kat"), definitie); }

Na Java 8:

table.putIfAbsent (nieuw woord ("kat"), definitie);

7.3. boolean remove ()

Laten we zeggen dat we het woord "kat" moeten verwijderen, maar alleen als de definitie "een dier" is.

Vóór Java 8:

if (table.get (new Word ("cat")). equals ("an animal")) {table.remove (new Word ("cat")); }

Na Java 8:

booleaans resultaat = table.remove (nieuw woord ("kat"), "een dier");

Eindelijk, terwijl oud verwijderen() methode retourneert de waarde, de nieuwe methode retourneert boolean.

7.4. vervangen()

Laten we zeggen dat we een definitie van "kat" moeten vervangen, maar alleen als de oude definitie "een klein gedomesticeerd vleesetend zoogdier" is.

Vóór Java 8:

if (table.containsKey (nieuw woord ("kat")) && table.get (nieuw woord ("kat")). equals ("een klein gedomesticeerd vleesetend zoogdier")) {table.put (nieuw woord ("kat" ), definitie); }

Na Java 8:

table.replace (nieuw woord ("kat"), "een klein gedomesticeerd vleesetend zoogdier", definitie);

7.5. computeIfAbsent ()

Deze methode is vergelijkbaar met putIfabsent (). Maar putIfabsent () neemt de waarde rechtstreeks, en computeIfAbsent () heeft een mapping-functie. Het berekent de waarde pas nadat het de sleutel heeft gecontroleerd, en dit is efficiënter, vooral als de waarde moeilijk te verkrijgen is.

table.computeIfAbsent (nieuw woord ("kat"), key -> "een dier");

Daarom is de bovenstaande regel gelijk aan:

if (! table.containsKey (cat)) {String definition = "an animal"; // merk op dat berekeningen plaatsvinden binnen if block table.put (new Word ("cat"), definition); }

7.6. computeIfPresent ()

Deze methode is vergelijkbaar met de vervangen() methode. Maar nogmaals, vervangen() neemt de waarde rechtstreeks, en computeIfPresent () heeft een mapping-functie. Het berekent de waarde binnenin de als blok, daarom is het efficiënter.

Laten we zeggen dat we de definitie moeten veranderen:

table.computeIfPresent (cat, (sleutel, waarde) -> key.getName () + "-" + waarde);

Daarom is de bovenstaande regel gelijk aan:

if (table.containsKey (cat)) {String concatination = cat.getName () + "-" + table.get (cat); table.put (kat, concatination); }

7.7. berekenen()

Nu lossen we een andere taak op. Laten we zeggen dat we een reeks hebben Draad, waar de elementen niet uniek zijn. Laten we ook berekenen hoeveel exemplaren van een String we in de array kunnen krijgen. Hier is de array:

String [] dieren = {"kat", "hond", "hond", "kat", "vogel", "muis", "muis"};

We willen ook een Hashtable die een dier als sleutel bevat en het aantal keren dat het voorkomt als een waarde.

Hier is een oplossing:

Hashtable table = nieuwe Hashtable (); for (String animal: animals) {table.compute (animal, (key, value) -> (value == null? 1: value + 1)); }

Laten we er tot slot voor zorgen dat de tafel twee katten, twee honden, een vogel en twee muizen bevat:

assertThat (table.values ​​(), hasItems (2, 2, 2, 1));

7.8. samenvoegen()

Er is een andere manier om de bovenstaande taak op te lossen:

for (String animal: animals) {table.merge (animal, 1, (oldValue, value) -> (oldValue + value)); }

Het tweede argument, 1, is de waarde die aan de sleutel wordt toegewezen als de sleutel nog niet op tafel ligt. Als de sleutel al in de tabel staat, berekenen we deze als oldValue + 1.

7.9. foreach ()

Dit is een nieuwe manier om de vermeldingen te doorlopen. Laten we alle vermeldingen afdrukken:

table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)

7.10. vervang alles()

Bovendien kunnen we alle waarden zonder iteratie vervangen:

table.replaceAll ((k, v) -> k.getName () + "-" + v);

8. Conclusie

In dit artikel hebben we het doel van de hashtabelstructuur beschreven en laten zien hoe je een direct-adrestabelstructuur ingewikkeld kunt maken om deze te krijgen.

Bovendien hebben we besproken wat botsingen zijn en wat een belastingsfactor is in een Hashtable. We hebben ook geleerd waarom we opheffen is gelijk aan () en hashCode () voor belangrijke objecten.

Eindelijk hebben we het gehad over Hashtable‘S eigenschappen en Java 8-specifieke API.

Zoals gewoonlijk is de volledige broncode beschikbaar op Github.