文字列から整数へのハッシュ関数の精度

Question

char配列をintまたはlongにハッシュしたい。結果の値は、指定された精度値に従わなければなりません。私が使用してきた 機能は以下の通りである：

int GetHash(const char* zKey, int iPrecision /*= 6*/) 
{ 
     /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp 

     unsigned long h = 0; 
     long M = pow(10, iPrecision); 

     while(*zKey) 
     { 
       h = (h << 4) + *zKey++; 
       unsigned long g = h & 0xF0000000L; 
       if (g) h ^= g >> 24; 
       h &= ~g; 
     }    

     return (int) (h % M); 
} 

ハッシュされる文字列は「SAEUI1210.00000010_1」に似ています。

ただし、重複する値が生成されることがあります。 異なる文字列値に対して同じハッシュを複製しない良い選択肢はありますか？

Answer 1

ハッシュの定義は、ハッシュ値の範囲がハッシュされたデータの領域よりも小さいため、一部の値に対して重複した値を生成することです。

理論的には、32ビットのハッシュでは、衝突を引き起こすことなく、すべての〜6文字の文字列（A〜Z、a〜z、0〜9のみ）をハッシュするのに十分な範囲があります。実際には、ハッシュは入力の完全な順列ではありません。 32ビットのハッシュが与えられた場合、birthday paradoxのために、〜16ビットのランダム入力をハッシュした後にハッシュ衝突を予想することができます。

データ値の静的なセットが与えられた場合、それらのために特別に設計されたハッシュ関数を構築できます（もちろん、出力のサイズは少なくともlog(|data set|)になります）。事前にすべての可能なデータ値を知っている。これはperfect hashingと呼ばれているし。

言われていること、hereあなたが始めるべきいくつかの選択肢（彼らは衝突を最小限に抑えるように設計されている）

Answer 2

すべてのハッシュには衝突があります。期間。これはBirthday Problemと呼ばれています。

暗号化にはMD5のような機能があります（比較的速く、安全でないことは気にしません）が、衝突する可能性があります。

Answer 3

ハッシュされている同じを生成あなたができることは、十分なdistribを持つハッシュ関数を作成することですこれらの衝突を最小限にするために、ビット深度（またはその両方）を設定します。精度（0-5？）のこの追加の制約があるので、衝突をもっと頻繁に打つことになります。

Answer 4

MD5またはSHA。多くのオープンな実装があり、その結果は重複した結果を生み出す可能性は非常に低いです。