44

C に固執する必要があり、C++ を使用できないため、boost:hash を使用できません。

しかし、多数 (10K から 100K) のトークン文字列 (5 から 40 バイトの長さ) をハッシュして、それらの中の検索を最速にする必要があります。

MD5、SHA1、または任意の長いハッシュ関数は単純なタスクには重すぎるようです。私は暗号化を行っていません。さらに、ストレージとコンピューティングのコストがかかります。

したがって、私の質問:

  1. ほとんどの実際のケースで衝突防止を保証する最も単純なハッシュ アルゴリズムは何でしょうか。

  2. ハッシュ値に使用するビット数は? 私は32ビットシステム用に開発しています。Perl/Python のハッシュ アルゴリズムも 32 ビット ハッシュを使用しますか? または、64 にジャンプする必要がありますか?

  3. 一般的なスクリプト言語でのハッシュ テーブルの実装について: 実装は衝突をチェックしますか、それともその部分を完全に回避できますか?

4

6 に答える 6

24

優れた (そして高速な) ハッシュ関数と興味深い読み物を以下で見つけることができます。http://www.azillionmonkeys.com/qed/hash.html

衝突をチェックしてはならない唯一のケースは、完全なハッシュ ( gperfのような古き良きルックアップ テーブル) を使用する場合です。

于 2009-04-13T14:04:18.937 に答える
11

  1. これは、最も注目すべき既知のハッシュ関数の概要です。

  2. 32ビットは問題なく動作するはずです。

  3. 面白いハッシュテーブルを書きたくない限り、常に衝突をチェックする必要があります:)

于 2009-04-13T14:02:43.560 に答える
8

ハッシュ テーブル ルックアップ用の一般的なハッシュ関数。暗号化目的で使用しないことを指定していますが、その意図がないことを指定したため、問題ありません。

試してみるハッシュ関数の調査が含まれています

于 2009-04-13T14:00:34.563 に答える
5

posix に似たシステムを使用していて、プレーンな C に固執している場合は、システムが既に提供しているものを使用するだけです。man 3 hcreate はすべての詳細を提供するか、ここでオンラインバージョンを見つけることができますhttp://linux.die.net/man/3/hcreate

于 2009-04-13T16:05:02.300 に答える
2

長い文字列にはAdler32を、短い文字列にはMurmur2を試してください。

于 2009-04-13T14:12:22.180 に答える
1

xxhashは非常に高速で簡単なオプションです。簡単なコードではXXH32関数を使用します:

unsigned int XXH32 (const void* input, int len, unsigned int seed);

32ビットハッシュです。lenisであるため、バイト数intを超える大きなデータには次を2^31-1使用します。

void*         XXH32_init   (unsigned int seed);
XXH_errorcode XXH32_update (void* state, const void* input, int len);
unsigned int  XXH32_digest (void* state);
于 2013-10-22T08:48:16.360 に答える