ファイル名がキーであるディスクキャッシュを書いています。キーはファイル名の最大長よりも長くなる可能性があるため、ハッシュする必要があります。衝突の可能性が非常に低い (無視できるように) 高速なハッシュ関数は何ですか?
基本的に、セキュリティ要件のない MD5 のより高速な代替手段を探しています。
(プラットフォーム = Android、言語 = Java)
3068 次
2 に答える
6
ハッシュが均一に分散されている場合は、衝突の前に処理すると予想されるおおよその数のファイルから、必要なハッシュのサイズ (ビット単位) を計算できます。基本的に、誕生日のパラドックスのため、ビット数の 2 倍になります。
したがって、たとえば、100 万個のファイルの衝突に満足している場合は、約 40 ビットのログ (2 * log2(1e6)) が必要です。
逆に、ハッシュが N ビットの場合、(多かれ少なかれ) 衝突のない 2^(N/2) ファイルに適しています。
多くの高速ハッシュがあります。たとえば、xxhashは 64 ビット ハッシュなので、約 4,000,000,000 個のファイルに適しています。 グーグルの高速ハッシュは別のものです。
64 ビットを超える (衝突前に最大 40 億ファイルを超える) 場合は、より大きな出力のハッシュを使用するか、2 つの 64 ビット ハッシュを結合することができます (元のファイルからの 1 つのハッシュと何らかの方法で変更された 1 つのハッシュ) (たとえば、スペースを前に付けます))。
于 2013-09-08T22:00:23.467 に答える
0
Google guava ライブラリには、さまざまな高速ハッシュの実装があります。
于 2015-04-12T13:51:35.280 に答える