ハッシュ化

ハッシュ化は非常に効率的です。ハッシュを使用した要素の検索、挿入、削除には O(1) 時間がかかります。バランスの取れた検索ツリーでは、O(log n) 時間で要素を見つけることができます。コンテナ内の要素を検索するより効率的な方法はありますか?この章では、ハッシュと呼ばれる手法を紹介します。ハッシュを使用すると、O(1) 時間で要素の検索、挿入、削除を行うマップまたはセットを実装できます。

ハッシュとは何ですか?

ハッシュでは、ハッシュ関数を使用してキーをインデックスにマップします。ハッシュを紹介する前に、ハッシュを使用して実装されるデータ構造であるマップについて確認してみましょう。 map (セクションで紹介) はエントリを格納するコンテナ オブジェクトであることを思い出してください。各エントリには、キーと値の 2 つの部分が含まれています。このキーは検索キーとも呼ばれ、対応する値を検索するために使用されます。たとえば、単語がキー、単語の定義が値であるマップに辞書を保存できます。

マップは、辞書、ハッシュ テーブル、または 連想配列とも呼ばれます。

Java Collections Framework は、マップをモデリングするための java.util.Map インターフェースを定義します。 3 つの具体的な実装は、java.util.HashMap、java.util.LinkedHashMap、および java.util.TreeMap です。 java.util.HashMap はハッシュを使用して実装され、java.util.LinkedHashMap は LinkedList を使用して実装され、java.util.TreeMap は red を使用して実装されます。 -黒い木々。

配列内の要素のインデックスがわかっている場合は、そのインデックスを使用して O(1) 時間で要素を取得できます。ということは、値を配列に格納し、そのキーをインデックスとして使用して値を検索できるということでしょうか?キーをインデックスにマッピングできれば、答えは「はい」です。値を格納する配列はハッシュ テーブルと呼ばれます。キーをハッシュ テーブル内のインデックスにマッピングする関数は、ハッシュ関数 と呼ばれます。以下の図に示すように、ハッシュ関数はキーからインデックスを取得し、そのインデックスを使用してキーの値を取得します。 ハッシュ化とは、検索を行わずにキーから取得したインデックスを利用して値を取得する手法です。

キーからインデックスを生成するハッシュ関数はどのように設計しますか?理想的には、各検索キーをハッシュ テーブル内の異なるインデックスにマップする関数を設計したいと考えています。このような関数は完全ハッシュ関数と呼ばれます。ただし、完全なハッシュ関数を見つけるのは困難です。 2 つ以上のキーが同じハッシュ値にマッピングされている場合、衝突が発生したといいます。この章で後ほど説明するように、衝突に対処する方法はありますが、最初から衝突を回避することをお勧めします。したがって、衝突を最小限に抑える、高速で計算が簡単なハッシュ関数を設計する必要があります。

以上がハッシュ化の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。