c++ - 哈希函数不严格依赖于字符串键的大小

Question

我正在制作一个哈希表，我需要制作一个不仅取决于字符串键的大小的哈希函数，因为元素周期表元素只有 1 到 3 个字符。如何创建一个散列函数，它可能基于字符串的每个字符的字节数为我提供一个索引？

Answer 1

几乎每个字符串上的哈希函数都会对字符进行哈希处理。纯粹按长度散列的字符串极为罕见。

一个简单的哈希函数系列是shift-add-XOR，顾名思义，它使用位移、加法和 XOR 的组合从字符串中获取哈希函数。它很容易实现，并且提供了相当好的密钥分布。

也就是说，如果你保证你只是使用元素周期表符号，你可能想尝试为元素找到一个完美的散列函数。这是为您正在使用的数据集定制的哈希函数，从不存在任何冲突。类似的工具gperf可用于创建此类功能。

希望这可以帮助！

Answer 2

最简单的解决方案是使用现有的解决方案，例如 FNV。但是要小心——一些非常普遍的散列函数在给定大量非常短的字符串（例如 java.lang.String 使用的那个）时表现不佳。对于通用哈希函数，我通常使用类似的东西：

size_t
hash( std::string const& value )
{
    size_t result = 2166136261;
    for ( std::string::const_iterator current = value.begin();
            current != value.end();
            ++ current ) {
        result = 127 * result + static_cast< unsigned char >( *current );
    }
    return result;
}

在乘法速度较慢的机器上，这比 FNV 略快，而且我还没有找到分布明显更差的情况。

但是，您提到最大字符串长度为三。在这种情况下，您可能可以使用更简单的技术：

size_t
hash( std::string const& value )
{
    union {
        size_t results;
        char input[ sizeof( size_t ) ];
    } working = 0;
    assert( value.size() <= sizeof( size_t ) );
    value.copy( working.input, sizeof( size_t ) );
    return working.results;
}

这两种方法都保证所有长度小于sizeof( size_t ).