連想配列とは

ハッシュテーブルまたはハッシュマップとも呼ばれる連想配列は、配列のインデックスが整数ではなく文字列であることを除いて、標準配列に似ています。 多くのデータベースアプリケーションや、大量のデータを扱う他のプログラムでは、連想配列は効率的な方法で情報をソートおよびアクセスするための重要な要素です。 連想配列の中心には、通常の場合と同様に、整数でインデックス付けされた標準配列があります。 ハッシュ関数と呼ばれる特別なアルゴリズムは、文字列インデックスを整数インデックスに変換して値を見つけます。 これは一貫した変換であるため、実際の整数インデックスを保存する必要はなく、毎回必要に応じて文字列から計算されます。

連想配列を指すときに使用される用語は、通常の配列について話すときに使用される用語とわずかに異なる場合があります。 通常はインデックスと呼ばれるもの、つまり配列内の要素の数値的な位置はキーと呼ばれます。 キーに関連付けられたデータは値と呼ばれます。 これは、連想配列内で、キーが値に関連付けられていることを意味します。これは、データ構造内の標準配列の要素を参照するインデックスに関連付けられています。

すべての連想配列の中心にあるのはハッシュ関数です。 これは、キーに基づいて値の数値インデックスを決定するために使用されるアルゴリズムです。 ハッシュ関数にはいくつかのタイプがあり、整数であるキーで動作するように設計されたものと、文字列であるキーで動作するように設計されたものがあります。 整数キーの場合、一般的な方法は、キー値を配列のサイズで除算し、除算の残りを使用して、一意のインデックス値を取得することです。

ハッシュ関数は、文字列であるキーに対してはるかに複雑になる可能性があります。 いくつかの方法には、文字列内の各文字の数値を追加してから数値で除算する方法や、文字列の最初の数文字のみを使用して一意の数値を取得する方法があります。 文字列から数値を導出するには多くの方法があります。

連想配列で大量のキーと値のペアを扱う場合、発生する可能性のある問題の1つは衝突と呼ばれます。 衝突は、キーから派生した整数インデックスが別のキーの整数インデックスと同じ場合に発生します。 これらの2つのキーは、値配列内の同じインデックスを効果的に指します。 衝突にはさまざまな解決策があります。これは主に、ほとんどの実用的なアプリケーションで発生する可能性が高いためです。

衝突の解決策の1つは、各値のインデックスを実際にリンクリストにすることです。これにより、複数のキーがそのインデックスの場所を解決するときに、その場所に複数の値を保持できます。 これはチェーンと呼ばれ、衝突を処理する簡単な方法ですが、情報を取得するのにかかる時間を遅くすることもできます。 衝突に対処する別の方法は、線形プローブと呼ばれます。 衝突が発生すると、未使用のインデックスが見つかるまで値配列を移動することにより、線形プローブが機能します。 このソリューションは、連想配列にデータを均等に分散させるのに役立ちますが、値を検索するために必要な時間を増やすこともできます。