8

Unicode / UTF-16 でエンコードされたパスがあります。パス区切り文字は U+005C '\' です。パスは、null で終わるルート相対 Windows ファイル システム パスです (例: "\windows\system32\drivers\myDriver32.sys")。

このパスを64 ビットの符号なし整数にハッシュしたいと考えています。「暗号的に健全」である必要はありません。ハッシュは大文字と小文字を区別しない必要がありますが、ASCII 以外の文字を処理できます。明らかに、ハッシュも適切に分散する必要があります。

私が持っていたいくつかのアイデアがあります：

A) Windows ファイル識別子を「ハッシュ」として使用する。私の場合、ファイルが移動された場合にハッシュを変更したいので、これはオプションではありません。

B) 通常の文字列ハッシュを使用するだけです: ハッシュ += プライム * ハッシュ + 文字列全体のコードポイント。

パスが「セグメント」(フォルダー名と最終的なファイル名) で構成されているという事実を活用できると感じています。

ニーズをまとめると、次のようになります。

1) 64 ビット ハッシュ
2) 適切な分散/ファイル システム パスの競合が少ない。
3) 効率的
4) 安全である必要がない
5) 大文字と小文字 を区別しない

4

4 に答える 4

3

私は単純なものを使うだけです。使用している言語がわからないため、以下は疑似コードです。

ui64 res = 10000019;
for(i = 0; i < len; i += 2)
{
  ui64 merge = ucase(path[i]) * 65536 + ucase(path[i + 1]);
  res = res * 8191 + merge; // unchecked arithmetic
}
return res;

ifが奇数の場合、最後のケースでは U+0000 を安全に読み取ることにpath[i + 1]基づいて、これは安全であると想定しています。len

UTF-16 のギャップ、小文字とタイトルの大文字、パスに無効な文字によるギャップがあるという事実を利用しません。これらは使用する方法で配布されていないためです。この事実の何かを迅速に使用することができます。32 (パス名では U+0032 より下のすべての文字は無効) でドロップしてもコストはかかりませんが、ハッシュがあまり改善されません。

于 2010-09-22T16:19:36.460 に答える
2

暗号化ハッシュが必要ない場合でも、それを使用できます。問題はセキュリティに関するものではないため、「壊れた」暗号化ハッシュは問題ありません。非常に高速な MD4をお勧めします。私の PC (シングル コアを使用する 2.4 GHz Core2 システム) では、MD4 は 700 MB/秒以上のハッシュを実行し、小さな入力 (50 バイト未満) の場合でも、毎秒約 800 万のメッセージを処理できます。より高速な非暗号化ハッシュが見つかるかもしれませんが、測定可能な違いを生むには、かなり特殊な状況が必要です。

求めている特定のプロパティについては、次のものが必要です。

  1. 大文字が小文字に変換されるように文字を「正規化」します (大文字と小文字を区別しないため)。一般的に言えば、Unicode の世界で大文字と小文字を区別しないことは簡単な作業ではないことに注意してください。あなたの説明から、Windowsがファイルアクセスに使用するのと同じ種類の大文字と小文字を区別しないようになっているだけだと思います（ ASCIIのみだと思うので、大文字から小文字への変換は簡単です）。

  2. MD4 の出力を切り捨てます。MD4 は 128 ビットを生成します。最初の 64 ビットのみを使用します。これは、必要に応じて分散されます。

上でリンクした RFC 1320 を含め、多くの場所で利用可能な MD4 実装があります。また、C でのオープンソース MD4 実装とsphlibでの Java を見つけることもできます。

于 2010-09-16T13:56:06.723 に答える
2

暗号的に安全なハッシュは、速度の点ではあまり効率的ではないかもしれませんが、事実上すべてのプログラミング言語で利用できる実装があります。
アプリケーションでそれらを使用できるかどうかは、速度にどれだけ依存しているかによって異なります。ベンチマークは、それに対する適切な答えを提供します。

そのようなハッシュの部分文字列を使用することもできます。たとえば、パス上の MD5 は以前に小文字に変換されていたため、ハッシュは事実上大文字と小文字を区別しません (すべての UTF を変換する方法を知っている小文字化の方法を使用する必要があります)。 -16 個の非標準文字 (ファイル システムで発生する可能性があります)。

暗号学的に安全なハッシュは、部分文字列のどの部分を使用しても非常に均等に分散されるという利点があります。これは、ハッシュが予測不能になるように設計されているためです。つまり、ハッシュの各部分は、他の部分と同様に、ハッシュされたデータ全体に理想的に依存します。

于 2010-09-15T20:34:47.880 に答える
1

C# で共有ライブラリを作成し、FileInfo クラスを使用して、ディレクトリまたはファイルの完全なパスを取得できます。次に、次のようにパスで .GetHashCode() を使用します。

Hash = fullPath.GetHashCode();

また

int getHashCode(string uri) 
{
   if (uri == null) throw new ArgumentNullException(nameof(uri));

   FileInfo fileInfo = new FileInfo(uri);
   return fileInfo.FullName.GetHashCode();
}

これは単なる 32 ビット コードですが、ファイルの他の特性に基づいて複製するか、別の HashCode を追加します。

于 2016-11-01T14:24:39.917 に答える