如何將目錄路徑轉換爲唯一的數字標識符（Linux/C++）？

Question

我正在研究如何獲取目錄（文件夾）並派生某種形式的唯一數字標識符。我調查了「字符串哈希」方法，然而，Pigeon Hole Principle意味着永遠不可能爲每個字符串派生一個真正唯一的數字。

字符串到唯一哈希是不好的。

我最近一直在研究實現我的目標等手段，從而有以下問題要問：

目錄時間戳 - 如何「獨一無二」是什麼人？ here（第二篇文章）中以'stat'報告的時間戳記是什麼分辨率？如果分辨率足夠小，是否有可能多個文件夾在Linux系統上共享完全相同的時間戳？

如果任何人有其他方法/技術，他們想與大家分享，我很樂意聽:)

編輯1爲了澄清我的使用情況，迴應迄今發佈的答案：我我在Android平臺上工作，所以文件系統沒有鏈接到任何其他（除了Micro SD卡等可移動媒體除外）。

我將每個路徑插入數據庫，但在查詢表時試圖避免字符串比較。在這裏，地圖/ hashmaps的使用不是一種選擇。是的，路徑本身是唯一的，但理想情況下，我需要一個數字標識符，可用於查詢表格而不是路徑本身。每個路徑的標識符也必須是唯一的。我用std :: collat​​e進行了實驗，但發現哈希中存在許多碰撞（一個包含20,000條路徑的數據集，約有100次碰撞）。更令人驚訝的是，每次運行我的應用程序時，哈希似乎都大不相同。我想知道它是否以某種方式播種？

非常感謝， P

Answer 1

在任何基於UNIX的系統，您可以使用索引節點號爲文件系統中的唯一標識符。將它與設備號碼結合起來可以使其在機器內獨一無二。如果你希望它是全球唯一的，你可以引入系統的主MAC地址。

請記住，但是，：

1. inode編號將「跟隨」的目錄，如果它被移動或重命名。如果目錄被刪除並被替換，它將會改變。

2. inode號碼在整個系統中不會穩定，超出一兩個真正特殊的目錄。 （例如，/通常是inode 2.）

Answer 2

+1 duskwuff，好的！

另一種方法是簡單地將目錄的路徑視爲一個數字（「BigInt」）。

以此目錄爲例：/opt/www/log
這是12個字符長。
12 * 8bits = 96bits
因此，您有一個96位長的數字，您可以用十六進制/ base64 /任何東西（如果您需要將它作爲HTML鏈接傳遞）表示。

雖然我會親自去黃昏的方法。

Answer 3

我認爲這很大程度上取決於您想要一個唯一的數字標識符的目的。時間戳可以改變，inode可以改變，disknumbers可以改變，MAC地址可以改變。 （仍然爲黃昏+1）

在某些情況下，您可以簡單地創建一個表格，其中每個添加的路徑都會獲得一個新的唯一編號，就像數據庫中的數字鍵列一樣。

雖然散列可以碰撞，在每一個實際環境中，這是絕對不可能的（如果你不使用最蹩腳算法各地......）這是更可能的是你的錯誤是由於您的實現的缺陷，例如，您將「/ tmp」視爲與「/ tmp /」不同，因爲在對它們進行哈希處理之前，您不會規範化路徑。或者，您要想要區分物理文件夾，但忘記檢查硬鏈接和符號鏈接到同一個文件夾，因此您可以爲同一目錄獲取多個哈希/ ID。

同樣，根據您的用例，碰撞不一定是致命的：如果您發現新路徑與現有路徑產生相同的散列（不會發生！），您仍然可以對該情況做出反應。 （*）

只是爲了幫助您發揮想象力：如果您使用64位散列，您可以用空文件夾填充150萬個1TB硬盤驅動器（沒有任何文件夾，但文件夾名稱短）...然後您肯定會有碰撞。如果您認爲這樣做太冒險（眨眼，眨眼），請使用128位散列，這使得它的可能性減少18 446 744 073 710 000。

哈希設計用於使碰撞不太可能，甚至好的老的MD5也會很好地完成工作，如果沒有人願意試圖產生碰撞。

（*）編輯： 你束之高閣的文章已經指出了這一點：碰撞只是意味着查找不再是O（1），但稍微慢一些。因爲它很少發生，你可以輕鬆地生活。如果您使用std :: map（無散列）或std :: hashmap，則不必擔心衝突。請參閱what the difference between map and hashmap in STL