代码之家 › 专栏 › 技术社区 › Dominik Weber

在UTF16中查找文件路径的好的64位哈希

hash-collision utf-16 collision path hash

Dominik Weber · 技术社区 · 14 年前

UTF-16编码路径 . 路径分隔符是U+005C'\'。

我想把这条路拼凑成一个 64位无符号 不需要 成为 “加密声音” 散列应该是 不区分大小写 显然,散列也应该分散得很好。

我有一些想法:

A) 将windows文件标识符用作“哈希”。在我的例子中,如果文件被移动,我确实希望哈希值改变,所以这不是一个选项。

B) 只需对整个字符串使用一个常规的sting散列:hash+=prime*hash+codepoint。

总结一下需求:

1) 64位哈希

3) 高效

5) 不区分大小写

4 回复 | 直到 14 年前

Arc 14 年前

密码学上安全的散列在速度上可能不是很有效,但实际上任何编程语言都有实现。
在你的应用程序中使用它们是否可行取决于你对速度的依赖程度——一个基准测试会给你一个合适的答案。

您可以使用这样一个散列的子字符串,例如路径上的MD5,它以前被转换成小写,这样散列就可以有效地不区分大小写(要求您使用一个小写的方法,它知道如何转换文件系统中可能出现的所有UTF-16非标准字符)。

密码学安全的散列有相当均匀的分布的好处,无论你采取的子字符串部分,因为他们被设计成不可预测的,即散列的每个部分理想地依赖于整个散列数据作为它的任何其他部分。

Thomas Pornin 14 年前

即使你没有需要 MD4

对于您需要的特定属性,您需要:

“规范化”字符,以便将大写字母转换为小写(不区分大小写)。注意,一般来说,Unicode世界中的大小写不敏感不是一件容易的事情。根据您的解释,我推断您只是在Windows用于文件访问的那种不区分大小写的情况下(I 它仅为ASCII码,因此转换为大写字母->小写字母很简单)。
截断MD4的输出。MD4产生128位;只需使用前64位。这将是分散,因为你可以希望。

sphlib .

Jon Hanna 14 年前

ui64 res = 10000019;
for(i = 0; i < len; i += 2)
{
  ui64 merge = ucase(path[i]) * 65536 + ucase(path[i + 1]);
  res = res * 8191 + merge; // unchecked arithmetic
}
return res;

我是这么想的 path[i + 1] 是安全的,因为如果 len 如果是奇数,那么在最后一种情况下,它将安全地读取U+0000。

我不会利用UTF-16中的空白、小写和标题大小写字符以及路径无效字符造成的空白,因为这些字符的分布方式不能利用这个事实—可以快速使用的东西。减少32(U+0032以下的所有字符在路径名中都是无效的)代价不会太高,但也不会对哈希进行太多改进。

reinier 8 年前

您只需在C#中创建一个共享库,并使用FileInfo类获取目录或文件的完整路径。然后在路径中使用.GetHashCode(),如下所示:

Hash = fullPath.GetHashCode();

int getHashCode(string uri) 
{
   if (uri == null) throw new ArgumentNullException(nameof(uri));

   FileInfo fileInfo = new FileInfo(uri);
   return fileInfo.FullName.GetHashCode();
}