2

私はたくさんの異なるアイテムを数える必要があります。次のようなペアのリストを処理しています。

A34223,34
B23423,-23
23423212,16

私が計画していたのは、最初の値 (キー) を 32 ビット整数にハッシュすることでした。これは、「値」が追加され (すべてゼロから始まる) 数になり、負になるスパース構造のキーになります。

キーが短く英数字であることを考えると、32 ビット x86 アーキテクチャで高速なハッシュ アルゴリズムを生成する方法はありますか? または既存の適切なハッシュはありますか?

ハッシュの設計については何も知りませんが、入力が単純​​であるため、特定のキー長「X」に対して衝突がないことを保証し、分散が高い高性能ハッシュを生成する方法があることを期待していました長さが「X」を超えると、衝突が最小限に抑えられます。

4

3 に答える 3

8

C++ を使用しているため、最初にすべきことは、std::map を使用して単純な実装を作成することです。それは十分に速いですか（おそらくそうなるでしょう）？そうでない場合は、C++ 実装でハッシュ テーブルが提供されているかどうかを調べてください。もしそうなら、それを使って簡単な実装を作成し、テストし、時間を計ってください。それは十分に速いですか（ほぼ確実にそうです）？

これらのオプションを使い果たした後でのみ、独自のハッシュ テーブルとハッシュ関数の実装を考える必要があります。

于 2009-06-05T13:36:07.027 に答える
1

衝突がないことを保証することは困難です。

あなたの場合、キー

A34223
B23423
23423212

ほとんど手間をかけずに 32 ビット整数に変換できます。

そして、これは文字列からハッシュを生成する優れた関数です:

/**
 *  "The Practice of Programming", Hash Tables, section 2.9, pg. 57
 *
 *  computes hash value of string
 */
DWORD
strhash( char* str )
{
  //#define MULTIPLIER 31 or 37
  unsigned int   h;
  unsigned char* p;

  h = 0;
  for ( p=(unsigned char*)str; *p != '\0'; p++ )
    h = 31 * h + *p; // <- FIXED MULTIPLIER

  return h;
}
于 2009-06-05T13:41:56.347 に答える
1

適切なハッシュ関数については、Bob Jenkin の Web サイトを確認してください。IIRC Perl で使用されるのと同じハッシュです。

于 2009-06-05T13:45:43.513 に答える