リンクされたリストが遅すぎる場合、通常の答えはハッシュ テーブルを実装することです。データ構造とアルゴリズムには、非常に多くの可能なバリエーションがあります。オープンな "single"-hashingについてだけ説明します。これは、私が最もよく知っているバリエーションです。
したがって、オープン ハッシュ テーブルでは、テーブルは単なる配列です (「クローズド」ハッシュにも配列がありますが、各要素はリンクされたリストです)。パフォーマンス上の理由から、アレイはせいぜい約半分まで使用する必要があります。また、最大容量では、満たされたテーブルには実際にはまだ 1 つの空のスロットがあります。これは、アルゴリズムが単純化されるためです。
キー値の型を受け入れ、整数を返すハッシュ関数も必要です。クラスター化されたキーと全体的なパフォーマンスに関して、ハッシュ関数がどのように動作するかを予測することは非常に困難です。したがって、後で簡単に変更できる独立した機能であることを確認してください。すべてのバイトをシフトアラウンドしてそれらを加算するのと同じくらい簡単です。
int hash (char *key, int key_length, int table_size)
{
int ret, i;
for (i=0, ret=0; i < key_length; i++)
{
ret += key[i] << i;
}
return abs(ret) % table_size;
}
テーブル ルックアップ関数は、ハッシュ関数を使用して、配列内の検索を開始する場所を決定します。そこにキーが見つからない場合 (memcmp()
実際の検索キーとテーブル内のその位置に格納されているキーに対して a を実行することによって決定されます)、配列の末尾から先頭に戻って、連続する各キーを調べます。空のテーブル要素が見つかった場合、失敗を宣言します。
#define RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY \
if (memcmp(table + i, &key, sizeof key) == 0 || (key_type)table[i] == 0) \
return table + i;
key_value_pair *hash_lookup(key_value_pair *table, int table_size, key_type key)
{
int h, i;
h = hash(&key, sizeof key, table_size);
i = h;
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
for ( ; i < table_size; i++)
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
for (i=0; i < h; i++)
RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
return NULL;
}
いくつかの癖を処理するために、この関数の前にもう 1 つの関数が必要です。キーが見つからないだけでなく、テーブル自体がいっぱいであることを示す NULL ポインターを返す場合があります。オーバーフル テーブル。これは実際には「完全に満杯」を意味しますが、「満杯」のテーブルには実際には 1 つの空の要素が必要であると以前に判断しました。これは、両方のfor
ループが最後まで実行されないことを意味します。空のテーブル位置が見つかった場合、それは失敗です。テーブルがいっぱいになると、キーが存在しないことを発見する前にテーブル全体をスキャンする必要があるため、ハッシュを使用することによるパフォーマンスの利点の多くがまったく失われます。
ルックアップ関数は、空のスロットへの有効なポインターを返すこともできます。これも値が見つからないことですが、エラーではありません。初めてキーと値のペアを追加する場合、これはそれを格納するスロットになります。
または、目的のテーブル要素へのポインターを返すこともできます。これは、配列であろうと連結リストであろうと、線形検索よりも高速です。
テーブルからキーを削除するには、シーケンス内の空いた位置を埋める必要があります。いくつかのオプションがあります。
テーブルのスペースが不足する心配がない場合 (テーブルは非常に大きく設定されており、有効期間と使用量を制御できます)、空のキーとは異なり、削除された特別なキーでエントリを上書きできます。
または、スペースも再利用したい場合は、キーを検索してから、残りの「チェーン」(次の空のスロットまでのキーのシーケンス (ラップアラウンドを含む)) をスキャンして移動する必要があります。削除するキーの位置に一致するハッシュを持つ最後のキー。次に、この移動したキー/値の位置を空のキーで上書きします。.... おっとっと!チェーンの最後のキーを実際にクリアするまで、この最後の一致するキーに対してこのプロセスを繰り返す必要があります。(今すぐ実装でこれを修正する必要があります!....)