4

我正在研究获取目录（文件夹）并派生某种形式的唯一数字标识符的方法。我研究了“字符串到哈希”方法，但是，鸽子洞原理意味着永远无法为每个字符串导出一个真正唯一的数字。

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

我最近一直在研究实现目标的其他方法，因此有以下问题要问：

目录时间戳 - 它们有多“独特”？此处 描述的“stat”报告的时间戳的分辨率是多少（第二篇文章）？如果分辨率足够小，是否可以在 Linux 系统上让多个文件夹共享完全相同的时间戳？

如果有人想分享其他方法/技术，我很乐意倾听:)

编辑 1澄清我的用例以回应迄今为止发布的答案：我在 Android 平台上工作，所以文件系统没有链接到任何其他（当然除了可移动媒体，如 Micro SD 卡）。

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

非常感谢，P

4

3 回答 3

6

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

但是，请记住：

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

  2. 跨系统的 inode 数量将不稳定，超过一两个真正特殊的目录。（例如，/通常是 inode 2。）

于 2012-09-02T17:42:29.150 回答
1

+1 黄昏，好一个！

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

以这个目录为例：/opt/www/log
它有 12 个字符长。
12 * 8bits = 96bits
因此，您有一个96 位长的数字，您可以用 hex/base64/anything 表示（以防您需要将其作为 HTML 链接传递）。

不过，我个人会选择黄昏的方法。

于 2012-09-02T17:50:20.277 回答
0

我认为这在很大程度上取决于您为什么想要一个唯一的数字标识符的目的。时间戳可以改变，inode 可以改变，disknumbers 可以改变，MAC 地址可以改变。（不过，+1 为黄昏）

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

尽管散列可能会发生冲突，但在每个实际环境中这绝对不可能（如果您不使用最糟糕的算法......）由于实现中的缺陷，您更有可能遇到错误，例如您对待“/ tmp" 与 "/tmp/" 不同，因为在对路径进行散列处理之前不会对其进行规范化。或者，您想区分物理文件夹，但忘记检查同一个文件夹的硬链接和符号链接，因此您会获得同一个目录的多个哈希/ID。

同样，根据您的用例，冲突不一定是致命的：如果您发现新路径导致与现有路径相同的哈希（不会发生！）您仍然可以对这种情况做出反应。(*)

只是为了帮助您的想象力：如果您使用 64 位散列，您可以用空文件夹填充 150 000 000 个 1TB 硬盘驱动器（上面什么都没有，只有简短的文件夹名称......），然后肯定会发生冲突。如果您认为这太冒险（眨眼，眨眼），请使用 128 位散列，这使其可能性降低 18 446 744 073 710 000 倍。

哈希旨在使冲突不太可能发生，如果没有人愿意尝试产生冲突，即使是好的旧 MD5 也会很好地完成它的工作。

(*) 编辑： 您的鸽巢文章已经指出：碰撞只是意味着查找不再是 O(1)，而是稍微慢一些。因为它很少发生，你可以很容易地忍受它。如果您使用 std::map（无哈希）或 std::hashmap，则不必担心冲突。看看STL中map和hashmap有什么区别

于 2012-09-02T18:31:50.373 回答