ハッシュバケット

コンピューティングにおけるハッシュテーブル [ハッシュマップ] とは、キー [一意の文字列または整数] に基づいてオブジェクトに事実上直接アクセスできるデータ構造です。ハッシュテーブルは、バケットやスロットの配列にインデックス計算を行うために、ハッシュ関数を使用し、そこから目的の値をみつけます。使用されるキーの主な特徴は次のとおりです。

• 社会保障番号、電話番号、口座番号などのキーを使用します。
• キーは一意である必要があります。
• 各キーは、値に関連付け（マッピング）されます。

ハッシュバケットは、ソートや検索の目的でデータ項目を割り当てる場合に使用されます。この作業の目的は、短い時間枠で、特定の項目の検索にアクセスできるように、リンクリストを弱めることです。バケットを使用するハッシュテーブルは、実際には配列とリンクリストの組み合わせです。配列 [ハッシュテーブル] の各要素は、リンクリストのヘッダーです。同じ場所にハッシュされる要素は、全てリストに格納されます。ハッシュ関数は、1つのバケットの中の最初のスロットに各レコードを割り当てます。スロットが埋まっている場合、空きスロットが見つかるまでバケットのスロットが順番に検索されます。バケットが埋まっている場合、レコードはテーブルの最後にある無限のオーバーフローバケットに格納されます。全てのバケットが同じオーバーフローバケットを共有します。ただし、優れた実装では、バケット間でレコードを均等に分散するハッシュ関数を使用して、オーバーフローバケットに入るレコードをできるだけ最小限にしています。