c++ - 制表哈希和 N3980

Question

我在调整未决的 C++1z 提案时遇到问题 N3980由@HowardHinnant 与 tabulation hashing 合作.

从头计算制表哈希的工作原理与 N3980 中描述的哈希算法(Spooky、Murmur 等)相同。它并没有那么复杂:只需通过 hash_append() 序列化任何用户定义类型的对象，然后让哈希函数在您进行时将指针更新为随机数表。

当尝试实现制表散列的一个不错的属性时，麻烦就开始了:如果对象发生变异，计算散列的增量更新非常便宜。对于“手工制作”的制表哈希，只需重新计算对象受影响字节的哈希。

我的问题是:如何将增量更新传达给 uhash<MyTabulationAlgorithm>函数对象，同时保持 N3980 的中心主题(Types don't know #)？

为了说明设计难点:假设我有一个用户定义的类型 X，其中有 N 个数据成员 xi 各种类型 Ti

struct X 
{
   T1 x1;
   ...
   TN xN;
};

现在创建一个对象并计算它的散列

X x { ... }; // initialize
std::size_t h = uhash<MyTabulationAlgorithm>(x);

更新单个成员，并重新计算散列

x.x2 = 42;
h ^= ...; // ?? I want to avoid calling uhash<>() again

我可以像这样计算增量更新

h ^= hash_update(x.x2, start, stop); 

哪里[start, stop)表示对应于 x2 数据成员的随机数表的范围。然而，为了增量地(即便宜地!)更新任意突变的散列，每个数据成员都需要以某种方式知道其包含类的序列化字节流中自己的子范围。这感觉不像是N3980的精神。例如，向包含的类添加新的数据成员会改变类布局，从而改变序列化字节流中的偏移量。

应用:tabulation hashing 非常古老，最近被证明具有非常好的数学特性(参见维基百科链接)。它在棋盘游戏编程社区(例如计算机国际象棋和围棋)中也很受欢迎，它的名称为 Zobrist hashing。 .在那里，棋盘位置扮演 X 的角色，移动扮演小更新的角色(例如，将棋子从其源移动到目的地)。如果 N3980 不仅可以适应这种制表哈希，而且还可以适应廉价的增量更新，那就太好了。

Answer 1

似乎您应该能够通过告诉 MyTabulationAlgorithm 忽略所有类成员的值来做到这一点，除了已更改的值:

x.x2 = 42;
IncrementalHashAdaptor<MyTabulationAlgorithm, T2> inc{x.x2};
hash_append(inc, x);
h ^= inc;

IncrementalHashAdaptor 所要做的就是检查传递给它的内存范围，看它是否包含 x2:

template<class HashAlgorithm, class T>
struct IncrementalHashAdaptor
{
    T& t;
    HashAlgorithm h = {};
    bool found = false;
    void operator()(void const* key, std::size_t len) noexcept
    {
        if (/* t contained within [key, key + len) */) {
            assert(!found);
            found = true;
            char const* p = addressof(t);
            h.ignore(key, (p - key));
            h(p, sizeof(T));
            h.ignore(p + sizeof(T), len - (p - key) - sizeof(T));
        }
        else {
            h.ignore(key, len);
        }
    }
    operator std:size_t() const { assert(found); return h; }
};

显然，这仅适用于对象位置既可以从外部确定又对应于传递给哈希算法的内存块的成员；但这应该对应于绝大多数情况。

您可能希望将 IncrementalHashAdaptor 和以下 hash_append 包装到 uhash_incremental 实用程序中；这是留给读者的练习。

性能有问号；假设 HashAlgorithm::ignore(...) 对编译器可见并且不复杂，它应该优化得很好；如果这没有发生，您应该能够使用类似的策略在程序启动时计算出 X::x2 的字节流地址。