1概要



  • Hashtable


    は、Javaにおけるハッシュテーブルデータ構造の最も古い実装です。 JDK 1.2で導入されました。

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


2いつ使うべきか

Hashtable


各単語にその定義がある辞書があるとしましょう。

また、辞書から単語を素早く取得、挿入、削除する必要があります。

したがって、

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


の重要性


  • Hashtable

    のキーとして使用するには、オブジェクトがリンクを違反してはいけません。ハッシュテーブルがどのように構成されているかを見てみましょう。


Hashtable

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

しかし、配列の末尾に新しい要素を追加して、要素を順番に格納しないのはなぜでしょうか。

要点は、インデックスを使って要素を見つけることは、要素を順番に比較しながら繰り返すよりもはるかに速いということです。したがって、キーをインデックスにマッピングする関数が必要です。


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

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

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

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

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

  • まず、キーは整数ではなく

    Word

    オブジェクトです。

  • 2番目に、もしそれらが整数なら、誰も彼らが小さいと保証することはないでしょう。

キーが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です。この操作は

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つのインスタンスが関係しています – 最初のインスタンスは次のものです。

エントリと2番目のエントリを取得するためのものです。これらは
インスタンスが等しい場合、それらの

hashCode()

メソッドは異なる数を返します。
** 各キーのインデックスは、セクション4.3の公式によって計算されます。

この式によると、異なるハッシュコードは異なるコードを生成する可能性があります。
索引
** これは、エントリを1つのバケツに入れてから取得しようとすることを意味します。

他のバケツから出してください。そのようなロジックは

Hashtable

を壊します

  • 等しいキーは等しいハッシュコードを返さなければなりません。それが

    hashCode()

    メソッドをオーバーライドする理由です。

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

  • 同じキーでも異なるハッシュコードを返さないようにすることをお勧めします** それ以外の場合は同じバケットになります。これはパフォーマンスを低下させ、それゆえ

    Hashtable

    の利点のいくつかを失います。

また、

String



Integer



Long

などのラッパー型のキーについては気にしないでください。

equal()

メソッドと

hashCode()

メソッドは、どちらもラッパークラスですでにオーバーライドされています。


5繰り返し

ハッシュテーブル



__Hashtablesを繰り返すにはいくつかの方法があります。

__このセクションでは、それらについてよく話し、その意味について説明します。


5.1. 速く失敗する:

繰り返し


フェイルファスト反復は、

Hashtable



__Iterator


が作成された後に変更された場合、

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

を作成します。

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

そして3番目に、テーブルを変更します。

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

は、たとえば1つのスレッドがテーブルを反復処理しているときに別のスレッドがそれを同時に修正しようとしているときに、バグを見つけて予測できない動作を回避するのに役立ちます。


5.2. 早く失敗しない:

列挙



Hashtable



Enumeration

は、高速ではありません。例を見てみましょう。

まず、

Hashtable

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

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

次に、

Enumeration

を作成しましょう。

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.

Hashtable



HashMap



Hashtable



HashMap

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

どちらも以下を提供します。

  • 高速反復

  • 予測不可能な繰り返し順序

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


  • HashMap



    Enumerationを提供していませんが、Hashtable

    は提供していません

高速ではありません
**

Hashtable



null

キーと

null

値を許可しませんが、


HashMap

は、1つの

null

キーと任意の数の

null

値を許可します。
**

Hashtable

’sメソッドは同期され、

HashMaps

’sメソッドは同期されます

ではない


7. Java 8の

Hashtable

API

Java 8では、コードをよりクリーンにするのに役立つ新しいメソッドが導入されました。特に、いくつかの

if

ブロックを取り除くことができます。これを実証しましょう。


7.1.

getOrDefault()


「dog____」という単語の定義を取得し、テーブルにある場合はそれを変数に割り当てる必要があるとしましょう。そうでなければ、変数に “not found”を代入してください。

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.

マージ()


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

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結論

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

さらに、衝突とは何か、および

Hashtableに含まれる負荷率について説明しました。また、キーオブジェクトに対して

equals()



hashCode()__をオーバーライドする理由を説明しました。

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

いつものように、完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[on Github]から入手できます。