c++ - ディレクトリパスを一意の数値識別子（Linux / C ++）に変換するにはどうすればよいですか？

Question

ディレクトリ（フォルダ）を取得して、何らかの形式の一意の数値識別子を導出する方法を調査しています。私は「文字列からハッシュへ」の方法を調査しましたが、鳩の巣原理は、すべての単一の文字列に対して真に一意の数を導き出すことは決してできないことを意味します。

一意のハッシュへの文字列は適切ではありません。

私は最近、自分の目標を達成するための他の手段を調査しているので、次の質問があります。

ディレクトリのタイムスタンプ-それらはどのように「ユニーク」ですか？ここで 説明されているように、「stat」によって報告されるタイムスタンプはどの解像度になりますか（2番目の投稿）？解像度が十分に小さい場合、Linuxシステムで複数のフォルダーがまったく同じタイムスタンプを共有することは可能ですか？

誰かが共有したい他の方法/テクニックを持っているなら、私は聞いてうれしいです:)

編集1これまでに投稿された回答に応じてユースケースを明確にするために：私はAndroidプラットフォームで作業しているため、ファイルシステムは他のプラットフォームにリンクされていません（もちろん、Micro SDカードなどの取り外し可能なメディアを除く）。

各パスをデータベースに挿入していますが、テーブルをクエリするときに文字列の比較を避けようとしています。マップ/ハッシュマップの使用はここではオプションではありません。はい、パス自体は一意ですが、理想的には、パス自体ではなく、テーブルのクエリに使用できる数値識別子が必要です。識別子もパスごとに一意である必要があります。std :: collat​​eを試してみましたが、ハッシュ内で多くの衝突があったことがわかりました（20、000パスのデータセットで約100回の衝突が発生します）。さらに驚いたのは、アプリケーションを実行するたびにハッシュが大きく異なるように見えたことです。どういうわけか種まきなのかな？

どうもありがとう、P

Answer 1

UNIXベースのシステムでは、iノード番号をそのファイルシステム内の一意の識別子として使用できます。デバイス番号と組み合わせると、マシン内で一意になります。グローバルに一意にする場合は、システムのプライマリMACアドレスを入力できます。

ただし、次の点に注意してください。

1. iノード番号は、ディレクトリが移動または名前変更された場合、ディレクトリを「追跡」します。ディレクトリを削除して置き換えると変更されます。

2. iノード番号は、1つまたは2つの本当に特別なディレクトリを超えて、システム間で安定しません。（たとえば、/通常はiノード2です。）

Answer 2

+1ダスクワフ、いいね！

もう1つの方法は、dirのパスを数値（ "BigInt"）として単純に扱うことです。

このディレクトリを例にとってみましょう/opt/www/log
。12文字の長さです。
12 *8ビット= 96ビット
したがって、96ビットの長さの数値があり、これはhex / base64 / anyで表すことができます（HTMLリンクとして渡す必要がある場合）。

でも個人的にはduskwuffのアプローチを選びます。

Answer 3

一意の数値識別子が必要な理由に大きく依存すると思います。タイムスタンプ、i ノード、ディスク番号、MAC アドレスが変更される可能性があります。（それでも、ダスクワフの場合は+1）

いくつかのシナリオでは、単純にテーブルを作成できます。このテーブルでは、追加した各パスが、データベースの数値キー列のように、新しい一意の番号を取得します。

ハッシュは衝突する可能性がありますが、すべての実際の環境では、これは絶対に起こりそうにありません (最もお粗末なアルゴリズムを使用しない場合...) 実装の欠陥が原因でエラーが発生する可能性がはるかに高くなります。ハッシュする前にパスを正規化しないため、tmp" は "/tmp/" とは異なります。または、物理フォルダーを区別したいが、同じフォルダーへのハードリンクとシンボリックリンクをチェックするのを忘れているため、同じディレクトリに対して複数のハッシュ/ ID を取得します。

繰り返しますが、ユースケースによっては、衝突は必ずしも致命的ではありません。新しいパスが既存のものと同じハッシュになることがわかった場合 (起こらないでしょう!)、その場合でも対応できます。(*)

想像力を助けるために: 64 ビット ハッシュを使用する場合、150 000 000 の 1 TB のハード ディスク ドライブを空のフォルダー (短いフォルダー名以外には何もありません...) で埋めることができ、衝突が確実に発生します。リスクが高すぎると思われる場合 (まばたき、まばたき)、128 ビット ハッシュを使用すると、18 446 744 073 710 000 倍の可能性が低くなります。

ハッシュは衝突を起こりにくくするように設計されており、古き良き MD5 でさえ、衝突を起こそうとする人がいなければうまく機能します。

(*) 編集: あなたのピジョンホールの記事はすでにそれを指摘しています: 衝突は、ルックアップがもはや O(1) ではなく、わずかに遅いことを意味します。めったに起こらないので、あなたはそれで簡単に暮らすことができます. std::map (ハッシュなし) または std::hashmap を使用する場合、衝突について心配する必要はありません。STLのマップとハッシュマップの違いを見てください