Search code examples
c++hashc++17hash-function

C++ - Hash/Map a std::vector<uint64_t> in a single uint64_t

I need to map a std::vector<uint64_t> to a single uint64_t. It is possible to do? I thought to use a hash function. Is that a solution?

For example, this vector:

std::vector<uint64_t> v {
  16377,
  2631694347470643681,
  11730294873282192384
}

should be converted into one uint64_t.

If a hash function is not a good solution (e.g. high percentage of collision) there is an alternative to do this mapping?

Solution

  • I need to hash a std::vector<uint64_t> to a single uint64_t. It is possibile to do?

    Yes, variable length hash functions exist, and it's possible to implement them in C++.

    C++ standard library comes with a few hash functions, but unfortunately not for vector (other than for the bool specialisation). We can reuse the hash function provided for string views, but this is a bit of a cludge:

    const char* data = reinterpret_cast<const char*>(v.data());
std::size_t size = v.size() * sizeof(v[0]);
std::hash<std::string_view> hash;
std::cout << hash(std::string_view(data, size));

    Note that using this is reasonable only in the case std::has_unique_object_representations_v is true of the element type of vector. I think it's reasonable to assume that to be the case for std::uint64_t.

    A caveat when using standard library hash functions is that they don't have exact specification and as such you cannot rely on hashes being identical across separate systems. You should use another hash function if that is a concern.