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

[Jan Engelhardt]

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