- 5 months ago 45
C++ Question

Hashing std::vector independent of items order

I am looking for a hash function for

, which would be independent from vector's item's ordering.

In other words I am looking for a hash implementation,
that would give me same result for

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

Any ideas on how I might accomplish this?

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;

That should do it. We gather the hashes via + which is symmetric.

+ is better than ^ because it takes longer to get a cycle. With ^, {1,1} and {2,2} would hash the same (and in general even numbers of anything "disappear"). With + they instead get multiplied.

So the end result is the sum, for each distinct value in the array, of the hash of that value times its count, mod "max(size_t)+1".