8

我有一个 Unicode/ UTF-16 编码路径。路径分隔符是 U+005C '\'。路径是以 null 结尾的根相对 Windows 文件系统路径，例如“\windows\system32\drivers\myDriver32.sys”

我想将此路径散列为64 位无符号整数。它不需要是“加密健全的”。哈希应该不区分大小写，但能够处理非 ascii 字母。显然，散列也应该很好地分散。

我有一些想法：

A) 使用 Windows 文件标识符作为“哈希”。在我的情况下，如果文件被移动，我确实希望哈希值发生变化，所以这不是一个选项。

B) 只需对整个字符串使用常规的 sting 散列：散列 += 素数 * 散列 + 代码点。

我确实觉得可以利用路径由“段”（文件夹名和最终文件名）组成的事实。

总结一下需求：

1) 64 位哈希
2) 文件系统路径的良好分布/很少冲突。
3) 高效
4) 不需要安全
5) 不区分大小写

4

4 回答 4

3

我只会使用简单的东西。我不知道你用的是什么语言，所以下面是伪代码：

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 以下的所有字符在路径名中都是无效的）不会太贵，但也不会过多地改善散列。

于 2010-09-22T16:19:36.460 回答
2

加密安全哈希在速度方面可能不是很有效，但几乎所有编程语言都有可用的实现。
使用它们对您的应用程序是否可行取决于您对速度的依赖程度——基准测试将为您提供适当的答案。

您可以使用此类哈希的子字符串，例如路径上的 MD5，之前已转换为小写，以便哈希实际上不区分大小写（要求您使用知道如何转换所有 UTF 的小写方法-16 个可能出现在文件系统中的非标准字符）。

无论您采用哪个子字符串部分，加密安全散列具有相当均匀分布的好处，因为它们被设计为不可预测的，即散列的每个部分理想情况下取决于整个散列数据的任何其他部分。

于 2010-09-15T20:34:47.880 回答
2

即使您不需要加密哈希，您仍然可以使用一个，并且由于您的问题与安全性无关，因此“损坏的”加密哈希就可以了。我建议MD4，它非常快。在我的 PC（2.4 GHz Core2 系统，使用单核）上，MD4 散列超过 700 MB/s，即使对于小输入（小于 50 字节），它也可以每秒处理大约 800 万条消息。您可能会发现更快的非加密哈希，但它已经需要一个相当具体的情况才能产生可​​衡量的差异。

对于您所追求的特定属性，您需要：

  1. “规范化”字符，以便将大写字母转换为小写字母（不区分大小写）。请注意，一般来说，Unicode 世界中不区分大小写并不是一件容易的事。根据您的解释，我认为您只是在 Windows 用于文件访问的相同类型的不区分大小写之后（我认为它只是 ASCII，因此转换大写-> 小写很简单）。

  2. 截断 MD4 的输出。MD4 产生 128 位；只需使用前 64 位。这将像您希望的那样分散。

很多地方都有 MD4 实现，包括我上面链接的 RFC 1320。您还可以在sphlib中找到 C 和 Java 中的开源 MD4 实现。

于 2010-09-16T13:56:06.723 回答
1

您可以在 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();
}

虽然这只是一个 32 位代码，但您可以根据文件的其他一些特征复制它或附加另一个 HashCode。

于 2016-11-01T14:24:39.917 回答