Shouldn't hash_combine use different constants for 32/64 bit size_t?

[IvanPizhenko]

Current code seems to be taken from Boost, but it is likely 32-bit oriented. Shouldn't the different constant be used for 64-bit size_t?

hash_append/n3876.h

Line 34 in bd892bf

seed ^= std::hash<T>{}(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);

[HowardHinnant]

This code came from http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf and is used only for comparison purposes with that proposal.

[IvanPizhenko]

Hmm, and is there a way for non-comitee member, i.e. for just anyone, to submit such a remark to N3876? Because it is really 32-bit based. The paper on which Boost have based it, mentioned also in the N3876 is http://www.cs.rmit.edu.au/~jz/fulltext/jasist-tch.pdf
and it says on the page 7: "The fingerprint generation function should produce as close as possible to a uniform distribution of integers [5]. The minutiae produced lie between two bounds—generally 0 and an arbitrarily high number such as 2^32 ". So in the Boost it likely was written at the times of 32-bit CPUs, and then N3876 blindly copied that.

[IvanPizhenko]

The constant itself should be coming from TEA algorithm, if we admit to process of its derivation, as described here https://softwareengineering.stackexchange.com/a/63599/188077 we must come up with different constant for different hash lengths. As follows:

• 8-bit: 158 or 0x9E.
• 16 bit:40 503 or 0x9E37.
• 32-bit: 2 654 435 769 or 0x9E3779B9.
• 64-bit: 11 400 714 819 323 198 485 or 0x9e3779b97f4a7c15.
• 128-bit (if we whenever get it): 210 306 068 529 402 873 165 736 369 884 017 287 508 or 0x9e3779b97f4a7c15f39cc0605d396154.
  (Written a small Java program to compute that: https://gist.github.com/ivanp2015/1fb04bc8570da4801a19efba5ec8945f)

[HowardHinnant]

This: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0814r2.pdf is the latest hash_combine proposal. It will be discussed this coming week in Jacksonville, FL. It looks poised to be standardized. I recommend emailing the author directly.

[IvanPizhenko]

Thank you, Howard, I have looked at the paper, and "proposed wording" looks quite generic and does not suggest any particular implementation, so there's actually no impact on the standard, and reference example still example and not final implementation. So looks like it is more proper to file this to the Boost.

[NikolausDemmel]

I'm just researching a little on how to create a simple hash-combine for my project, e.g. to support std::pair keys in std::unordered_map. I'd like to avoid adding an external dependency.

I came across the mentioned hash-combine

seed ^= std::hash<T>{}(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);

in multiple places, and thus also this issue. Since I'm interested mostly in a version where size_t is 64bit, and I'm greateful for the "magic number" for 64bit hashes posted above. However, what is not clear, is what should be done to the bit-shifts. Can anyone here judge if this the following would be a reasonable hash combiner for 64bit?

seed ^= std::hash<T>{}(val) + 0x9e3779b97f4a7c15 + (seed<<6) + (seed>>2); 

Should the shifts be different? For my application it doesn't have to be perfect and I'd prefer a simple and fast solution, but I'd like to avoid obvious mistakes.

[IvanPizhenko]

Since 64 bit is 2x of 32 bit, you can try increasing shifts 2x. i.e. seed << 12 and seed >> 4

[IvanPizhenko]

To make it even more portable, maybe following can be done:

#include <cstdint>

template <typename T>
inline void hash_combine (std::uint16_t& seed, const T& val)
{
    seed ^= std::hash<T>{}(val) + 0x9e37U + (seed<<3) + (seed>>1);
}

template <typename T>
inline void hash_combine (std::uint32_t& seed, const T& val)
{
    seed ^= std::hash<T>{}(val) + 0x9e3779b9U + (seed<<6) + (seed>>2);
}


template <typename T>
inline void hash_combine (std::uint64_t& seed, const T& val)
{
    seed ^= std::hash<T>{}(val) + 0x9e3779b97f4a7c15LLU + (seed<<12) + (seed>>4);
}

Proper overload will be automatically invoked, depending on the actual size of the std::size_t.

[NikolausDemmel]

Awesome thanks for you reply. Makes sense to me. Might not be the best ever possible, but considering we were using a simple xor at some point to combine hashes, this is a step up. I ended up with using constexpr, since there might be some weirdness where size_t is neither uint32_t nor uint64_t.

// to work around static_assert(false, ...)
template <class T>
struct dependent_false : std::false_type {};

template <class T>
inline void hash_combine(std::size_t& seed, const T& value) {
  // Simple hash_combine, see e.g. here:
  // https://github.com/HowardHinnant/hash_append/issues/7
  // Not sure we ever need 32bit, but here it is...
  if constexpr (sizeof(std::size_t) == 4) {
    seed ^= std::hash<T>{}(value) + 0x9e3779b9U + (seed << 6) + (seed >> 2);
  } else if constexpr (sizeof(std::size_t) == 8) {
    seed ^= std::hash<T>{}(value) + 0x9e3779b97f4a7c15LLU + (seed << 12) +
            (seed >> 4);
  } else {
    static_assert(dependent_false<T>::value, "hash_combine not implemented");
  }
}

[IvanPizhenko]

@NikolausDemmel size_t is unsigned type by definition. So chances that it will not fit either into uint16_t, uint32_t or uint64_t are very low. Your solution with if constexpr obviously works, but requires C++17, while overloads will work for the earlier standards too.

[NikolausDemmel]

unsigned is clear, but what happened apparently is that size_t was unsigned long and uint64_t was unsigned long long, both 64bit, but distinct types. Fair point about C++17, that is fine for me, but maybe not in other cases. I guess whoever finds this can chose whatever suits them.

[JVApen]

Is there any update on the fix for this issue?

[IvanPizhenko]

@JVApen This is not a bug, just a suggestion. If you find it useful, you can take n3876.h from here and patch it yourself using code examples discussed above. Also, since the discussion is already quite old, and at the momemt none of the discussed above code example is included into n3876.h, I doubt @HowardHinnant will ever do it.

[HowardHinnant]

That's correct. hash_combine is not part of this proposal, nor do I recommend it. As the readme states, the entirety of this proposal is in one file: hash_append.h. Everything thing else is used as examples or comparisons.