用哈希缩短长网址？

我有一个文件缓存，文件从不同的URL下载。我想通过他们的url的名称保存每个文件。这些名字可能会很长，但我使用的是FAT32文件系统的设备 - 所以在我耗尽实际磁盘空间之前，长名字已经耗尽了资源。用哈希缩短长网址？

我正在寻找一种缩短文件名的方法，得到了对字符串进行散列的建议。但我不确定哈希是否保证对于两个不同的字符串是唯一的。如果两个散列网址具有相同的散列值，那么如果我无意中获取了错误的图像，那将会很糟糕。

感谢

来源

2011-09-01 user291701

我想你会发现麻烦散列文件名：哈希（恕我直言）可产生重复的条目... – Marco

当你说“长名称在我耗尽实际磁盘空间之前就吃尽了资源“，我感到有点怀疑。不知道为什么。但不是存储相当便宜吗？ – Coffee

@Marco，同意，哈希可以产生重复（“碰撞”）。如果碰撞发生，您应该制作一些碰撞处理程序来尝试新的哈希...... – poplitea

有没有（缩短）散列可以保证不同的散列每个输入。这根本不可能。

我通常这样做的方式是在缓存文件的开始处（例如第一行）保存原始名称。因此，要找到你做这样的缓存文件：

哈希的URL
找到对应于散列
检查第一行的文件。如果是一样的完整URL：
文件的其余部分是由两个线和前锋

您也可以考虑保存在数据库中URL->文件映射。

来源

2011-09-01 18:52:24

目前推荐使用SHA-1算法。没有已知的方法有意挑起这种算法的碰撞，所以你应该是安全的。用两个具有共同结构的数据（例如前缀http://）激发碰撞更加困难。如果在获得HTTP 200响应后保存这些内容，那么该URL显然会获取某些内容，因此使用相同的SHA-1哈希获得两个截然不同的有效URL实际上不应该成为问题。

如果有任何再保证Git使用它来标识源代码库中的所有对象，提交和文件夹。我还没有听说有人在对象商店发生碰撞。

来源

2011-09-01 18:52:28

看看我的评论。
一个可能的解决方案（有很多）是创建一个本地文件（SQLite？XML？TXT？），其中存储一对（file_id - file_name），以便您可以使用它们的唯一ID将文件保存为文件名。
只是一个想法，没有最好...

来源

2011-09-01 18:52:46 Marco

hash并不是保证是唯一的，但碰撞的几率是微乎其微。

如果你的散列值是128位，那么任何一对条目的冲突的概率是2^128中的1。通过生日悖论，如果你的桌子上有10^18个条目，那么碰撞的可能性只有1％，所以你不必担心它。如果你是偏执狂，那么通过使用SHA256或SHA512增加哈希的大小。

很明显，您需要确保散列表示实际占用的空间比原始文件名更少。 Base-64编码的字符串表示每个字符6位，因此您可以通过数学计算来确定它是否值得首先执行哈希。

如果您的文件系统barfs由于名称太长，您可以为实际存储创建前缀子目录。例如，如果文件映射哈希ABCDE，则可以将其存储为/path/to/A/B/CDE或/path/to/ABC/DE，具体取决于对您的文件系统最有效的方式。

Git是这种技术在实践中的一个很好的例子。

来源

2011-09-01 18:53:09

即使是一个128位散列，也可能会使原来的文件名缩短。 –

Base64编码只有22个字符。如果这对FAT32来说仍然太大，那么使用不同的文件系统可能是更好的解决方案。严重的是，FAT32仍在使用中？ –

FAT32可以有更长的文件名。这种担心似乎与一个非常大的*数量*的长文件名。如果文件名是基于URL的，那么使用22个字符散列值可能仍会导致平均长度的减少。但有两四次，可能不会。 –

你可以做什么是由索引保存文件，并使用一个索引文件，以找到实际文件的位置

您有：

index.txt 
file1 
file2 
... 
etc.

和index.txt你使用一些数据结构来有效地查找文件名（或用一个数据库替换）

来源

2011-09-01 18:53:55

但我不确定散列是否保证对于两个不同的字符串是唯一的。

他们非常不（也不能，因为pigeonhole principle）。但是，如果散列足够长（至少64位）并且分布良好（理想情况下是密码散列），那么碰撞的可能性变得非常小以至于不值得担心。

作为粗略指导，一旦文件数量接近可能的不同散列数（birthday paradox）的平方根，就会发生冲突。因此，对于64位散列（10个字符文件名），如果您有40亿个文件，则一次冲突的可能性大约为50％。

您必须决定这是否是可接受的风险。你可以通过使哈希长度更长来减少碰撞的机会，但是当然在某些时候，这意味着与你想要的相反。

来源

2011-09-01 18:56:39

您可以为每个URL生成UUID并将其用作文件名。

UUID是唯一的（或“实际上唯一的”），长度为36个字符，所以我猜文件名不会是一个问题。

从版本5开始，JDK附带一个类来生成UUID（java.util.UUID）。如果有方法将它们与URL相关联，则可以使用随机生成的UUID，也可以使用基于名称的UUID。基于名称的UUID的总是相同的，所以下面的始终是真实的：

String url = ... 
UUID urlUuid = UUID.nameUUIDFromBytes(url.getBytes); 
assertTrue(urlUuid.equals(UUID.nameUUIDFromBytes(url.getBytes)));

来源

2011-09-01 20:21:41

用哈希缩短长网址？

回答

相关问题