在 C++ 中散列原始字节？

Question

我想编写一个接受两种类型 T、U 的函数，这样 sizeof(T)+sizeof(U)<=8 并通过一个接一个地重新解释它们的字节来获得 uint64_t .但是，这似乎不起作用。我确信有一种更快、更优雅（和正确）的方法可以做到这一点，但我不知道。非常感谢任何提示。

#include <cstdint>
#include <iostream>
#include <vector>

template <typename T, typename U>
constexpr auto hash8(T x, U y) {
  static_assert(sizeof(T) + sizeof(U) <= 8);

  uint64_t u = 0;
  uint64_t v = 0;
  auto px = (uint8_t*)&x;
  auto py = (uint8_t*)&y;
  for (auto i = 0; i < sizeof(T); ++i) {
    u |= (uint64_t)px[i];
    u <<= 8;
  }
  for (auto i = 0; i < sizeof(U); ++i) {
    v |= (uint64_t)py[i];
    v <<= 8;
  }

  return u << (sizeof(U) * 8) | v;
}

int main() {
  std::cout << hash8(131, 0) << '\n';
  std::cout << hash8(132, 0) << '\n';
  std::cout << hash8(500, 0) << '\n';
}

Answer 1

最简单的方法通常是 memcpy:

#include <cstdint>
#include <cstring> // for memcpy

template <typename T, typename U>
auto hash8(T x, U y) {
  static_assert(sizeof(T) + sizeof(U) <= 8);

  uint64_t u = 0;
  char* u_ptr = reinterpret_cast<char*>(&u);
  std::memcpy(u_ptr, &x, sizeof x);
  std::memcpy(u_ptr+sizeof x, &y, sizeof y);
  return u;
}

如果大小参数在编译时已知（并且相当小），任何体面的编译器都会将 memcpy 调用内联到一些位操作。

如果您确实需要 constexpr 函数，您可以尝试使用 C++20 中的 std::bit_cast（如果输入参数的大小不是 1、2、4 或8).

Answer 2

由于缺乏细节，我无法解决您代码中的问题，但我可以提出一个可能更简单的解决方案。

首先，我建议添加检查参数对象是否具有唯一的对象表示。除非满足，否则散列将毫无意义。

其次，std::memcpy 可能会使这更简单：

template <typename T, typename U>
auto
hash8(T x, U y) noexcept {
    static_assert(sizeof x + sizeof y <= sizeof(std::uint64_t));
    static_assert(std::has_unique_object_representations_v<T>);
    static_assert(std::has_unique_object_representations_v<U>);
    std::uint64_t ret{};
    auto ptr = reinterpret_cast<unsigned char*>(&ret);
    std::memcpy(ptr, std::addressof(x), sizeof x);
    ptr += sizeof x;
    std::memcpy(ptr, std::addressof(y), sizeof y);
    return ret;
}

接下来，我们可以将其推广到任意数量的参数（只要它们合适）和不同的 return 类型：

template <typename R = std::uint64_t, typename... Args>
auto
hash(Args... args) noexcept {
    static_assert((sizeof args + ...) <= sizeof(R));
    static_assert((std::has_unique_object_representations_v<Args> && ...));
    static_assert(std::has_unique_object_representations_v<R>);
    R ret{};
    auto ptr = reinterpret_cast<unsigned char*>(&ret);
    (
        (
            std::memcpy(ptr, std::addressof(args), sizeof args),
            ptr += sizeof args
        ), ...
    );
    return ret;
}

需要注意的是，即使对象的大小匹配，这样的散列在不同系统中也不相同。

P.S。使你的函数 constexpr 毫无意义，因为你使用了常量表达式中不允许的重新解释转换。

在 C++ 中散列原始字节？

Hashing raw bytes in C++?

c++

hash

bit-manipulation

bitwise-operators