ハッシュテーブルは、アプリケーションのパフォーマンスを最適化する便利な方法を提供します。
ハッシュテーブルは、コンピュータ分野では新しい概念ではありません。これらは、今日の基準からすると非常に遅いコンピューター処理を高速化するように設計されており、多くのデータ エントリをクエリするときに特定のエントリをすばやく見つけることができます。 最新のマシンは何千倍も高速ですが、ハッシュテーブルはアプリケーションから最高のパフォーマンスを引き出すための便利なツールです。
約 1,000 件のレコード (中小企業の顧客レコードなど) を含むデータ ファイルと、そのレコードをメモリに読み込んで処理するプログラムがあると想像してください。各レコードには、一意の 5 桁の顧客 ID 番号、顧客名、住所、口座残高などが含まれます。レコードが顧客 ID 番号によってソートされていないと仮定します。したがって、プログラムが顧客番号を「キー」として使用して特定の顧客レコードを見つけたい場合、それを見つける唯一の方法は各レコードを連続して検索することです。必要なレコードがすぐに見つかる場合もありますが、プログラムが必要なレコードを見つける前に、ほとんど最後のレコードを検索してしまう場合もあります。 1,000 レコードの中から検索する場合、1 つのレコードを見つけるには、プログラムは平均 500.5 ((1000 + 1)/2) レコードをチェックする必要があります。データを頻繁に検索する必要がある場合は、レコードをより迅速に検索する方法が必要になる場合があります。
検索を高速化する 1 つの方法は、レコードを分割して、1 つの大きなリストを検索する代わりに、複数の短いリストを検索することです。数値の顧客 ID 番号の場合は、0 で始まる ID 番号のリスト 1 つ、1 で始まる ID 番号のリスト 1 つなど、10 個のリストを作成できます。したがって、顧客 ID 番号 38016 を見つけるには、3 から始まるリストを検索するだけで済みます。 レコードが 1,000 件あり、各リストの平均長が 100 の場合 (1,000 レコードが 10 のリストに分割される)、レコードを検索するための平均比較数は約 50 に減少します (図 1 を参照)。
もちろん、顧客番号の約 10 分の 1 が 0 で始まり、さらに 10 分の 1 が 1 で始まる場合、このアプローチはうまく機能します。顧客番号の 90% が 0 で始まる場合、そのリストには 900 件のレコードが含まれ、検索ごとに平均 450 件の比較が必要になります。さらに、プログラムが実行する必要がある検索の 90% は、0 で始まる数値に対するものです。したがって、平均比較数値は単純な数学的演算の範囲をはるかに超えています。
キー値の数値の分布に関係なく、各リストにほぼ同じエントリが含まれるようにリスト内のレコードを分散できれば、より良いでしょう。顧客数を統合し、結果をより適切に分散する方法が必要です。たとえば、数値の各桁を取得し、それに大きな数値 (桁の位置によって異なります) を掛け、その結果を加算して合計を出し、この数値を 10 で割って、その余りをインデックスとして与えることができます。値（インデックス）。レコードが読み込まれると、プログラムは顧客番号に対してこのハッシュ関数を実行し、そのレコードがどのリストに属しているかを判断します。ユーザーがクエリを行う必要がある場合、正しいリストを検索できるように、同じハッシュ関数が顧客番号の「キー」として使用されます。このようなデータ構造をハッシュテーブルと呼びます。
Javaのハッシュテーブル
Java には、多目的ハッシュテーブル メカニズムを提供するjava.util.Hashtableとjava.util.HashMapという 2 つのクラスが含まれています。 2 つのクラスは非常に似ており、通常は同じパブリック インターフェイスを提供します。ただし、これらにはいくつかの重要な違いがあります。それについては後ほど説明します。
Hashtable オブジェクトと HashMap オブジェクトを使用すると、キーと値を組み合わせ、 put () メソッドを使用してキーと値のペアをテーブルに入力できます。その後、 get() メソッドを呼び出し、キーをパラメーターとして渡すことで値を取得できます。キーと値は、2 つの基本要件を満たす限り、任意のオブジェクトにすることができます。キーと値はオブジェクトである必要があるため、プリミティブ型は Integer(int) などのメソッドを使用してオブジェクトに変換する必要があることに注意してください。
特定のクラスのオブジェクトをキーとして使用するには、クラスが 2 つのメソッド、equals() と hashCode() を提供する必要があります。これら 2 つのメソッドはjava.lang.Objectにあるため、すべてのクラスがこれら 2 つのメソッドを継承できますが、Object クラスでのこれら 2 つのメソッドの実装は通常役に立たないため、通常はこれら 2 つのメソッドを自分でオーバーロードする必要があります。
Equals () メソッドは、そのオブジェクトと別のオブジェクトを比較し、2 つのオブジェクトが同じ情報を表す場合に true を返します。このメソッドは、両方のオブジェクトが同じクラスに属しているかどうかも確認します。 2 つの参照オブジェクトが同一のオブジェクトである場合、Object.equals() は true を返します。これが、このメソッドが一般に適切ではない理由を説明しています。ほとんどの場合、フィールドごとに比較する方法が必要となるため、同じデータを表す異なるオブジェクトは等しいと見なされます。
HashCode() メソッドは、オブジェクトの内容を使用してハッシュ関数を実行することにより、int 値を生成します。 Hashtable と HashMap は、この値を使用して、キーと値のペアがどのバケット (またはリスト) にあるかを判断します。
例として、String クラスを見てみましょう。このクラスには、これら 2 つのメソッドを実装する独自のメソッドがあります。 String.equals() は 2 つの String オブジェクトを 1 文字ずつ比較し、文字列が同じ場合に true を返します。
次のようにコードをコピーします。
文字列 myName = "アインシュタイン";
// 次のテストは
// 常に真
if ( myName.equals("Einstein") )
{ ...
String.hashCode() は文字列に対してハッシュ関数を実行します。文字列内の各文字の数値コードは 31 倍され、結果は文字列内の文字の位置によって異なります。これらの計算の結果が加算されて合計が得られます。このプロセスは複雑に見えるかもしれませんが、値のより適切な分散が保証されます。また、独自の hashCode() メソッドを開発するときに、結果が一意であることを確信してどこまでできるかも示します。
たとえば、ハッシュテーブルを使用して書籍カタログを実装し、書籍の ISBN 番号を検索キーとして使用して検索したいとします。 String クラスを使用して詳細を伝え、equals() メソッドと hashCode() メソッドを準備できます (リスト 1 を参照)。 put () メソッドを使用して、キーと値のペアをハッシュテーブルに追加できます (リスト 2 を参照)。
Put () メソッドは 2 つのパラメーターを受け取り、どちらも Object 型です。最初のパラメータはキー、2 番目のパラメータは値です。 Put () メソッドはキーの hashCode() メソッドを呼び出し、結果をテーブル内のリストの数で除算します。残りをインデックス値として使用して、レコードをどのリストに追加するかを決定します。キーはテーブル内で一意であることに注意してください。既存のキーを使用してput () を呼び出すと、一致するエントリが新しい値を参照するように変更され、古い値が返されます (キーがテーブル内に存在しない場合)。 、 put () は null 値を返します)。
テーブルから値を読み取るには、get() メソッドで検索キーを使用します。正しい型に変換されたオブジェクト参照を返します。
次のようにコードをコピーします。
ブックレコード br =
(ブックレコード)isbnTable.get(
"0-345-40946-9");
System.out.println(
「著者:」 + br.author
+ " タイトル: " + br.title);
もう 1 つの便利なメソッドは、remove() です。これは、get() とほぼ同じように使用され、テーブルからエントリを削除し、呼び出し側プログラムに返します。
自分のクラス
プリミティブ型をキーとして使用する場合は、同じ型のオブジェクトを作成する必要があります。たとえば、整数キーを使用する場合は、コンストラクター Integer(int) を使用して整数からオブジェクトを生成する必要があります。 Integer、Float、Boolean などのすべてのラッパー クラスは、プリミティブ値をオブジェクトとして扱い、equals() メソッドと hashCode() メソッドをオーバーロードするため、キーとして使用できます。 JDK で提供される他の多くのクラスもこれに似ています (Hashtable クラスと HashMap クラスでも独自の equals() メソッドと hashCode() メソッドを実装しています) が、クラスのオブジェクトをハッシュテーブル キーとして使用する前にドキュメントを確認する必要があります。また、クラスのソースをチェックして、equals() と hashCode() がどのように実装されているかを確認する必要があります。たとえば、Byte、Character、Short、および Integer はすべて、表された整数値をハッシュ コードとして返します。これは、ニーズに合う場合もあれば、合わない場合もあります。
Javaでのハッシュテーブルの使用
キーとして定義したクラスのオブジェクトを使用するハッシュテーブルを作成する場合は、そのクラスの equals() メソッドと hashCode() メソッドが有用な値を提供することを確認する必要があります。まず、拡張するクラスを調べて、その実装がニーズを満たしているかどうかを判断します。そうでない場合は、メソッドをオーバーロードする必要があります。
quals() メソッドの基本的な設計上の制約は、渡されたオブジェクトが同じクラスに属し、そのデータ フィールドが同じデータを表す値に設定されている場合に true を返す必要があるということです。また、メソッドに空の引数を渡した場合、コードが戻り値を返すことを確認する必要があります。
次のようにコードをコピーします。
false：パブリックブール値と等しい(オブジェクトo)
{
if ( (o == null)
|| !(myClass のインスタンス))
{
false を返します。
}
// データ フィールドを比較します...
さらに、 hashCode() メソッドを設計するときに留意すべきルールがいくつかあります。まず、メソッドは、メソッドが何回呼び出されたかに関係なく、特定のオブジェクトに対して同じ値を返さなければなりません (もちろん、呼び出し間でオブジェクトの内容が変更されない限り)。オブジェクトをハッシュテーブル キーとして使用する場合、これは次のようにする必要があります。避けてください）。次に、equals() メソッドで定義された 2 つのオブジェクトが等しい場合、それらは同じハッシュ コードも生成する必要があります。 3 番目に、これは原則というよりガイドラインですが、オブジェクトの内容ごとに異なる結果が生成されるようにメソッドを設計する必要があります。時折、異なるオブジェクトが同じハッシュ コードを生成することがあっても問題ありません。ただし、メソッドが 1 から 10 の範囲の値しか返せない場合、ハッシュテーブル内のリストの数に関係なく、使用できるリストは 10 個のみになります。
equals() と hashCode() を設計するときに留意すべきもう 1 つの要素はパフォーマンスです。 put () または get() を呼び出すたびに、正しいリストを見つけるために hashCode() を呼び出す必要があります。 get() がリストをスキャンしてキーを見つけるとき、リスト内の各要素に対して equals() を呼び出します。実行速度が重要となる高パフォーマンスのアプリケーションで他のユーザーがクラスを使用する可能性があるため、クラスを公開する予定がある場合は特に、これらのメソッドができるだけ速く効率的に実行されるように実装します。
ハッシュテーブルのパフォーマンス
ハッシュテーブルの効率に影響を与える主な要因はテーブル内のリストの平均長です。平均検索時間はこの平均長に直接関係しているためです。平均長を短くするには、ハッシュテーブル内のリストの数を増やす必要があるのは明らかです。リストの数が多すぎて、ほとんどまたはすべてのリストに 1 つのレコードしか含まれていない場合に、最高の検索効率が得られます。しかし、これは行き過ぎかもしれません。ハッシュテーブルにデータエントリよりもはるかに多くのリストが含まれている場合は、そのようなメモリコストを支払う必要はなく、場合によっては、人々がこのアプローチを受け入れることが不可能です。
前の例では、レコード数が 1,000 であることが事前にわかっていました。これを知ることで、検索速度とメモリ使用効率の最適な妥協点を達成するためにハッシュテーブルに含めるリストの数を決定できます。ただし、多くの場合、処理するレコードの数は事前にわかりません。データの読み取り元のファイルが継続的に増加する可能性や、レコード数が日ごとに大幅に変化する可能性があります。
Hashtable クラスと HashMap クラスは、エントリの追加に応じてテーブルを動的に拡張することで、この問題に対処します。どちらのクラスにも、テーブル内のリストの初期数と負荷係数をパラメーターとして受け入れるコンストラクターがあります。
パブリックハッシュテーブル(
int の初期容量、
浮動小数点負荷係数)
パブリックハッシュマップ(
int の初期容量、
浮動小数点負荷係数)
これら 2 つの数値を乗算して、臨界値を計算します。新しいエントリがハッシュ テーブルに追加されるたびにカウントが更新され、カウントが臨界値を超えるとテーブルがリセット (再ハッシュ) されます。 (リスト サイズは前のサイズの 2 倍に 1 を加えた値に増加し、すべてのエントリが正しいリストに移動されます。) デフォルトのコンストラクターは初期容量を 11 に設定し、負荷係数を 0.75 に設定するため、重要な値は 8 です。 9 番目のレコードがテーブルに追加されると、ハッシュ テーブルが 23 個のリストを持つように再スケールされ、新しい臨界値は 17 (23*0.75 の整数部分) になります。負荷係数は、ハッシュ テーブル内のリストの平均数の上限であることがわかります。これは、デフォルトでは、ハッシュ テーブルに複数のレコードを含む多数のリストが含まれることはほとんどないことを意味します。元の例と比較してください。1,000 レコードが 10 のリストに分散されていました。デフォルト値を使用すると、このテーブルは 1,500 を超えるリストを含むように拡張されます。しかし、これはコントロールできます。負荷係数を掛けたリストの数が処理中のエントリの数より大きい場合、テーブルは再作成されないため、次の例に従うことができます。
次のようにコードをコピーします。
// テーブルはそれまで再ハッシュされません
// エントリが 1,100 個あります (10*110):
ハッシュテーブル myHashTable =
新しいハッシュテーブル(10, 110.0F);
空のリスト用にメモリを節約したくなく、余分な検索時間が気にならない場合 (組み込みシステムではそうである可能性があります) を除いて、おそらくこれを行う必要はありません。ただし、リセットには計算コストがかかり、このアプローチによりリセットが発生しないことが保証されるため、このアプローチは便利です。
put () を呼び出すとテーブルが大きくなる (リストの数が増える) 可能性がありますが、remove() を呼び出しても逆の効果は生じないことに注意してください。したがって、大きなテーブルがあり、そこからほとんどのエントリを削除すると、最終的には大きなテーブルがほとんど空になります。
ハッシュテーブルとハッシュマップ
Hashtable クラスと HashMap クラスの間には 3 つの重要な違いがあります。最初の違いは主に歴史的な理由によるものです。 Hashtable は古い Dictionary クラスに基づいており、HashMap はJava 1.2 で導入されたMapインターフェイスの実装です。
おそらく最も重要な違いは、Hashtable のメソッドは同期的であるのに対し、HashMap のメソッドは同期的ではないことです。つまり、特別な操作を行わずにマルチスレッド アプリケーションで Hashtable を使用できますが、同様に HashMap に対して外部同期を提供する必要があります。便利な方法は、Collections クラスの静的 synchronizedMap() メソッドを使用することです。このメソッドは、スレッドセーフなMapオブジェクトを作成し、それをカプセル化されたオブジェクトとして返します。このオブジェクトのメソッドを使用すると、基になる HashMap に同期的にアクセスできます。この結果、必要のないとき (シングル スレッド アプリケーションなど) にハッシュテーブルの同期を切断できなくなり、同期により多くの処理オーバーヘッドが追加されます。
3 番目の違いは、テーブル エントリのキーまたは値として null 値を使用できるのは HashMap だけであることです。 HashMap 内の空のキーにできるレコードは 1 つだけですが、任意の数のエントリを空の値にすることができます。これは、検索キーがテーブル内に見つからない場合、または検索キーが見つかってもそれが null 値である場合、get() は null を返すことを意味します。必要に応じて、containKey() メソッドを使用して 2 つの状況を区別します。
一部の情報では、同期が必要な場合は Hashtable を使用し、それ以外の場合は HashMap を使用することを示唆しています。ただし、HashMap は必要なときに同期できること、Hashtable よりも多くの機能を備えていること、古いクラスに基づいていないことなどから、さまざまな状況で Hashtable よりも HashMap の方が好まれると考える人もいます。
プロパティについて
場合によっては、ハッシュテーブルを使用してキー文字列を値文字列にマップしたい場合があります。 DOS、Windows、Unix には環境文字列の例がいくつかあります。たとえば、キー文字列 PATH は値文字列 C:/WINDOWS;C:/WINDOWS/SYSTEM にマップされます。ハッシュテーブルはこれらを表現する簡単な方法ですが、 Java には別の方法が用意されています。
Java .util.Properties クラスは、文字列キーと値で使用するために設計された Hashtable のサブクラスです。 Properties オブジェクトの使用法は Hashtable の使用法と似ていますが、クラスには知っておくべき 2 つの時間節約メソッドが追加されています。
Store() メソッドは、Properties オブジェクトの内容を読み取り可能な形式でファイルに保存します。 Load() メソッドはその逆で、ファイルを読み取り、キーと値を含むように Properties オブジェクトを設定するために使用されます。
Properties は Hashtable を拡張するため、スーパークラスのput () メソッドを使用して String オブジェクトではないキーと値を追加できることに注意してください。これはお勧めできません。さらに、String オブジェクトを含まない Properties オブジェクトで store() を使用すると、store() は失敗します。 put () と get() の代わりに、String パラメータを取る setProperty() と getProperty() を使用する必要があります。
さて、ハッシュテーブルを使用して処理を高速化する方法を理解できたと思います。