百万の短い文字列の一意の整数/浮動小数点ハッシュを作成する

Question

ほとんどのアプリケーション、特にデータベースは、小さな整数でソートしたりフィルタリングしたりすることができます。

したがって、文字列ではなく整数で比較できるように、32ビットまたは64ビットの短い文字列（約5〜40文字）を返すために使用できるハッシュ関数があるかどうかは疑問です。

私は最初にcrc32を考えましたが、数値が小さすぎてwould result in possible collisions in less than 50,000 hashes（私は100万を超える必要があります）のようです。

私は、Python、PHP、V8 Javascript、PostgreSQL、およびMySQLでの作業にほとんど関心があります。

Answer 1

50kエントリで衝突が発生する可能性が高いという問題は、すべての32ビットハッシュに固有の問題です。 Birthday problemのビットを読んだ場合、約sqrt(HashSpace)個の要素があると衝突が発生する可能性が高くなります。 32ビットハッシュの場合はsqrt(2^32) = 64kです。

---

64ビットハッシュの衝突は非常に稀です。しかし、私はまだ自分のプログラムの正しさをあまりにも快適に賭けている気がしません。

ウィキペディアからの近似を使用する：

我々1000万個の要素のための3×10 -8 100万個の要素、および3 * 10 -6の確率を得ます。

これにCRC64を使用できます。または、md5やsha1などの暗号ハッシュを目的の長さに切り詰めるだけです。

---

悪意のある人が故意に衝突を作成することによって、あなたのプログラムを壊す、文字列を選択することができれば、あなたは、HMACとしてキー付きハッシュ、少なくとも切り替える必要があります。

---

あなたがやっていることによって、あなたは単にあなたは単にあなたが遭遇する各要素のカウンタをインクリメント文字列と整数間のインメモリマッピングを作成することができます。これにより、衝突のリスクがない完璧なマッピングが得られますが、一部のシナリオでのみ適用されます。