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;
    ...

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

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

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

Answer 1

在 C++17 中，您应该使用std::hash<std::string_view>它无缝工作，因为const char*可以隐式转换为它。

Answer 2

当然,创建一个临时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_t32位或64位宽的平台.

Answer 3

由于 C++17 添加了std::string_view专门std::hash化，您可以使用它来计算 C 字符串的哈希值。

例子：

#include <string_view>
#include <cstring>

static size_t hash_cstr(const char *s)
{
    return std::hash<std::string_view>()(std::string_view(s, std::strlen(s)));
}

如果您必须处理 C++17 之前的编译器，您可以检查 STL 中是否有实现定义的哈希函数并调用它。

例如，libstdc++（GCC 默认使用的）提供了std::_Hash_bytes可以这样调用的函数：

#include <functional>
// -> which finally includes /usr/include/c++/$x/bits/hash_bytes.h
#include <cstring>

static size_t hash_cstr_gnu(const char *s)
{
    const size_t seed = 0;
    return std::_Hash_bytes(s, std::strlen(s), seed);
}

Answer 4

我之前已经做过这件事，最终编写了一个函数来实现这一点，其实现方式与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;
}

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