寻找一个适用于UTF16文件路径的好的64位哈希函数

Question

我有一个Unicode/UTF-16编码的路径。路径分隔符为U+005C“\”。 这些路径是以根目录为基础的Windows文件系统路径，例如"\windows\system32\drivers\myDriver32.sys"。

我想将此路径哈希成64位无符号整数。 它不需要是“加密安全”的。 哈希应该是大小写不敏感的，但能够处理非ASCII字母。 显然，哈希也应该散布得很好。

我有一些想法：

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

B）只需使用常规字符串哈希：对于整个字符串，哈希=素数*哈希+代码点。

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

总结需求：

1）64位哈希
2）适用于文件系统路径的良好分布/少碰撞。
3）高效
4）不需要安全
5）大小写不敏感

- Dominik Weber

---

下面的答案是足够的 - 但我希望有一个哈希，利用输入是utf-16文件路径的事实。 - Dominik Weber

对于加密哈希函数而言，使用UTF-16或其他编码方式几乎没有区别，因为它们被设计成不可预测，并使用输入中提供的所有信息，在结果哈希的每个比特位上实现完美分布和最小碰撞（至少在理论上如此——哈希越安全，就越能满足这一点），这就是为什么您可以使用哈希的任何部分。 - Arc

但是在UTF-16代码空间中存在空缺，私有使用区域和大写或小写字符都没有被使用。或者担心输入数据的结构是毫无意义的吗？ - Dominik Weber

理论上，这对于一个好的加密哈希函数来说不应该有影响。当然，哈希数据结构可能存在隐藏的依赖关系，但是对于您的应用程序来说，这些依赖关系几乎不可观察，否则我猜想在检查哈希函数时会有人发现并且这可能会立即使哈希无法用于加密。安全哈希被认为是您可以获得的最好的完美分布。 - Arc

以下页面提供了多种通用哈希函数的实现，这些函数高效且碰撞较少：http://www.partow.net/programming/hashfunctions/index.html - Matthieu N.

Answer 1

我建议您使用简单的方法。我不知道您正在使用的编程语言，因此以下是伪代码：

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 中存在的空白造成的间隙、小写和标题字符以及非路径有效字符的事实，因为这些内容分布不均，不能很快地利用这个事实。将所有低于 U+0032 的字符减少32不会太消耗性能，但也不会太大地改善哈希效率。

- Jon Hanna

---

这不错——它避免了必须将整个字符串大写，而且空值终止技巧也很巧妙。 - Dominik Weber

嗯，它本质上是在UCase部分将整个字符串变成大写。这段伪代码的意思是进行大写格式化。无论是作为字符串还是逐个字符进行操作都没有关系（包括效率），假设我正确地记得文件大小写折叠是按字符和不考虑文化的。我的记忆可能有误。无论哪种情况，您都希望使用与Windows文件系统相同的方法。 - Jon Hanna

Answer 2

即使您不需要加密哈希，仍然可以使用它，而且由于您的问题与安全无关，所以“破碎”的加密哈希也可以。我建议使用MD4，这个算法非常快。在我的电脑上（一台2.4 GHz Core2系统，使用单个核心），MD4每秒可以处理超过700 MB的哈希值，即使对于小输入（少于50字节），它也可以每秒处理约800万条消息。您可能会发现更快的非加密哈希，但这已经需要相当特殊的情况才能产生可衡量的差异。

针对您的具体需求，您需要：

1. “规范化”字符，使大写字母转换为小写字母（用于大小写不敏感）。请注意，一般来说，在Unicode世界中实现大小写不敏感并不是一件容易的事情。从您的解释中，我理解您只追求与Windows文件访问使用的相同类型的大小写不敏感性（我认为它仅限于ASCII，因此将大写字符转换为小写字符很简单）。

2. 截断MD4的输出。MD4生成128位哈希值；只需使用前64位。这将是您所期望的最散乱的哈希值。

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

- Thomas Pornin

---

是的，密码哈希本身并不一定是不好的，因此我建议如果需要评估，则进行一些基准测试。由于MD4被认为是不安全的，因此某些加密库可能会逐步淘汰其支持，因此广泛实现的MD5在可移植性和兼容性方面可能更具未来性。据我所知，Windows支持Unicode文件系统名称用于NTFS和VFAT（UTF-16；根据维基百科，NTFS使用16位字符，可以是UTF-16，但不一定）。http://en.wikipedia.org/wiki/NTFS - Arc

实际上，每个NTFS卷都有一个大写映射表，文件系统驱动程序用于进行不区分大小写的比较。 - Dominik Weber

关于速度，Java在我提供的相关问题中使用的哈希代码对于编译语言（包括C/C++和Java）可能也是足够好的 - 对于动态解释语言（例如PHP、Perl），语言函数库提供的哈希函数（通常是本机机器代码）可能比您在解释语言中提供的函数更快（还取决于输入的长度）。https://dev59.com/nXI-5IYBdhLWcg3w0MDx#1660613 - Arc

Answer 3

加密安全哈希在速度方面可能不太高效，但几乎每种编程语言都可以实现它们。
使用它们是否适合您的应用程序取决于您对速度的依赖程度-基准测试会给出一个适当的答案。

您可以使用这样一种哈希的子字符串，例如在您的路径上使用MD5，先转换为小写，以使哈希实际上是不区分大小写的（这要求您使用一种方法来小写化，该方法知道如何转换文件系统中可能出现的所有UTF-16非标准字符）。

加密安全哈希的好处是，无论您选择哪个子字符串部分，它们的分布都非常均匀，因为它们被设计为不可预测，即理想情况下哈希数据的每个部分都取决于其全部哈希数据以及其他任何部分。

- Arc

---

谢谢 - 但是我知道的MD5和几乎所有其他的“加密哈希”都比64位大。我必须缩小密钥空间。我有一种基于Unicode 5.1的方法，可以快速将字符串转换为小写。 - Dominik Weber

是的，就像我说的那样，你需要取MD5的64位子串。或者，你可以看一下这个问题：https://dev59.com/nXI-5IYBdhLWcg3w0MDx - Arc

是的，那应该可以 - 我被“子字符串”这个术语搞混了 - 我以为指的是文件路径，而不是生成的哈希值。 - Dominik Weber

选择这个方案是因为它对我来说似乎是最好的解决方案，并且评论中有很好的跟进！谢谢！ - Dominik Weber

Answer 4

您可以在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。

- reinier

---

OP正在寻找哈希算法，而您建议将GetHashCode C#函数嵌入共享库中？ - arainone