计算复合类的哈希值

Question

我有一个 class 结构，如下所示：

class A
{
    int x,y,z;
    int w[4];
};

bool operator==(const A& a1, const A& a2) 
{ 
    for (int i=0; i<4; ++i)
        if (a1.w[i] != a2.w[i])
            return false;
    return (a1.x == a2.x && a1.y == a2.y && a1.z == a2.z)
}

class B
{
    int q,p;
    vector<A> a;
};

bool operator==(const B& b1, const B& b2) 
{ 
    return (b1.q == b2.q && b1.a == b2.a)
}

现在我需要 class B 的自定义哈希值，为此重要的是成员 p 不相关，即两个具有相等值的实例（包括所有向量 a) 中 A 的实例除了 p 应该有相同的散列。对于class A的哈希值，所有成员都是相关的。

我查找了适合的函数并发现了 DJBHash：

unsigned int DJBHash(const char* str, unsigned int length)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for (i = 0; i < length; ++str, ++i)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash;
}

我现在有两个问题：

此函数的输入是等效的字符串。有没有一种高效的方法可以将我的整数成员转换为合适的输入？我的方法是通过手动输入值来手工制作哈希函数，但我认为可能会有一些技巧，比如让所有成员变量在内存中彼此落后等。
B的哈希值是否由向量a中A实例的所有哈希值组成？还是这种分层计算会导致错误？

如果有任何建议，我将不胜感激。

Answer 1

Is there a performant way to turn my integer members into suited input

首先，让我们尝试一些简单易读的东西，看看它是否足够好。

这里是算法的增量版本：

struct Djb2Hash {
  unsigned int hash = 5381;
  
  void Add(char c) {
    hash = hash * 33 + c;
  }
};

然后再添加一些高阶函数组成结构体：

struct Djb2Hash {
    /* ... */

    void Add(int value) {
        char bytes[sizeof(int)];
        memcpy(bytes, &value, sizeof(int));
        for (auto c : bytes) {
            Add(c);
        }
    }

    void Add(const A& value) {
        Add(value.x);
        Add(value.y);
        Add(value.z);
        for (auto w : value.w) {
            Add(w);
        }
    }

    void Add(const B& value) {
        Add(value.q);
        for (auto& a : value.a) {
            Add(a);
        }
    }
}

...然后打开编译器的优化器：

https://godbolt.org/z/rceGcc

编译器：

算出来hash*33是一个shift和一个add
跳过memcpy直接读取字节
读取整数块中的字节
内联大部分方法
展开除 A 的 std::vector 之外的所有循环。

那是相当不错。您可能会通过查找算法的 SIMD 实现、对齐结构、将非散列值放在最后、确保编译器在您支持的每个平台上连续打包结构以及散列底层字节块来提高性能.

但是这样一来，您的代码可读性就会降低，变得更加复杂，而且您还依赖于实现定义的行为。所以如果这里的性能不是瓶颈，我会说坚持天真的方式。

计算复合类的哈希值

Calculating a hash value for composite classes

c++

hash

计算复合 类 的哈希值

Calculating a hash value for composite classes

c++

hash

计算复合类的哈希值