[cfe-dev] RFC: change string hash function in libc++

[Howard Hinnant]

On Dec 3, 2011, at 10:37 PM, Jan Engelhardt wrote:

> 
> On Sunday 2011-12-04 02:17, Howard Hinnant wrote:
> 
>> I've put together the following test function which scores a container at any given time during its lifetime based on the number of collisions it has.  A score of 0.f indicates that all values are hashed into the same bucket.  A score of 100.f indicates that there are no collisions.
>> 
>> //  A quantitative grade [0, 100] of how many collisions there
>> //    are in an unordred_set/map.
>> //    0 == all elements in the same bucket
>> //  100 == no collisions
>> //  A lower max_load_factor pushes this score towards 100
>> //  A higher max_load_factor pushes this score towards 0
>> template <class C>
>> float
>> grade(const C& c)
>> {
>>   using namespace std;
>>   if (c.size() <= 1)
>>       return 100;
>>   float score = 0;
>>   size_t bc = c.bucket_count();
>>   for (size_t i = 0; i != bc; ++i)
>>   {
>>       size_t bs = c.bucket_size(i);
>>       if (bs > 1)
>>           score += bs - 1;
>>   }
>>   return 100*(1 - score / (c.size() - 1));
>> }
>> 
>> I'm not at this time proposing putting this code into libc++ nor even in the
>> test suite. I'm simply requesting comments on if this is a reasonable tool for
>> quantifying the goodness of an unordered container's state.
> 
> Yes, it matches [1]. hmap_agg_index was introduced Aug 19 2009 there.
> 
> [1] http://tinyurl.com/7xsz8jw
>    long: http://libhx.git.sourceforge.net/git/gitweb.cgi?p=libhx/libhx;a=blob;f=src/tc-map.c;hb=HEAD#l340

Proof positive that there are no new ideas.  Just recycled ones. ;-)

Howard