时间戳

首页 > 解决方案 > 计算复合类的哈希值

c++ - 计算复合类的哈希值

问题描述

我有一个如下的类结构：

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)
}

现在我需要 B 类的自定义散列值，重要的是成员 p不相关，即两个具有相等值的实例（包括向量 a 中的所有 A 实例）除了 p 应该具有相同的散列。对于 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;
}

我现在有两个问题：

  1. 此函数的输入是等效的字符串。有没有一种高效的方法可以将我的整数成员转换为合适的输入？我的方法是通过手动输入值来手工制作散列函数，但我认为可能会有一些技巧，比如将所有成员变量放在内存中，等等。

  2. B 的哈希值是否包含向量 a 中 A 实例的所有哈希值？还是这种分层计算会导致错误？

我非常感谢您对此提出任何建议。

标签： c++hash

解决方案

有没有一种高效的方法可以将我的整数成员转换为合适的输入

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

这是算法的增量版本：

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是一个转变和一个添加
  • 跳过memcpy并直接读取字节
  • 读取整数大小块中的字节
  • 内联大部分方法
  • 展开除 A 之外的所有循环std::vector。

这真是太好了。您可以通过查找算法的 SIMD 实现、对齐结构、将非散列值放在最后、确保编译器在您支持的每个平台上连续打包结构以及散列底层字节块来挤出更多性能.

但是，您的代码将变得不那么可读，更复杂，然后您将依赖于实现定义的行为。因此，如果这里的性能不是瓶颈，我会说坚持天真的方式。

推荐阅读