c – 制表散列和N3980

发布时间：2020-12-16 03:11:34 所属栏目：百科来源：网络整理

导读：我很难适应@HowardHinnant的待处理C 1z提案 N3980 与 tabulation hashing 合作. 从头开始计算一个制表哈希与N3980中描述的散列算法(Spooky,Murmur等)相同.这不是那么复杂：只需通过hash_append()序列化任何用户定义类型的对象,并让哈希函数在一个随机数表中

我很难适应@HowardHinnant的待处理C 1z提案 N3980与 tabulation hashing合作.

从头开始计算一个制表哈希与N3980中描述的散列算法(Spooky,Murmur等)相同.这不是那么复杂：只需通过hash_append()序列化任何用户定义类型的对象,并让哈希函数在一个随机数表中更新一个指针.

当尝试实现列表哈希的一个不错的属性时,麻烦就开始了：如果对象被突变,则计算对哈希的增量更新是非常便宜的.对于“手工”制表散列,只需重新计算对象受影响字节的散列.

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

说明设计困难：说我有一个用户定义的类型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的精神.例如,将新数据成员添加到包含类中,将改变类布局,从而改变序列化字节流中的偏移量.

应用：制表散列很旧,最近已经显示出它有非常好的数学属性(参见维基百科链接).它也是非常受欢迎的棋盘游戏编程社区(电脑象棋,例如),它以Zobrist hashing的名义.在那里,一个板位置扮演X的角色,并移动一个小的更新的作用(移动一块从其来源到其目的地例如).如果N3980不仅可以适应这种制表散列,那么这将是很好的,但它也可以适应便宜的增量更新.

解决方法

看来你应该能够通过告诉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的字节流地址.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!