c++ 使用std::string作为 Package 器来散列原始缓冲区是不是不好?

wnavrhmk  于 2023-04-08  发布在  其他
关注(0)|答案(1)|浏览(92)

C++ std::hash<>has some standard specializations用于固定大小的基本类型,以及std::string家族,这是唯一一个具有可变内存大小的家族(还有std::vector<bool>,这里不关心)
一旦我们倾向于散列多个变量或一个缓冲区,我们需要实现一个散列算法,这是很难记住,很容易出错。
std::string可以用作缓冲区(我知道std::vector<std::byte>更好),如果我们在其中存储utf-8字符串(包含ASCII以外的字节),它可能也是哈希的。
这样的缺点是什么:

std::string hash_wrapper(4 * 4, '\0');
int* write_ptr = reinterpret_cast<int*>(hash_wrapper.data());

write_ptr[0] = val1;
write_ptr[1] = val2;
write_ptr[2] = val3;
write_ptr[3] = val4;

std::unordered_map<std::string, int> ht;
ht[hash_wrapper] = val;
qvk1mo1f

qvk1mo1f1#

您的代码违反了严格别名。
你的代码非常不清楚它在做什么。
散列Map的关键在于它们是Map,散列Map是从一个模糊的转换字符串类型到数据,而不是从一个合理的键到数据。
我的建议是:
1.写一个散列组合器,或者使用其他人发布的散列组合器(具有适当的属性/权限),如boost的散列组合器。
1.扩展到散列组合器,它采用任意散列序列并将其组合。
现在写一个简短的库。

namespace MyHash {
  // by default, dispatch to std::hash:
  template<class T>
  std::size_t runtime_hash( T const& t ) {
    return std::hash<T>{}(t);
  }
  // range-like support (begin/end):
  template<class R>
  std::size_t hash_range( R const& r );
  // tuple-like support (std::get, etc):
  template<std::size_t...Is, class T>
  std::size_t tuple_hasher( std::index_sequence<Is...>, T const& t );

  // TODO: supply this function
  inline std::size_t hash_combine( std::size_t lhs, std::size_r rhs ) {
    // write this
  }
  // support for 0 to infinite args:
  inline std::size_t hash_combine( std::size_t x ) {
    return x;
  }
  inline std::size_t hash_combine() {
    return 0;
  }
  template<class...Ts>
  std::size_t hash_combine( std::size_t lhs, std::size_t rhs, Ts... ts ) {
    return hash_combine( lhs, hash_combine( rhs, ts... ) );
  }

  // Add std runtime_hashs here:

  // std "range" type supports:
  template<class...Ts>
  std::size_t runtime_hash( std::vector<Ts...> const& v ) {
    return hash_range(v);
  }
  template<class...Ts>
  std::size_t runtime_hash( std::set<Ts...> const& s ) {
    return hash_range(s);
  }
  template<class...Ts>
  std::size_t runtime_hash( std::unordered_set<Ts...> const& s ) {
    return hash_range(s);
  }
  template<class...Ts>
  std::size_t runtime_hash( std::map<Ts...> const& m ) {
    return hash_range(m);
  }
  template<class...Ts>
  std::size_t runtime_hash( std::unordered_map<Ts...> const& m ) {
    return hash_range(m);
  }

  // tuple-like support:
  template<class...Ts>
  std::size_t runtime_hash( std::tuple<Ts...> const& t ) {
    return tuple_hasher( std::make_index_sequence<Ts...>{}, t );
  }
  template<class T0, class T1>
  std::size_t runtime_hash( std::pair<T0, T1> const& t ) {
    return tuple_hasher( std::make_index_sequence<2>{}, t );
  }
  template<class T, std::size_t N>
  std::size_t runtime_hash( std::array<T, N> const& t ) {
    return tuple_hasher( std::make_index_sequence<N>{}, t );
  }

  // optional.  Note that hash of an engaged optional is distinct
  // from a hash of a value by a hash_combine.  An optional acts
  // as a range of 0 or 1 element hash-wise.
  template<class T>
  std::size_t runtime_hash( std::optional<T> const& t ) {
    std::size_t retval = 0x0;
    if (t) retval = hash_combine(retval, runtime_hash(t) );
    return retval;
  }
  // add more types here!

  struct runtime_hasher {
    template<class T>
    std::size_t operator()(T const& t)const{
      return runtime_hash(t);
    }
  };
  
  template<class R>
  std::size_t hash_range( R const& r ) {
    std::size_t seed = 0;
    for (auto const& e : r) {
      seed = hash_combine( seed, runtime_hash(r) );
    }
  }
  template<std::size_t...Is, class T>
  std::size_t tuple_hasher( std::index_sequence<Is...>, T const& t ) {
    return hash_combine( runtime_hash(std::get<Is>(t))... );
  }
}

现在,只要你需要一个自定义的运行时哈希,就在类型的命名空间中为你的自定义类型重写runtime_hash
通过这项工作

namespace bob {
  struct alice {
    int val1, val2, val3, val4;
    friend auto operator==(const alice&, const alice&) = default;
  };
}

我可以添加哈希支持:

namespace bob {
  inline std::size_t runtime_hash( alice const& a ) {
    return runtime_hash( std::tie(a.val1, a.val2, a.val3, a.val4) );
  }
}

有了这个

std::unordered_map<bob::alice, int, MyHash::runtime_hasher> map;

只是工作。
runtime_hash函数是通过ADL找到的。更重要的是,std::vector<bob::alice>有哈希支持,std::tuple<bob::alice>std::tuple<std::set<bob::alice>, bob::alice>等也是如此。如果你写任何其他复合类型并像我做的std容器一样给予它,那些包含bob::alice的容器也可以工作。
上面这个实用程序代码的大小和复杂性都足够短,因此,在缓冲区和指针以及未定义的别名之间浪费时间是绝对不值得的。
请注意,我将其命名为runtime_hash--这既使其具有某种独特的命名(对ADL很重要),也强调了无法保证此哈希在程序的不同执行过程中是稳定的。您不能以这种方式依赖std哈希的稳定性,因为它们不提供这种保证。
上面的代码是直接输入到答案中的,从未被编译过,所以它可能至少包含一个tpyo。

相关问题