libxelar.so - 3 months ago 29

C++ Question

I am looking for a hash function for

`std::vector`

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?

Answer

```
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".