[boost] Re: [review] hash functions

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2005-03-11 06:40:06

________________________________________________________________________
- What is your evaluation of the design?

There is not much to say about the class boost::hash itself, as there is 
not much to say about functors besides they are common.
On top of that this very functor been fought out by several smart minds.

The extensions to the plain TR1 requirements, hash_range and ADL-based
support of user-defined hashing, are most useful because they are 
important to allow arbitrary data to be hashed (e.g. a std::string may 
be not too well-suited to implement LZW coding for binary data).

I am missing a way to parametrize how hash values are combined.
This is especially desirable because the skeleton could then be
exploited to implement double hashing for compound data (a comon
technique to avoid collisions by varying the hash function) and can be 
useful in other situations (e.g. a small hash table in memory vs. a 
large one on disk).
If we wanted to allow this, however, it is questionable if the proposed 
extensions are optimal, already.

________________________________________________________________________
- What is your evaluation of the documentation?

Good. Easily understandable.

Nitpicking: a hash table is not required to store its elements
in buckets in general - this is a property of the most common way to
implement hash tables.

________________________________________________________________________
- What is your evaluation of the implementation?

Here are my notes from reading the source:

The implementation of hash_combine does not need conditional jumps as a 
probably slightly slower variant, which I've seen quite often does. I 
know this variant works empirically well in practice, so will this one, 
I figure.

However, I believe that hashing speed is generally overrated and that 
there are numerous situations where it's worth to trade some of it for 
fewer collisions (as memory access generally gives more room for 
performance optimization than CPU instructions do).

--
One idea that immediately came to my mind was some "syntactic sugar" to 
ease hashing of class members:
   std::size_t hash_value(point const& p)
   {
     return (boost::hash_value = p.x, p.y, p.z);
   }
Note: It's just a spontanous idea I am not convinced of myself...
--
The for loop in hash_float_value is a nice one to be unrolled via 
metaprogramming.
________________________________________________________________________
- What is your evaluation of the potential usefulness of the library?
Very useful. It's surprising it has been missing in both C++ and Boost
for so long.
________________________________________________________________________
- Did you try to use the library?
Not yet.
________________________________________________________________________
- How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?
Read the documentation and the code. About 2 hours total time.
________________________________________________________________________
- Are you knowledgeable about the problem domain?
Not more than a general-educated and curious programmer should be...
________________________________________________________________________
- Do you think the library should be accepted as a Boost library?
Yes. Though there should be some research if it is possible to add to 
its genericity as mentioned in the first paragraph (just saw the latest 
discussions and seems we're already at it).
Regards,
Tobias