Java.util.Hashtableクラスの紹介
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]から入手できます。
