Default hashing function for AA's

Steven Schveighoffer schveiguy at yahoo.com
Tue Oct 10 15:22:05 UTC 2017


On 10/9/17 10:11 AM, RazvanN wrote:
> Hi all,
> 
> We in the UPB dlang group have been having discussions about the hashing 
> functions of associative arrays. In particular, we were wondering why is 
> the AA implementation in druntime is not using the hash function 
> implemented in druntime/src/core/internal/hash.hashOf for classes that 
> don't define toHash().

AA uses typeid(Key).getHash. [1]

For objects, this calls the virtual function `toHash`. [2]

Please keep in mind that all you are hashing is the class reference 
pointer, as that is the default comparison for `opEquals`. It might make 
sense to shuffle those bits a bit, since the bucket algorithm only looks 
at the lower bits of the hash, and this basically guarantees keys with 
the default hash will be empty in the first few buckets, since class 
objects are aligned on a power-of-2 boundary.

But I'm not sure running a full blown hash on the pointer is necessary. 
Perhaps just xor-ing the upper bits with the lower bits makes more sense.

Alternatively, you could change the default `opEquals` but that may 
break things more than expected.

What you *can't* do is change what the hash is based on without changing 
`opEquals`.

Note that I wouldn't recommend using an Object as a key without defining 
toHash and opEquals anyway.

-Steve

[1] https://github.com/dlang/druntime/blob/master/src/rt/aaA.d#L310
[2] https://github.com/dlang/druntime/blob/master/src/object.d#L66


More information about the Digitalmars-d mailing list