如何散列三态二维数组？

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;

之后，如果您想让散列变得更强，请使用例如MurmurHash3再次进行散列。