java - 64 ビット符号なしハッシュ関数

Question

64 ビットの符号なし整数 (0 から 2^63 - 1 の範囲) があり、それらを 32 ビットの符号なし整数 (0 から 2^31 - 1 の範囲) にハッシュしたいと考えています。

データは一様分布に従います。この分布の衝突数が少ないハッシュ関数を提案できる人はいますか (衝突が発生する可能性がある可能性があります)。

Answer 1

の分布が本当に均一である場合は、下位nビット（ハッシュ値の幅）を取得します。これは、最悪の場合、バケットに2つ^のN-n要素を含めることができることを意味します。（ここでNは、元の番号の幅を示します）

注： @JanDvorakが（私の答えの前に）すでにこれを提案しているのを見たばかりです。モジュロ2 ⁿを使用することは、下位nビットを取得することと同じです...

これが実際に約64ビットの符号なし整数が32ビットの符号なし整数にハッシュされている場合、正しい範囲は[0; 264-1]と[0; ²³² -1]になり、 1^回の衝突で最大232^回の衝突が発生します。ハッシュ。ただし、Javaには、符号なし整数はありません...

^{これが符号付き64ビット整数値と32}ビット整数値の正の半分をそれぞれ使用する場合、範囲値は正しく、最悪の場合でも232回の衝突が発生します。

Answer 2

このような単純な分布の場合、適切なハッシュ関数はすべて適合します。(int)(longvalue+(longvalue>>32))確認するには、衝突を数えてみてください。31 ビットのみが必要な場合は、make をres&0x7fffffff実行します (値が unsigned であることを強調するのはなぜですか? 31 ビットの int と 63 ビットの long は、signed と unsigned の両方の範囲に収まります)。

Answer 3

適切な長さとビットの均一な分布が既にあるのに、なぜハッシュするのですか? セキュリティ要件を念頭に置いていると思いますか？共有してください。

探しているのが標準のハッシュである場合は、SHA-1 を検討してください。

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
//Some more imports

MessageDigest md = MessageDigest.getInstance("SHA-1");
md.update(data);
byte[] hash = md.digest());