5

1 ～ 15 バイトの範囲のバイト シーケンス (文字列) でキーを検索するハッシュ テーブルを作成したいと考えています。

整数値を格納したいので、ハッシュ用の配列で十分だと思います。特定のキーが配列にインデックスを与えるようなハッシュ関数を構築する方法を概念化するのに苦労しています。

どんな援助でも大歓迎です。

ハッシュ内のエントリの最大数は、4081*15 + 4081*14 + ... 4081 = 4081((15*(16))/2) = 489720 です。

たとえば、次のようになります。

int table[489720];

int lookup(unsigned char *key)
{
    int index = hash(key);
    return table[index];
}

ハッシュ関数の適切な選択肢は何ですか? または、ハッシュ関数を構築するにはどうすればよいですか?

ありがとう。

4

4 に答える 4

3

C 文字列をハッシュするために、私は常にこの関数を使用してきました (ハッシュ テーブルのサイズの結果を取得します)。

int hashstring(const char* s) {
  int key = 0;
  while (*s) {
    key = key*37 + *s++;
  }
  return key;
}

最初にどこから手に入れたのか覚えていませんが、何年もの間、私を失望させていません.

于 2011-02-22T08:03:23.113 に答える
2

キー空間は大きい (約 2^(8*15)) ため、完全なハッシュが必要な場合は、489720 個の実際のキーが表示されることを事前に知っておく必要があります。それでも、はるかに大きなテーブル (つまり非常に低い負荷率) を許可したとしても、これらのキーの完全なハッシュを見つけることは事実上不可能です。私が知っている完全なハッシュを見つける唯一の方法は、試行錯誤によるものであり、テーブルに 489720^2 エントリが近くない限り、ランダム ハッシュは失敗する可能性があります。

通常の（完全ではない）ハッシュを使用し、衝突を適切に処理することを強くお勧めします。

struct entry {
  unsigned char *key;
  int value;
  struct entry *next;
} *table[1<<20];
int lookup(unsigned char *key) {
  int index = hash(key) % (1<<20);
  for (struct entry *e = table[index]; e != NULL; e = e->next) {
    if (!strcmp(key, e->key)) return e->value;
  }
  // not found
}

また、これを自分で実装しないことをお勧めします - c++ hashmapのような標準ライブラリを使用してください。

于 2010-06-02T23:43:07.663 に答える
0

完全ハッシュが必要な場合は、ウィキペディアの完全ハッシュに関する記事を読むことから始めることができます。思わぬ障害に遭遇した場合は、ここで助けを求めることができます。

于 2010-06-02T23:02:49.573 に答える
0

テーブルに常駐する文字列の平均数が少ない場合 (10,000 エントリ未満など)、最新の CPU アーキテクチャ上にある場合は線形検索を使用しても、連想配列が妥当なアプローチになります。

それ以外の場合、「完全なハッシュ」を構築するには、文字列の各文字を検査し、可能な範囲に基づいて一意の値を計算する必要があります。たとえば、キーで A..Z の 26 文字のみが許可されている場合、これは機能します。

int
hash (const char *key)
{
   int h = 0;
   while (key && *key)
       h = h * 26 + (*key++ - 'A');
   return h;
}
于 2010-06-02T23:07:20.153 に答える