10

If I did std::hash using libstdc++ and then did one on the upcoming C++11 VS 2012 library - would they match?

I assume that hash implementations are not part of the C++ specification and can vary by distribution?

Marc Mutz - mmutz
  • 24,485
  • 12
  • 80
  • 90
Matt Clarkson
  • 14,106
  • 10
  • 57
  • 85
  • I think the value is unspecified, but consistent within a single execution. – Flexo Aug 16 '12 at 15:42
  • This is unlikely to be an issue, since the containers that use `std::hash` are most likely shipped in header-only libraries, too, so you're getting the entire package anyway. – Kerrek SB Aug 16 '12 at 15:45
  • No, the standard doesn't specify the value of the function, only it's characteristics. – Daniel Aug 16 '12 at 15:46
  • Thanks to everyone. I read `17.6.3.4` but just wanted to be sure. There are three answers that are identical - what is the standard procedure that I should follow to accept the correct answer? – Matt Clarkson Aug 16 '12 at 15:54
  • 1
    @MattClarkson - oldest answer or best formatted or best text with the quote are sensible options. It's entirely up to you though. – Flexo Aug 16 '12 at 15:58
  • @Flexo went with most votes/best formatted. – Matt Clarkson Aug 17 '12 at 11:25
  • 1
    They can (but typically don't) vary by run, and will be required to if goes through. Whether or not it does, std::hash is not good to use for fingerprinting. – Nevin Aug 17 '12 at 14:26

3 Answers3

9

No, this is not guaranteed. std::hash only has to respect the following conditions:

  1. Accepts a single parameter of type Key.
  2. Returns a value of type size_t that represents the hash value of the parameter.
  3. Does not throw exceptions when called.
  4. For two parameters k1 and k2 that are equal, std::hash()(k1) == std::hash()(k2).
  5. For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric_limits::max().

http://en.cppreference.com/w/cpp/utility/hash

user1202136
  • 11,171
  • 4
  • 41
  • 62
  • 2
    While cppreference is a good site (I use it all the time myself), it is not equivalent to the standard. – KillianDS Aug 16 '12 at 16:06
9

The standard only says this:

20.8.12 Class template hash The unordered associative containers defined in 23.5 use specializations of the class template hash as the default hash function. For all object types Key for which there exists a specialization hash, theinstantiation hash shall:

  • satisfy the Hash requirements (17.6.3.4), with Key as the function call argument type, the DefaultConstructible requirements (Table 19), the CopyAssignable requirements (Table 23),
  • be swappable (17.6.3.2) for lvalues,
  • provide two nested types result_type and argument_type which shall be synonyms for size_t and Key, respectively,
  • satisfy the requirement that if k1 == k2 is true, h(k1) == h(k2) is also true, where h is an object of type hash and k1 and k2 are objects of type Key.

in 17.6.3.4, this is of most importance (table 26):

Shall not throw exceptions. The value returned shall depend only on the argument k. [ Note: Thus all evaluations of the expression h(k) with the same value for k yield the same result. — end note ] [ Note: For two different values t1 and t2, the probability that h(t1) and h(t2) compare equal should be very small, approaching 1.0 / numeric_- limits::max(). — end note ]

So in general, no, the computation itself is not defined and the result is not required to be consistent over implementations. For that matter, even two different versions of the same library may give different results.

KillianDS
  • 16,936
  • 4
  • 61
  • 70
5

The requirements (17.6.3.4 Hash requirements [hash.requirements]) on the value returned by a Hash function are:

Table 26 — Hash requirements [hash]

The value returned shall depend only on the argument k. [ Note: Thus all evaluations of the expression h(k) with the same value for k yield the same result. —end note ] [ Note: For two different values t1 and t2, the probability that h(t1) and h(t2) compare equal should be very small, approaching 1.0 / numeric_limits<size_t>::max(). —end note ]

In practice, it's quite common that for integral types std::hash(k) would equal k, as that is the simplest possible implementation conformant with the standard. For other types, anything is possible.

ecatmur
  • 152,476
  • 27
  • 293
  • 366