char \* 值而不是内存地址上的 std::hash 值？

Question

如本 链接 所述：

C 字符串没有专门化。 std::hash 产生指针值（内存地址）的哈希值，它不检查任何字符数组的内容。

这意味着使用相同的 char* 值，可以产生不同的哈希码。例如，有这个代码：

 //MOK and MOV are template arguments
void emit(MOK key, MOV value) {
    auto h = hash<MOK>()(key);
    cout<<"key="<<key<<" h="<<h<<endl;
    ...

这是通过在同一个 key （使用 MOK=char* ）值（但 4 个不同的标记/字符串对象）上调用 4 次 emit() 产生的输出：

 key=hello h=140311481289184
key=hello h=140311414180320
key=hello h=140311414180326
key=hello h=140311481289190

如何获得 char* 的相同哈希码？我不想使用 boost

原文由 justHelloWorld 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

当然，创建一个临时的 std::string 并对其进行散列是一种简单（且缓慢）的解决方案。如果您不想这样做，恐怕您将不得不实现自己的哈希函数。可悲的是，当前的 C++ 标准库没有提供脱离特定对象哈希解决方案的通用哈希算法。 （但有 一些希望 这可能会在未来改变。）

假设你有一个函数

std::size_t
hash_bytes(const void * data, std::size_t size) noexcept;

这将获取一个地址和一个大小，并返回一个根据该地址后面的那么多字节计算的哈希值。借助该功能，您可以轻松编写

template <typename T>
struct myhash
{
  std::size_t
  operator()(const T& obj) const noexcept
  {
    // Fallback implementation.
    auto hashfn = std::hash<T> {};
    return hashfn(obj);
  }
};

然后将其专门用于您感兴趣的类型。

 template <>
struct myhash<std::string>
{
  std::size_t
  operator()(const std::string& s) const noexcept
  {
    return hash_bytes(s.data(), s.size());
  }
};

template <>
struct myhash<const char *>
{
  std::size_t
  operator()(const char *const s) const noexcept
  {
    return hash_bytes(s, std::strlen(s));
  }
};

这让您只需要执行 hash_bytes 的练习。幸运的是，有一些相当不错的散列函数很容易实现。我的简单散列算法是 Fowler-Noll-Vo 散列函数。你可以用五行代码来实现它；请参阅链接的维基百科文章。

如果您想花哨一点，请考虑以下实现。首先，我定义了一个通用的 template 可以专门用于任何版本的 FNV-1a 哈希函数。

 template <typename ResultT, ResultT OffsetBasis, ResultT Prime>
class basic_fnv1a final
{

  static_assert(std::is_unsigned<ResultT>::value, "need unsigned integer");

public:

  using result_type = ResultT;

private:

  result_type state_ {};

public:

  constexpr
  basic_fnv1a() noexcept : state_ {OffsetBasis}
  {
  }

  constexpr void
  update(const void *const data, const std::size_t size) noexcept
  {
    const auto cdata = static_cast<const unsigned char *>(data);
    auto acc = this->state_;
    for (auto i = std::size_t {}; i < size; ++i)
      {
        const auto next = std::size_t {cdata[i]};
        acc = (acc ^ next) * Prime;
      }
    this->state_ = acc;
  }

  constexpr result_type
  digest() const noexcept
  {
    return this->state_;
  }

};

接下来，我为 32 位和 64 位版本提供别名。参数取自 Landon Curt Noll 的网站。

 using fnv1a_32 = basic_fnv1a<std::uint32_t,
                             UINT32_C(2166136261),
                             UINT32_C(16777619)>;

using fnv1a_64 = basic_fnv1a<std::uint64_t,
                             UINT64_C(14695981039346656037),
                             UINT64_C(1099511628211)>;

最后，我提供类型元函数来选择给定所需位数的算法版本。

 template <std::size_t Bits>
struct fnv1a;

template <>
struct fnv1a<32>
{
  using type = fnv1a_32;
};

template <>
struct fnv1a<64>
{
  using type = fnv1a_64;
};

template <std::size_t Bits>
using fnv1a_t = typename fnv1a<Bits>::type;

有了这个，我们就可以开始了。

 constexpr std::size_t
hash_bytes(const void *const data, const std::size_t size) noexcept
{
  auto hashfn = fnv1a_t<CHAR_BIT * sizeof(std::size_t)> {};
  hashfn.update(data, size);
  return hashfn.digest();
}

请注意此代码如何自动适应 std::size_t 为 32 或 64 位宽的平台。

原文由 5gon12eder 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我以前必须这样做，最后编写了一个函数来执行此操作，其实现与 Java 的 String 哈希函数 基本相同：

 size_t hash_c_string(const char* p, size_t s) {
    size_t result = 0;
    const size_t prime = 31;
    for (size_t i = 0; i < s; ++i) {
        result = p[i] + (result * prime);
    }
    return result;
}

请注意，这不是加密安全哈希，但它足够快并产生良好的结果。

原文由 Aaditya Kalsi 发布，翻译遵循 CC BY-SA 3.0 许可协议