c++ - 如何哈希一个三态二维数组？

Question

考虑以下代码。在 unordered_map 中使用 Key 中的数组的好的散列函数是什么？

#include <unordered_map>

using namespace std;

enum TriState {
    S0 = -1,
    S1 = 0,
    S2 = +1
};

struct K { // Key for the map
    TriState a[8][8];
    bool operator==(const K& k1) const {
        for (int i = 0; i < 64; i++)
            if (k1.a[0][i] != a[0][i])
                return false;
        return true;
    }
};

struct Hash {
    size_t operator()(const K& k) const {
        size_t s;
        // s = what is a good hash value?
        return s;
    }
};

unordered_map<K, int, Hash> m;

Answer 1

这个算法应该很快并且提供近乎均匀的散列:

size_t s = 0x3a7eb429; // Just some random seed value
for (int i = 0; i != 8; ++i)
{
    for (int j = 0; j != 8; ++j)
    {
        s = (s >> 1) | (s << (sizeof(size_t) * 8 - 1));
        s ^= k.a[i][j] * 0xee6b2807;
    }
}
s *= 0xee6b2807;
s ^= s >> 16;

在那之后，如果你想让散列更强大，再次使用 hash s 例如 MurmurHash3 .