ここ数か月間、私はコンピューターサイエンスの新しい概念ごとに1つの特徴があることに気づきました。それは、すべてのことに欠点があるということです。この観察はハッシュテーブルにも当てはまります。何が優れたハッシュテーブルを構成するのかを見てみましょう。
Contents
優れたハッシュテーブルの主要コンポーネント
優れたハッシュテーブルには、次のようなハッシュ関数が必要です。
1.計算が簡単です。
2.衝突を回避します。
3.値が与えられるたびに同じキーを返し、すべての入力データを使用します。
計算が簡単な関数
複雑な関数は時間とスペースを大量に消費し、効率的なデータ構造の目的を損なうため、ハッシュ関数は計算が簡単である必要があります。
すべてのデータの処理
この関数は、大量のデータを迅速に保存する効率を維持するために、すべてのデータを処理し、適切に保存する必要があります。
一貫したキーの返却
ハッシュ関数が一貫して同じキーを返さない場合、データを取得することは不可能になります。
衝突の回避
2つの要素が配列内の同じ場所に挿入されると、衝突が発生します。ほぼすべてのハッシュ関数で衝突が発生します。各入力値を一意のハッシュバケットにマッピングする完全なハッシュ関数は、まれです。
衝突解決の戦術
リニアプロービング
このメソッドは、次の空のハッシュバケットを見つけて衝突を処理します。次のバケットがいっぱいの場合、関数は空のバケットが見つかるまで調査を続けます。このアプローチは、データがハッシュテーブルの1つの領域にグループ化されるクラスタリングにつながる可能性があります。
クラスタリング
クラスタリングは、ハッシュテーブルの設計が不適切であることを示します。これは、ハッシュ関数がテーブル範囲全体を使用していない場合、またはデータが均等に分散されていない場合に発生します。
連鎖
チェーン化では、リンクリストを使用して複数の要素を1つのキーに保存します。リンクリストの検索には時間がかかりますが、ハッシュ関数が要素を均等に分散する場合、平均して一定の検索時間になります。
優れたハッシュ関数の威力
優れたハッシュ関数は強力なハッシュテーブルを作成します。Ananda Gunawardena教授が説明しているように、関数は計算が簡単で、衝突を可能な限り回避する必要があります。優れたハッシュ関数を使用したとしても、ある程度の衝突は避けられません。
現実世界のアプリケーション
ハッシュテーブルはコンピューティングで広く使用されています。たとえば、UnixおよびLinuxシステムは、内部ハッシュテーブルを使用して、「PATH」変数によって参照されるディレクトリの内容を保存します。
例:スペルチェッカーの実装
ハッシュテーブルを使用すると、スペルチェッカーを効率的に実装できます。辞書内のすべての単語をハッシュすることにより、辞書のサイズに関係なく、単語の存在を迅速かつ効率的にチェックできます。
リソース
ハッシュ関数はよく研究されています。これらに興味がある場合は、多数のリソースで深い知識を得ることができます。
- ハッシュ関数:優れたハッシュテーブルへの鍵。
- 衝突:一般的であり、解決が必要です。
- チェーンとプロービング:衝突を処理するテクニック。
- スペルチェッカー:ハッシュテーブルの実用的なアプリケーション。