如何将目录path转换为唯一的数字标识符(Linux / C ++)?

我正在调查的方式采取一个目录(文件夹),并派生某种forms的唯一的数字标识符。 我调查过“string哈希”的方法,但是, 鸽子洞原则意味着永远不可能为每一个string派生一个真正唯一的数字。

string到唯一哈希是不好的。

我最近一直在调查其他方法来实现我的目标,因此有以下问题要问:

目录时间戳 – 他们有多“独特”? 这里所描述的“stat”报告的时间戳记是什么样的(第二篇文章)? 如果分辨率足够小,是否有可能多个文件夹在Linux系统上共享完全相同的时间戳?

如果任何人有其他方法/技术,他们想分享,我会很高兴听:)

编辑1为了澄清我的用例,以回应迄今为止发布的答案:我正在Android平台上工作,所以文件系统没有链接到任何其他(除了Micro SD卡等可移动媒体除外)。

我将每个path插入数据库,但试图避免查询表时string比较。 地图/ hashmaps的使用不是一个选项在这里。 是的,path本身是唯一的,但理想情况下,我需要一个数字标识符,可以用来查询表,而不是path本身。 每个path的标识符也必须是唯一的。 我已经用std :: collat​​e进行了实验,但是发现哈希中有很多碰撞(一个数据集有20,000条path,大约有100个碰撞)。 更令人惊讶的是,每次我的应用程序运行时,哈希似乎都大不相同。 我想知道它是否以某种方式播种?

非常感谢,P

Solutions Collecting From Web of "如何将目录path转换为唯一的数字标识符(Linux / C ++)?"

在任何基于UNIX的系统上,都可以使用inode编号作为该文件系统中的唯一标识符。 将其与设备号码结合在一起将使其在机器内独一无二。 如果您希望它是全球唯一的,则可以引入系统的主MAC地址。

请记住,但是,

  1. 如果移动或重命名,inode号码将“跟随”目录。 如果目录被删除并被替换,它将会改变。

  2. inode号码在系统之间是不稳定的,超出一个或两个真正特殊的目录。 (例如, /通常是inode 2)

+1黄昏,好一个!

另一种方法是简单地将目录的路径视为一个数字(“BigInt”)。

以这个目录为例: /opt/www/log
这是12个字符。
12 * 8位= 96位
因此,你有一个96位长的数字 ,你可以在十六进制/ base64 /任何东西(如果你需要通过它作为一个HTML链接)表示。

尽管如此,我个人也会选择黄昏的做法。

我认为这很大程度上取决于你想要一个唯一的数字标识符的目的。 时间戳可以改变,inode可以改变,disknumbers可以改变,MAC地址可以改变。 (仍然,黄昏+1)

在某些情况下,您可以简单地创建一个表,其中添加的每个路径都会获得一个新的唯一编号,就像数据库中的数字键列一样。

虽然哈希可能会发生碰撞,但是在每个实际的环境中,这是绝对不可能的(如果你不使用最糟糕的算法……)由于实现中的缺陷,你很可能会得到错误,例如你把“ tmp“不同于”/ tmp /“,因为在对它们进行哈希处理之前,您不会规范化这些路径。 或者,你区分物理文件夹,但忘记检查硬链接和符号链接到相同的文件夹,因此你得到相同的目录多个哈希/ ID的。

再一次,取决于你的用例,碰撞不一定是致命的:如果你发现一个新的路径与现有的路径产生相同的散列(不会发生!),你仍然可以对这种情况作出反应。 (*)

只是为了帮助你的想象力:如果你使用64位散列,你可以用空文件夹填充150万个1TB的硬盘驱动器(没有任何文件夹,但文件夹名称很短),然后就会发生冲突。 如果您认为这样做太冒险(眨眼,眨眼),请使用128位散列,这样可能会减少18 446 744 073 710 000。

哈希是为了使碰撞不太可能发生,即使没有人愿意尝试产生碰撞,即使是好的旧MD5也能很好工作。

(*)编辑:您的鸽子文章已经指出:碰撞只是意味着查找不再是O(1),但稍慢。 由于它很少发生,你可以轻松地生活。 如果使用std :: map(无散列)或std :: hashmap,则不必担心冲突。 看看STL中的map和hashmap有什么区别