制表散列和N3980

Question

我无法适应待处理的C++ 1Z提案N3980通过@HowardHinnant一起工作制表散列.

从头开始计算制表散列的工作方式与N3980中描述的散列算法(Spooky,Murmur等)相同.它并不复杂:只需通过hash_append()序列化任何用户定义类型的对象,并让哈希函数在您进行时将指针更新为随机数表.

当试图实现制表散列的一个很好的属性时,麻烦就开始了:如果一个对象发生变异,计算散列的增量更新非常便宜.对于"手工制作"制表哈希,只需重新计算对象受影响字节的哈希值.

我的问题是:如何uhash<MyTabulationAlgorithm>在保持N3980的中心主题(类型不知道#)的同时,将功能对象的增量更新通信？

为了说明设计上的困难:假设我有一个用户定义的类型X,其中包含各种类型的N个数据成员xi

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的精神.例如,将新数据成员添加到包含类将更改类布局,从而更改序列化字节流中的偏移量.

应用程序:制表哈希是非常古老的,最近已经证明它具有非常好的数学属性(参见维基百科链接).它在棋盘游戏编程社区(计算机象棋,例如)中也很受欢迎,它以Zobrist哈希的名义命名.在那里,董事会职位扮演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使用类似的策略计算程序启动时的字节流地址.