ハッシュテーブルとは？

コンピューターサイエンスでは、ハッシュテーブルはキーと呼ばれる値のリストで構成されるデータを格納するためのデータ構造であり、配列と呼ばれる対応する値のリストとペアになります。 たとえば、ビジネス名は住所とペアになる場合があります。 通常、配列内の各値には、ハッシュと呼ばれる位置番号があります。 ハッシュ関数は通常、各キー値をハッシュにマップする一連の命令またはアルゴリズムです。たとえば、ビジネス名を住所、電話番号、ビジネスカテゴリに接続します。 ハッシュ関数の目的は、各キーを配列内の一意の対応する値に割り当てることです。 これは一般にハッシュと呼ばれます。 ハッシュ関数が適切に機能するには、ハッシュテーブルが適切にフォーマットされている必要があります。

一連のデータに対するハッシュテーブルのパフォーマンスは、そのハッシュ関数の効率に依存します。 通常、適切なハッシュ関数は、キーの均一なルックアップと、対応する配列内のマッピングの均等な分布を提供します。 2つのキーが同じ対応する値に割り当てられると、ハッシュ衝突が発生します。 ハッシュ衝突が発生すると、通常、一意の対応する値が見つかるまでハッシュ関数が再度実行されます。 これにより、通常、ハッシュ時間が長くなります。 ハッシュテーブル内のキーの数は通常固定されていますが、重複キーが存在する場合があります。 それでも、適切に設計されたハッシュテーブルには、各キーを配列内の一意の対応する値にマッピングする効果的なハッシュ関数があります。

ハッシュテーブル内の非効率的なハッシュ関数もマッピングのクラスターを生成する場合があります。 ハッシュ関数が既存のキーのマッピングのクラスターを作成すると、対応する値を検索するのにかかる時間が長くなる可能性があります。 通常、ほとんどのハッシュ関数は配列内で次に使用可能な位置を探すため、これにより将来のキーのハッシュが遅くなる可能性があります。 値の大きなクラスターが既に割り当てられている場合、通常、新しいキーの割り当てられていない値を探すのにはるかに時間がかかります。

負荷係数は、ハッシュ関数の効率に関連するもう1つの概念です。 負荷係数は、ハッシュテーブル内の対応する配列の全体サイズに対する既存のハッシュの量です。 通常、すでに割り当てられているキーの数を対応する配列のサイズで割ることによって定義されます。 負荷係数が増加しても、適切なハッシュ関数は通常、特定のポイントまで一定数の衝突とクラスターを維持します。 多くの場合、このしきい値を使用して、指定された数のキーに対するハッシュ関数の効率と、新しいハッシュ関数が必要になるタイミングを判断できます。

多くのコンピューターサイエンスの研究者は、完全なハッシュ関数（負荷係数が増加しても衝突やクラスターを生成しない関数）の生成に努めてきました。 理論的には、完全なハッシュテーブルを作成するための鍵は、完全なハッシュ関数を作成することです。 一般に、研究者は、完全なハッシュ関数が一定のパフォーマンス（衝突とクラスターの数）を持ち、負荷係数が増加すると考えています。 最悪のシナリオでは、完全なハッシュ関数により、しきい値に達することなく一定のハッシュが可能になります。