Eine Einführung in die Java.util.Hashtable-Klasse

1. Übersicht

Hashtable ist die älteste Implementierung einer Hash-Tabellendatenstruktur in Java. Die HashMap ist die zweite Implementierung, die in JDK 1.2 eingeführt wurde.

Beide Klassen bieten ähnliche Funktionen, aber es gibt auch kleine Unterschiede, die wir in diesem Tutorial untersuchen werden.

2. Wann sollte Hashtable verwendet werden ?

Nehmen wir an, wir haben ein Wörterbuch, in dem jedes Wort seine Definition hat. Außerdem müssen wir Wörter schnell aus dem Wörterbuch holen, einfügen und entfernen.

Daher ist Hashtable (oder HashMap ) sinnvoll. Wörter werden die Schlüssel in der Hashtabelle sein , da sie einzigartig sein sollen. Definitionen sind dagegen die Werte.

3. Anwendungsbeispiel

Fahren wir mit dem Wörterbuchbeispiel fort. Wir werden Word als Schlüssel modellieren :

public class Word { private String name; public Word(String name) { this.name = name; } // ... }

Angenommen, die Werte sind Strings . Jetzt können wir eine Hashtabelle erstellen :

Hashtable table = new Hashtable();

Fügen wir zunächst einen Eintrag hinzu:

Word word = new Word("cat"); table.put(word, "an animal");

Um einen Eintrag zu erhalten:

String definition = table.get(word);

Zum Schluss entfernen wir einen Eintrag:

definition = table.remove(word);

Es gibt viel mehr Methoden in der Klasse, und wir werden einige davon später beschreiben.

Aber zuerst sprechen wir über einige Anforderungen für das Schlüsselobjekt.

4. Die Bedeutung von hashCode ()

Um als Schlüssel in einer Hashtable verwendet zu werden , darf das Objekt nicht gegen den hashCode () -Vertrag verstoßen . Kurz gesagt, gleiche Objekte müssen denselben Code zurückgeben. Um zu verstehen, warum wir uns ansehen, wie die Hash-Tabelle organisiert ist.

Hashtable verwendet ein Array. Jede Position im Array ist ein "Bucket", der entweder null sein oder ein oder mehrere Schlüssel-Wert-Paare enthalten kann. Der Index jedes Paares wird berechnet.

Aber warum nicht Elemente nacheinander speichern und neue Elemente am Ende des Arrays hinzufügen?

Der Punkt ist, dass das Finden eines Elements anhand des Index viel schneller ist, als die Elemente mit dem Vergleich nacheinander zu durchlaufen. Daher benötigen wir eine Funktion, die Schlüssel Indizes zuordnet.

4.1. Direkte Adresstabelle

Das einfachste Beispiel für eine solche Zuordnung ist die Direktadressentabelle. Hier werden Schlüssel als Indizes verwendet:

index(k)=k, where k is a key

Schlüssel sind eindeutig, dh jeder Bucket enthält ein Schlüssel-Wert-Paar. Diese Technik eignet sich gut für Ganzzahlschlüssel, wenn der mögliche Bereich relativ klein ist.

Aber wir haben hier zwei Probleme:

  • Erstens sind unsere Schlüssel keine ganzen Zahlen, sondern Word- Objekte
  • Zweitens, wenn sie ganze Zahlen wären, würde niemand garantieren, dass sie klein sind. Stellen Sie sich vor, die Schlüssel sind 1, 2 und 1000000. Wir haben ein großes Array der Größe 1000000 mit nur drei Elementen, und der Rest wird Platz verschwenden

Die Methode hashCode () löst das erste Problem.

Die Logik zur Datenmanipulation in der Hashtabelle löst das zweite Problem.

Lassen Sie uns dies ausführlich diskutieren.

4.2. hashCode () -Methode

Jedes Java-Objekt erbt die hashCode () -Methode, die einen int- Wert zurückgibt . Dieser Wert wird aus der internen Speicheradresse des Objekts berechnet. Standardmäßig gibt hashCode () unterschiedliche Ganzzahlen für unterschiedliche Objekte zurück.

Somit kann jedes Schlüsselobjekt mit hashCode () in eine Ganzzahl konvertiert werden . Aber diese ganze Zahl kann groß sein.

4.3. Reichweite reduzieren

Die Methoden get () , put () und remove () enthalten den Code, der das zweite Problem löst - die Reduzierung des Bereichs möglicher Ganzzahlen.

Die Formel berechnet einen Index für den Schlüssel:

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

Dabei ist tab.length die Arraygröße und hash eine Zahl, die von der hashCode () -Methode des Schlüssels zurückgegeben wird.

Wie wir sehen können, ist der Index eine Erinnerung an den Divisions- Hash durch die Array-Größe . Beachten Sie, dass gleiche Hash-Codes denselben Index erzeugen.

4.4. Kollisionen

Darüber hinaus können auch verschiedene Hash-Codes den gleichen Index erzeugen . Wir bezeichnen dies als Kollision. Um Kollisionen aufzulösen, speichert Hashtable eine LinkedList mit Schlüssel-Wert-Paaren.

Eine solche Datenstruktur wird als Hash-Tabelle mit Verkettung bezeichnet.

4.5. Ladefaktor

It is easy to guess that collisions slow down operations with elements. To get an entry it is not enough to know its index, but we need to go through the list and perform a comparison with each item.

Therefore it's important to reduce the number of collisions. The bigger is an array, the smaller is the chance of a collision. The load factor determines the balance between the array size and the performance. By default, it's 0.75 which means that the array size doubles when 75% of the buckets become not empty. This operation is executed by rehash() method.

But let's return to the keys.

4.6. Overriding equals() and hashCode()

When we put an entry into a Hashtable and get it out of it, we expect that the value can be obtained not only with same the instance of the key but also with an equal key:

Word word = new Word("cat"); table.put(word, "an animal"); String extracted = table.get(new Word("cat"));

To set the rules of equality, we override the key’s equals() method:

public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Word)) return false; Word word = (Word) o; return word.getName().equals(this.name); }

But if we don’t override hashCode() when overriding equals() then two equal keys may end up in the different buckets because Hashtable calculates the key’s index using its hash code.

Let’s take a close look at the above example. What happens if we don’t override hashCode()?

  • Two instances of Word are involved here – the first is for putting the entry and the second is for getting the entry. Although these instances are equal, their hashCode() method return different numbers
  • The index for each key is calculated by the formula from section 4.3. According to this formula, different hash codes may produce different indexes
  • This means that we put the entry into one bucket and then try to get it out from the other bucket. Such logic breaks Hashtable

Equal keys must return equal hash codes, that’s why we override the hashCode() method:

public int hashCode() { return name.hashCode(); }

Note that it's also recommended to make not equal keys return different hash codes, otherwise they end up in the same bucket. This will hit the performance, hence, losing some of the advantages of a Hashtable.

Also, note that we don’t care about the keys of String, Integer, Long or another wrapper type. Both equal() and hashCode() methods are already overridden in wrapper classes.

5. Iterating Hashtables

There are a few ways to iterate Hashtables. In this section well talk about them and explain some of the implications.

5.1. Fail Fast: Iteration

Fail-fast iteration means that if a Hashtable is modified after its Iterator is created, then the ConcurrentModificationException will be thrown. Let's demonstrate this.

First, we'll create a Hashtable and add entries to it:

Hashtable table = new Hashtable(); table.put(new Word("cat"), "an animal"); table.put(new Word("dog"), "another animal");

Second, we'll create an Iterator:

Iterator it = table.keySet().iterator();

And third, we'll modify the table:

table.remove(new Word("dog"));

Now if we try to iterate through the table, we'll get a ConcurrentModificationException:

while (it.hasNext()) { Word key = it.next(); }
java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1378)

ConcurrentModificationException helps to find bugs and thus avoid unpredictable behavior, when, for example, one thread is iterating through the table, and another one is trying to modify it at the same time.

5.2. Not Fail Fast: Enumeration

Enumeration in a Hashtable is not fail-fast. Let's look at an example.

First, let's create a Hashtable and add entries to it:

Hashtable table = new Hashtable(); table.put(new Word("1"), "one"); table.put(new Word("2"), "two");

Second, let's create an Enumeration:

Enumeration enumKey = table.keys();

Third, let's modify the table:

table.remove(new Word("1"));

Now if we iterate through the table it won't throw an exception:

while (enumKey.hasMoreElements()) { Word key = enumKey.nextElement(); }

5.3. Unpredictable Iteration Order

Also, note that iteration order in a Hashtable is unpredictable and does not match the order in which the entries were added.

This is understandable as it calculates each index using the key's hash code. Moreover, rehashing takes place from time to time, rearranging the order of the data structure.

Hence, let's add some entries and check the output:

Hashtable table = new Hashtable(); table.put(new Word("1"), "one"); table.put(new Word("2"), "two"); // ... table.put(new Word("8"), "eight"); Iterator
    
      it = table.entrySet().iterator(); while (it.hasNext()) { Map.Entry entry = it.next(); // ... } }
    
five four three two one eight seven

6. Hashtable vs. HashMap

Hashtable and HashMap provide very similar functionality.

Both of them provide:

  • Fail-fast iteration
  • Unpredictable iteration order

But there are some differences too:

  • HashMap doesn't provide any Enumeration, while Hashtable provides not fail-fast Enumeration
  • Hashtable doesn't allow null keys and null values, while HashMap do allow one null key and any number of null values
  • Hashtable‘s methods are synchronized while HashMaps‘s methods are not

7. Hashtable API in Java 8

Java 8 has introduced new methods which help make our code cleaner. In particular, we can get rid of some if blocks. Let's demonstrate this.

7.1. getOrDefault()

Let's say we need to get the definition of the word “dogand assign it to the variable if it is on the table. Otherwise, assign “not found” to the variable.

Before Java 8:

Word key = new Word("dog"); String definition; if (table.containsKey(key)) { definition = table.get(key); } else { definition = "not found"; }

After Java 8:

definition = table.getOrDefault(key, "not found");

7.2. putIfAbsent()

Let's say we need to put a word “cat only if it's not in the dictionary yet.

Before Java 8:

if (!table.containsKey(new Word("cat"))) { table.put(new Word("cat"), definition); }

After Java 8:

table.putIfAbsent(new Word("cat"), definition);

7.3. boolean remove()

Let's say we need to remove the word “cat” but only if it's definition is “an animal”.

Before Java 8:

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

After Java 8:

boolean result = table.remove(new Word("cat"), "an animal");

Finally, while old remove() method returns the value, the new method returns boolean.

7.4. replace()

Let's say we need to replace a definition of “cat”, but only if its old definition is “a small domesticated carnivorous mammal”.

Before Java 8:

if (table.containsKey(new Word("cat")) && table.get(new Word("cat")).equals("a small domesticated carnivorous mammal")) { table.put(new Word("cat"), definition); }

After Java 8:

table.replace(new Word("cat"), "a small domesticated carnivorous mammal", definition);

7.5. computeIfAbsent()

This method is similar to putIfabsent(). But putIfabsent() takes the value directly, and computeIfAbsent() takes a mapping function. It calculates the value only after it checks the key, and this is more efficient, especially if the value is difficult to obtain.

table.computeIfAbsent(new Word("cat"), key -> "an animal");

Hence, the above line is equivalent to:

if (!table.containsKey(cat)) { String definition = "an animal"; // note that calculations take place inside if block table.put(new Word("cat"), definition); }

7.6. computeIfPresent()

This method is similar to the replace() method. But, again, replace() takes the value directly, and computeIfPresent() takes a mapping function. It calculates the value inside of the if block, that's why it's more efficient.

Let's say we need to change the definition:

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

Hence, the above line is equivalent to:

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

7.7. compute()

Now we'll solve another task. Let's say we have an array of String, where the elements are not unique. Also, let's calculate how many occurrences of a String we can get in the array. Here is the array:

String[] animals = { "cat", "dog", "dog", "cat", "bird", "mouse", "mouse" };

Also, we want to create a Hashtable which contains an animal as a key and the number of its occurrences as a value.

Here is a solution:

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

Finally, let's make sure, that the table contains two cats, two dogs, one bird and two mouses:

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

7.8. merge()

There is another way to solve the above task:

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

The second argument, 1, is the value which is mapped to the key if the key is not yet on the table. If the key is already in the table, then we calculate it as oldValue+1.

7.9. foreach()

This is a new way to iterate through the entries. Let's print all the entries:

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

7.10. replaceAll()

Additionally, we can replace all the values without iteration:

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

8. Conclusion

In this article, we've described the purpose of the hash table structure and showed how to complicate a direct-address table structure to get it.

Darüber hinaus haben wir erläutert, was Kollisionen sind und was ein Lastfaktor in einer Hashtabelle ist. Außerdem haben wir gelernt, warum equals () und hashCode () für Schlüsselobjekte überschrieben werden.

Schließlich haben wir über die Eigenschaften von Hashtable und die Java 8-spezifische API gesprochen.

Der vollständige Quellcode ist wie gewohnt auf Github verfügbar.