衝突困難性と一様性に優れた64bit値を出力するハッシュ関数を一番知りたいが、衝突困難性と一様性が優れるならば64bit値に関わらず知りたい。

Question

###前提・実現したいこと
64bit値の一様な値を得てデータベースのIDやハッシュテーブル、二分木のキー値への利用や簡易メッセージダイジェストなどに利用したい。

###知りたいこと
64bit値を出力する衝突困難性と一様性に優れたハッシュ関数のアルゴリズム名を知りたい。アルゴリズム解説サイトへのURLがあれば嬉しい。
無論のこと、高速なアルゴリズムであればあるほど都合が良い。蛇足だが32bit値を出力するMurMurHashは十分高速であった。

解答例:
32bit値ならMurMurHash https://en.wikipedia.org/wiki/MurmurHash
128bit値ならMD5? 等

詳しい方、ご存知の方、ハッシュ関数のアルゴリズム名だけでも聞き覚えのある方、ご返信いただければ嬉しく思います。宜しくお願い致します。

###追記

64bit値を出力するMurMurHash2というアルゴリズムが見つかりました。その他にも候補に上がるアルゴリズムをご存じの方がいましたら宜しくお願い致します。

Answer 1

どのような用途で使うのかは知りませんが、64ビットのハッシュ値に衝突困難性を期待すること自体、あまり適当ではありません。

誕生日攻撃と言われるように、大量に生成したハッシュ値同士が衝突する確率は、ハッシュ値が取りうるパターンの平方根に概ね比例します。64ビットのハッシュ値であれば平方根をとった32ビット分で42億程度ですので、使い方によっては衝突してしまうこともなくはない、という計算になります。

Comments

[Touhoku]

なるほど。誕生日攻撃という考慮事項があったのですね。とても勉強になりました。ご返信有り難うございました。
用途に関して具体性を求められたと感じたので『前提・実現したいこと』を更新しました。レジスタ長の一意はIDの生成は何かとほしい時がありまして――。

Answer 2

高速なハッシュ関数としては FNV-1/FNV-1a も選択肢に入ると思います。

別のQ&Aサイトですが "Which hashing algorithm is best for uniqueness and speed?" も参考にください。

Comments

[Touhoku]

ものすごい詳細なレポートが掲載されていて目が飛び出ました。この度は貴重な情報ありがとうございました。