AMDG On 03/25/2011 06:57 AM, Michael Goldshteyn wrote:

After reading the explanation of how hash_combine should be used, I am left wondering. Why is the recommendation for hash_combine different from what one would intuitively expect?

Either one is okay.

Namely, given:

struct MyStruct { int a; int b; int c; };

The recommendation via examples and documentation is:

size_t hash(const MyStruct &s) { size_t hashValue=0;

// Combine hashes of all elements hash_combine(hashValue,s.a); hash_combine(hashValue,s.b); hash_combine(hashValue,s.c);

return hashValue; }

Rather than what I would think is the expected correct approach:

size_t hash(const MyStruct &s) { // For a composite hash, start by hashing the first element size_t hashValue=hash_value(s.a);

// Then, combine with hashes of the remaining elements hash_combine(hashValue,s.b); hash_combine(hashValue,s.c);

return hashValue; }

In Christ, Steven Watanabe

The thing that bothers me about the use "hash_combine" for even the first hashed value of a bunch of values is the fact that: size_t myHashVal=0; boost::hash_combine(myHashVal,firstVal); ... becomes size_t seed=0; seed ^= hash_value(myFirstHashVal) + 0x9e3779b9; // + (seed << 6) + (seed >> 2) does nothing for seed==0 ... The xor'ing of the first value doesn't bother me, but this displacement by 0x9e3779b9 of the first value does, since for 32-bit size_t values, we've just lost a bunch of info. It seems like the formula will result in less of the first value being applied to the overall hash, due to the "potential" unsigned 32-bit overflow caused by the addition. Maybe I'm misinterpreting the effect. If so, please correct me. Thanks, Michael Goldshteyn

Your method implies a special status to the first element, which it should not have. Of course, because ordering makes a difference the first element is special because it is the first, but the second element is special because it is the second, and so on. Every element should be treated uniformly. Code should always be written, to the extent possible, to reflect concept and intent to the greatest extent possible. Is it really conceptually necessary that any combining algorithm should be just as good if the hash of the initial value can be treated as if it were the combination of a sequence of values? (My own preference would have been for a combiner that was a struct which would be initialized, called on each value to be included and then finalized when the final hash value is extracted -- a more general interface which could be implemented to do precisely what this one does. But I didn't speak up when this was being discussed, so I don't have anything to complain about). Topher On 3/25/2011 9:57 AM, Michael Goldshteyn wrote:

After reading the explanation of how hash_combine should be used, I am left wondering. Why is the recommendation for hash_combine different from what one would intuitively expect?

Namely, given:

struct MyStruct { int a; int b; int c; };

The recommendation via examples and documentation is:

size_t hash(const MyStruct &s) { size_t hashValue=0;

// Combine hashes of all elements hash_combine(hashValue,s.a); hash_combine(hashValue,s.b); hash_combine(hashValue,s.c);

return hashValue; }

Rather than what I would think is the expected correct approach:

size_t hash(const MyStruct &s) { // For a composite hash, start by hashing the first element size_t hashValue=hash_value(s.a);

// Then, combine with hashes of the remaining elements hash_combine(hashValue,s.b); hash_combine(hashValue,s.c);

return hashValue; }

Thanks,

Michael Goldshteyn