SIMD值的Sane哈希值？

Question

我想用__m128i作为测试一个简单的hashmap，但是C ++抱怨散列函数不兼容：

/Applications/Xcode.app/[...]/c++/v1/__hash_table:880:5: error: static_assert failed due to requirement [...] "the specified hash does not meet the Hash requirements"

    static_assert(__check_hash_requirements<_Key, _Hash>::value,
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In file included from [...] note: in instantiation of template class [...] requested here
    std::unordered_map<__m128i, std::size_t> hmap;

现在，我可以通过使用类似于此的代码提供哈希函数：

    class hash128i
    {
    public:
        std::size_t operator()(const __m128i &r) const
        {
            return something;
        }
    };

随着我发明的something，像OR高低64位的__m128i，然后使用std::hash。

鉴于哈希函数的敏感性，我不知道这种方法是否合理。

什么是__m128i（或其他SIMD变量）的优秀C ++哈希函数？

Answer 1

散列函数的实际质量在某种程度上取决于您需要的属性以及数据的分布方式。

如果您不必防止恶意输入试图用大量碰撞值阻塞您的表，那么一个相当简单的功能就足够了。

对于短整数，Chris Wellons使用他的analysis程序完成了相当多的hash-prospector。

他提到的一个很好的64位函数如下，找到here：

uint64_t splittable64(uint64_t x)
{
    x ^= x >> 30;
    x *= UINT64_C(0xbf58476d1ce4e5b9);
    x ^= x >> 27;
    x *= UINT64_C(0x94d049bb133111eb);
    x ^= x >> 31;
    return x;
}

您可以散列128位整数的两半并通过XOR组合它们，如果您希望这两半经常相同，则旋转其中一个。所以你的解决方案看起来像这样：

class hash128i
{
public:
    std::size_t operator()(const __m128i &r) const
    {
        uint64_t lower_hash = splittable64(static_cast<uint64_t>(r));
        uint64_t upper_hash = splittable64(static_cast<uint64_t>(r >> 64));
        uint64_t rotated_upper = upper_hash << 31 | upper_hash >> 33;
        return lower_hash ^ rotated_upper;
    }
};

如果您的哈希表应该抵御恶意输入，您可能希望使用以随机密钥播种的密钥哈希函数。看看SIPHash。