Cの最小ハッシュ関数？

Question

boost：hashを使うことはできません。なぜなら私はCに固執する必要があり、C++を使うことができないからです。

しかし、それらの検索が最も高速になるように、大きな（10K〜100k）のトークン文字列（5〜40バイト長）をハッシュする必要があります。

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

したがって、私の質問：

1. 最も実用的な例には衝突防止を保証する最も簡単なハッシュアルゴリズムであるかもしれない何を。

2. ハッシュ値に使用するビット数はいくつですか？私は32ビットシステム用に開発中です。 Perl/Pythonのハッシュアルゴリズムも32ビットハッシュを使用していますか？あるいは、私は64にジャンプしなければならないのですか？

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

Answer 1

あなたはhttp://www.azillionmonkeys.com/qed/hash.htmlで、良い（と速い）ハッシュ関数、および興味深い読み取りを見つけることができます

完全なハッシュを使用している場合は、唯一のチェックは不要です。これは、gperfのような古き良きルックアップテーブルです。

Answer 2

hash table lookupの一般的なハッシュ関数。それはを指定しますの暗号化目的には使用しませんが、その意図がないと指定してからOKにしてください。それは含まれて

は

Answer 3

1. Hereを試してみハッシュ関数のA調査で最も注目すべき既知のハッシュ関数の素敵な概観です。

2. 32ビットはうまくいくはずです。あなたが面白いハッシュテーブルを記述する場合を除き、あなたは常に、衝突をチェックする必要があります:)

Answer 4

短い文字列の場合は、長い文字列 またはMurmur2を試してください。Adler32

Answer 5

あなたがposixのようなシステムでプレーンCに固執しているなら、私は単純にシステムが提供しているものを使います。男3 hcreateはあなたにすべての詳細を提供するか、ここでオンライン版を見つけることができますhttp://linux.die.net/man/3/hcreate

Answer 6

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

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

32ビットハッシュです。len以上2^31-1バイトは、これらを使用し、より大きなデータに対して、intあるので：

void*   XXH32_init (unsigned int seed); 
XXH_errorcode XXH32_update (void* state, const void* input, int len); 
unsigned int XXH32_digest (void* state);