1. 概要

Hashtableは、Javaのハッシュテーブルデータ構造の最も古い実装です。 HashMap は、JDK1.2で導入された2番目の実装です。

どちらのクラスも同様の機能を提供しますが、このチュートリアルで説明する小さな違いもあります。

2. ハッシュテーブルを使用する場合

各単語に定義がある辞書があるとしましょう。 また、辞書から単語をすばやく取得、挿入、削除する必要があります。

したがって、 Hashtable (または HashMap )は理にかなっています。 単語は一意であると想定されているため、Hashtableのキーになります。 一方、定義は値になります。

3. 使用例

辞書の例を続けましょう。 Wordをキーとしてモデル化します。

public class Word {
    private String name;

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

値がStringsであるとしましょう。 これで、Hashtableを作成できます。

Hashtable<Word, String> table = new Hashtable<>();

まず、エントリを追加しましょう。

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

また、エントリを取得するには:

String definition = table.get(word);

最後に、エントリを削除しましょう。

definition = table.remove(word);

クラスにはさらに多くのメソッドがあり、それらのいくつかについては後で説明します。

ただし、最初に、キーオブジェクトのいくつかの要件について説明しましょう。

4. hashCode()の重要性

ハッシュテーブルでキーとして使用するには、オブジェクトがhashCode()コントラクトに違反していてはなりません。つまり、等しいオブジェクトは同じコードを返す必要があります。 なぜハッシュテーブルがどのように編成されているかを見てみましょう。

Hashtableは配列を使用します。 配列内の各位置は「バケット」であり、nullにすることも、1つ以上のキーと値のペアを含めることもできます。 各ペアのインデックスが計算されます。

しかし、配列の最後に新しい要素を追加して、要素を順番に格納しないのはなぜですか?

重要なのは、インデックスによる要素の検索は、要素を順番に比較して繰り返すよりもはるかに高速であるということです。 したがって、キーをインデックスにマップする関数が必要です。

4.1. 直接アドレステーブル

このようなマッピングの最も簡単な例は、直接アドレステーブルです。 ここで、キーはインデックスとして使用されます。

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

キーは一意です。つまり、各バケットには1つのキーと値のペアが含まれています。 この手法は、整数キーの可能な範囲が適度に小さい場合にうまく機能します。

しかし、ここには2つの問題があります。

  • まず、キーは整数ではなく、Wordオブジェクトです
  • 第二に、それらが整数である場合、誰もそれらが小さいことを保証しません。 キーが1、2、1000000であると想像してください。 サイズが1000000で、要素が3つしかない大きな配列があり、残りは無駄なスペースになります

hashCode()メソッドは最初の問題を解決します。

Hashtable のデータ操作のロジックは、2番目の問題を解決します。

これについて詳しく説明しましょう。

4.2. hashCode()メソッド

すべてのJavaオブジェクトは、 int値を返すhashCode()メソッドを継承します。 この値は、オブジェクトの内部メモリアドレスから計算されます。 デフォルトでは、 hashCode()は、個別のオブジェクトに対して個別の整数を返します。

したがって、任意のキーオブジェクトは、hashCode()を使用して整数に変換できます。 しかし、この整数は大きいかもしれません。

4.3. 範囲を狭める

get() put()、および remove()メソッドには、2番目の問題である可能な整数の範囲を減らすコードが含まれています。

この式は、キーのインデックスを計算します。

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

ここで、 tab.length は配列サイズであり、 hash は、キーの hashCode()メソッドによって返される数値です。

ご覧のとおり、 indexは、配列サイズによる分割ハッシュを思い出させるものです。 等しいハッシュコードは同じインデックスを生成することに注意してください。

4.4. 衝突

さらに、異なるハッシュコードでも同じインデックスを生成できます。 これを衝突と呼びます。 衝突を解決するために、 Hashtable は、キーと値のペアのLinkedListを格納します。

このようなデータ構造は、連鎖を伴うハッシュテーブルと呼ばれます。

4.5. 負荷率

衝突によって要素の操作が遅くなることは容易に推測できます。 エントリを取得するには、そのインデックスを知るだけでは不十分ですが、リストを調べて各アイテムと比較する必要があります。

したがって、衝突の数を減らすことが重要です。 配列が大きいほど、衝突の可能性は小さくなります。 負荷率は、アレイサイズとパフォーマンスのバランスを決定します。デフォルトでは0.75です。これは、バケットが空でなくなると、アレイサイズが2倍になることを意味します。 この操作は、 rehash()メソッドによって実行されます。

しかし、キーに戻りましょう。

4.6. equals()とhashCode()をオーバーライドする

Hashtable にエントリを入れてそこから取り出すと、同じキーのインスタンスだけでなく、同じキーでも値を取得できることが期待されます。

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

等式のルールを設定するには、キーの equals()メソッドをオーバーライドします。

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);
}

ただし、 equals()をオーバーライドするときに hashCode()をオーバーライドしないと、 Hashtable がキーのインデックスを計算するため、2つの等しいキーが異なるバケットに入る可能性があります。そのハッシュコードを使用します。

上記の例を詳しく見てみましょう。 hashCode()をオーバーライドしないとどうなりますか?

  • ここでは、 Word の2つのインスタンスが関係しています。1つはエントリを配置するためのもので、もう1つはエントリを取得するためのものです。 これらのインスタンスは同じですが、 hashCode()メソッドは異なる数値を返します
  • 各キーのインデックスは、セクション4.3の式によって計算されます。 この式によれば、ハッシュコードが異なればインデックスも異なる可能性があります
  • これは、エントリを1つのバケットに入れてから、もう1つのバケットから取り出そうとすることを意味します。 そのような論理はハッシュテーブルを壊します

等しいキーは等しいハッシュコードを返す必要があるため、 hashCode()メソッドをオーバーライドします。

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

等しくないキーが異なるハッシュコードを返すようにすることもお勧めします。そうしないと、同じバケットに入れられてしまいます。  これはパフォーマンスに影響を与えるため、Hashtableの利点の一部が失われます。

また、 String Integer Longまたは別のラッパータイプのキーは気にしないことに注意してください。 equal()メソッドと hashCode()メソッドはどちらも、ラッパークラスで既にオーバーライドされています。

5. ハッシュテーブルの反復

繰り返す方法はいくつかありますハッシュテーブル。 このセクションでは、それらについてよく話し、いくつかの影響について説明します。

5.1. 速く失敗する:反復

フェイルファスト反復とは、イテレータの作成後にハッシュテーブルが変更された場合、ConcurrentModificationExceptionがスローされることを意味します。 これをデモンストレーションしましょう。

まず、 Hashtable を作成し、それにエントリを追加します。

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

次に、イテレータを作成します。

Iterator<Word> it = table.keySet().iterator();

そして第三に、テーブルを変更します。

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

ここで、テーブルを反復処理しようとすると、ConcurrentModificationExceptionが発生します。

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

ConcurrentModificationException は、バグを見つけるのに役立ちます。たとえば、あるスレッドがテーブルを反復処理し、別のスレッドが同時にテーブルを変更しようとしている場合に、予期しない動作を回避できます。

5.2. 速く失敗しない:列挙

HashtableEnumerationはフェイルファストではありません。 例を見てみましょう。

まず、 Hashtable を作成し、それにエントリを追加しましょう。

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

次に、列挙を作成しましょう。

Enumeration<Word> enumKey = table.keys();

第三に、テーブルを変更しましょう:

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

これで、テーブルを反復処理しても、例外はスローされません。

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

5.3. 予測できない反復順序

また、 Hashtable の反復順序は予測不可能であり、エントリが追加された順序と一致しないことに注意してください。

キーのハッシュコードを使用して各インデックスを計算するため、これは理解できます。 さらに、データ構造の順序を並べ替えて、再ハッシュが時々行われます。

したがって、いくつかのエントリを追加して、出力を確認しましょう。

Hashtable<Word, String> table = new Hashtable<Word, String>();
    table.put(new Word("1"), "one");
    table.put(new Word("2"), "two");
    // ...
    table.put(new Word("8"), "eight");

    Iterator<Map.Entry<Word, String>> it = table.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<Word, String> entry = it.next();
        // ...
    }
}
five
four
three
two
one
eight
seven

6. ハッシュテーブル対。 HashMap

HashtableHashMapは、非常によく似た機能を提供します。

それらの両方が提供します:

  • フェイルファスト反復
  • 予測できない反復順序

しかし、いくつかの違いもあります。

  • HashMap 列挙型を提供しませんが、 Hashtableはフェイルファストではありません列挙型
  • Hashtablenullキーとnull値を許可しませんが、HashMapは1つのnullキーとnull値の数
  • Hashtable のメソッドは同期されますが、HashMapsのメソッドは同期されません

7. Hashtable API in Java 8

Java 8は、コードをよりクリーンにするのに役立つ新しいメソッドを導入しました。 特に、いくつかのifブロックを取り除くことができます。 これをデモンストレーションしましょう。

7.1. getOrDefault()

「dogという単語の定義を取得し、それがテーブルにある場合はそれを変数に割り当てる必要があるとします。 それ以外の場合は、変数に「見つかりません」を割り当てます。

Java 8より前:

Word key = new Word("dog");
String definition;

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

Java 8以降:

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

7.2. putIfAbsent()

まだ辞書に載っていない場合にのみ、「catという単語を入れる必要があるとしましょう。

Java 8より前:

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

Java 8以降:

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

7.3. boolean remove()

「猫」という単語を削除する必要があるとしましょう。ただし、その定義が「動物」である場合に限ります。

Java 8より前:

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

Java 8以降:

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

最後に、古い remove()メソッドは値を返しますが、新しいメソッドはbooleanを返します。

7.4. replace()

「猫」の定義を置き換える必要があるとしましょう。ただし、その古い定義が「小さな飼いならされた肉食哺乳類」である場合に限ります。

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);
}

Java 8以降:

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

7.5. computeIfAbsent()

このメソッドは、 putIfabsent()に似ています。  ただし、 putIfabsent()は値を直接取得し、 computeIfAbsent()はマッピング関数を取得します。 キーをチェックした後にのみ値を計算します。これは、特に値を取得するのが難しい場合に、より効率的です。

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

したがって、上記の行は次のようになります。

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()

このメソッドは、 replace()メソッドに似ています。 ただし、ここでも、 replace()は値を直接取得し、 computeIfPresent()はマッピング関数を取得します。 if ブロック内の値を計算するため、より効率的です。

定義を変更する必要があるとしましょう。

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

したがって、上記の行は次のようになります。

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

7.7. compute()

次に、別のタスクを解決します。 String の配列があり、要素が一意ではないとします。  また、配列内で取得できる文字列の出現回数を計算してみましょう。 配列は次のとおりです。

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

また、キーとして動物を含み、値としてその出現回数を含むHashtableを作成したいと思います。

解決策は次のとおりです。

Hashtable<String, Integer> table = new Hashtable<String, Integer>();

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

最後に、テーブルに2匹の猫、2匹の犬、1羽の鳥、2匹のマウスが含まれていることを確認しましょう。

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

7.8. merge()

上記のタスクを解決する別の方法があります。

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

2番目の引数1は、キーがまだテーブルにない場合にキーにマップされる値です。 キーがすでにテーブルにある場合は、 oldValue +1として計算します。

7.9. foreach()

これは、エントリを反復処理するための新しい方法です。 すべてのエントリを印刷してみましょう。

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

7.10. replaceAll()

さらに、反復せずにすべての値を置き換えることができます。

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

8. 結論

この記事では、ハッシュテーブル構造の目的を説明し、直接アドレステーブル構造を複雑にしてそれを取得する方法を示しました。

さらに、ハッシュテーブルの衝突と負荷率について説明しました。また、 equals() hashCode()をオーバーライドする理由も学びました。 キーオブジェクト用。

最後に、HashtableのプロパティとJava8固有のAPIについて説明しました。

いつものように、完全なソースコードはGithub入手できます。