c++ - 散列 std::vector 独立于项目顺序

Question

我正在为 std::vector 寻找一个散列函数，它独立于 vector 项的排序。

换句话说，我正在寻找一个散列实现， 这会给我同样的结果

std::vector<int> v1(1,2,3);
std::vector<int> v2(2,3,1);
std::vector<int> v3(1,3,2); 

关于如何实现这一点有什么想法吗？

Answer 1

template<template<class...>class element_hash=std::hash>
struct symmetric_range_hash {
  template<class T>
  std::size_t operator()( T const& t ) const {
    std::size_t r = element_hash<int>{}(0); // seed with the hash of 0.
    for (auto&& x:t) {
      using element_type = std::decay_t<decltype(x)>;
      auto next = element_hash<element_type>{}(x);
      r = r + next;
    }
    return r;
  }
};

应该可以了。我们通过对称的 + 收集哈希值。

+ 比 ^ 好，因为它需要更长的时间才能得到一个循环。使用 ^，{1,1} 和 {2,2} 会散列相同的内容(通常偶数的任何东西都会“消失” ).使用 +，它们会成倍增加。

因此，对于数组中的每个不同值，最终结果是该值的散列乘以其计数的总和，mod "max(size_t)+1"。

请注意，unordered_map 需要散列和相等性。如果你想要碰撞，你还需要写一个 ==。

struct unordered_equal {
  template<class C>
  bool operator()(C const& lhs, C const& rhs)const {
    using std::begin;
    using K = std::decay_t< *decltype(begin(lhs)) > >;
    std::unordered_map< K, std::size_t > counts;
    for (auto&& k : lhs) {
      counts[k]++;
    }
    for (auto&& k : rhs) {
      counts[k]--;
    }
    for (auto&& kv : counts)
      if (kv.second != 0) return false;
    return true;
  }
};