c++ - 短文件名的最佳字符串散列函数

Question

对于像字符串这样的文件名来说，最好的字符串散列函数是什么？字符串将类似于：

pics/test.pic
maps/test.map
materials/metal.mtl

Answer 1

如果要散列的数据的性质不需要任何花哨的散列算法，例如文本字符串的性质，您可能需要尝试FNV 散列函数。FNV 散列是 Fowler/Noll/Vo 的缩写，以纪念创造者，是一种非常快速的算法，已在许多应用程序中使用并取得了出色的结果，而且由于其简单性，FNV 散列应该是最早尝试的散列之一一个应用程序。

unsigned int fnv_hash (void* key, int len)
{
    unsigned char* p = key;
    unsigned int h = 2166136261;
    int i;

    for (i = 0; i < len; i++)
        h = (h*16777619) ^ p[i];

    return h;
}

或者使用MD5 算法来代替，它是通用的，因此可以很好地满足您的需求。

Answer 2

不存在独立于如何使用散列的普遍“最佳”散列函数。

假设您想要一个 32 位的 int 以便在内存中使用一个小的哈希表。

然后你可以使用FNV-1a 算法：

hash = offset_basis
for each octet_of_data to be hashed
 hash = hash xor octet_of_data
 hash = hash * FNV_prime
return hash

如果您的目的是确信两条路径给出不同的哈希，那么您可以使用SHA1 算法。

如果您想确定恶意创建冲突非常困难，那么您可以使用SHA256。

请注意，最后两个算法会生成长哈希（比您的典型路径长）。

Answer 3

只需使用std::hash<std::string>. 这是您的库实现者对“最佳”通用非加密哈希函数的想法。