如何为 std::vector<std::vector<bool>> 编写哈希函数

Question

我有一个结构，它有一个变量，一个 std::vector<std::vector<bool>> 代表一个网格。如果网格相等，或者网格的任何旋转相等，则这些结构之一等于另一个。我正在尝试使用 unordered_set 来存储其中的许多内容，但是，经过一些研究，我发现我需要某种哈希函数。我以前从未使用过散列函数，我发现的有关它的内容让我感到困惑。所以，我的问题是，I/what 是为这种数据类型编写哈希函数的最佳方法，还是只使用一组无序的网格并在我添加它们时测试旋转更好？

一些代码：

int nx, ny;

typedef std::vector<std::vector<bool>> grid;

struct rotateableGrid {
public:
    grid data;
    rotateableGrid(grid data) : data(data) {}
    rotateableGrid(rotateableGrid &rg) : data(rg.data) {}
    bool operator==(const rotateableGrid & rhs) {
        for (int c = 0; c < 4; c++) {
            if (rotate(c) == rhs.data) return true;
        }
        return false;
    }
private:
    grid rotate(int amt) {
        if (amt % 4 == 0) return data;

        grid ret(ny, std::vector<bool>(nx));

        for (int x = 0; x < nx; x++) {
            for (int y = 0; y < ny; y++) {
                switch (amt % 4) {
                case 1:
                    if (x < ny && nx - 1 - y >= 0) ret[x][nx - 1 - y] = data[y][x];
                    break;
                case 2:
                    if (nx - 1 - x >= 0 && ny - 1 - y >= 0) ret[ny - 1 - y][nx - 1 - x] = data[y][x];
                    break;
                case 3:
                    if (ny - 1 - x >= 0 && y < nx) ret[x][nx - 1 - y] = data[y][x];
                    break;
                default:
                    break;
                }
            }
        }

        return ret;
    }
};

提前致谢！

注意：我在 VS 2013 中使用 C++

Answer 1

您可以做的是合并矩阵中所有向量的哈希值。 std::vector<bool> 的 std::hash 过载。如果你尝试这样的事情

size_t hash_vector(const std::vector< std::vector<bool> >& in, size_t seed)
{
    size_t size = in.size();
    std::hash< std::vector<bool> > hasher;
    for (size_t i = 0; i < size; i++)
    {
        //Combine the hash of the current vector with the hashes of the previous ones
        seed ^= hasher(in[i]) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    return seed;
}

为了获得旋转不变性，您需要结合网格所有旋转的哈希值。正如@zch 在评论中所建议的那样，您可以这样做

size_t hash_grid(rotateableGrid& in, size_t seed = 92821)
             //  ^^^^^ Should be const, but rotate isn't marked const
{
    return hash_vector(in.data) ^ hash_vector(in.rotate(1).data) ^ hash_vector(in.rotate(2).data) ^ hash_vector(in.rotate(3).data);
}

但是，由于 rotateableGrid 的轮换成员标记为私有，您必须将 hash_grid 声明为 rotateableGrid 的朋友。为此，您必须将其添加到 rotateableGrid

的定义中

friend size_t hash_grid(rotateableGrid&, size_t);

如何为 std::vector<std::vector<bool>> 编写哈希函数

How to write a hash function for a std::vector<std::vector<bool>>

c++

hash

struct

stl

unordered-set