連想配列とは何ですか？

ハッシュテーブルまたはハッシュマップとも呼ばれる連想配列は、配列のインデックスが整数ではなく文字列になることを除いて、標準配列に似ています。多くのデータベースアプリケーションおよび大量のデータを扱う他のプログラムでは、連想配列は、効率的な方法で情報を並べ替えてアクセスするのに役立つ重要な要素です。連想配列のコアには、通常そうであるように、整数でインデックスが付けられた標準配列があります。 Hash関数と呼ばれる特別なアルゴリズムは、文字列インデックスを整数インデックスに変換して値を見つけます。これは一貫した変換であるため、実際の整数インデックスを保存する必要はありませんが、代わりに必要に応じて必要に応じて文字列から計算されます。通常、インデックスと呼ばれるもの - 配列内の要素の数値的位置 - は鍵。キーに関連付けられたデータは値と呼ばれます。これは、連想配列内で、キーが値に関連付けられていることを意味します。これは、データ構造の標準配列の要素を参照するインデックスに相関しています。

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

ハッシュ関数は、文字列であるキーの方がはるかに複雑です。いくつかの方法には、文字列内の各文字の数値を追加してから、ある数で除算することが含まれます。または、文字列の最初の数文字のみを使用して一意の数字を取得します。一連の文字列から数字を導き出す方法はたくさんあります。

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

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