storing the hash multiplier instead of the hash value

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Tue Mar 23 11:04:51 PDT 2010


On 03/23/2010 12:08 PM, Fawzi Mohamed wrote:
> On 22-mar-10, at 21:04, Andrei Alexandrescu wrote:
>> Better suggestions are always welcome. For integrals I'm unclear on
>> what we could use to make things better. (Clearly we could and should
>> get rid of the extraneous field.)
>
> I like murmurhash, that I what I put into tango, see
> http://www.dsource.org/projects/tango/browser/trunk/tango/core/rt/compiler/util/hash.d
>
> all that file is based on freely available code and written by me, and I
> give my code with whatever license would be needed.

Thanks, Fawzi, that's great.

I'm trying to collect evidence of MurmurHash's effectiveness versus 
Hsieh's SuperFastHash. I seemed to find some:

http://tanjent.livejournal.com/756623.htmlhttp://tanjent.livejournal.com/756623.html

I also found what seems to be a thorough benchmark:

http://www.strchr.com/hash_functions

Looks pretty solid to me. The benchmarks look only at strings, not at 
typical workloads on void* (e.g. arbitrary objects containing integers 
and pointers and whatnot). Hsieh's hash is smack in the middle, whereas 
Murmur2 is fourth, faster by 10%.

> I think that the public interface should be exposed (or re-exposed)
> somewhere to the outside so that one can easily create efficient hashes
> for user defined types.
> For example it is nice to be able to chain hash functions (something
> that the default one does not allow).

What I'm pushing for as of now is to move the associative array 
definition from opacity into templated goodies in object_.d.


Andrei



More information about the Digitalmars-d mailing list