Performance of hashes and associative arrays

["Raphaël]

Hello everybody,

we had a conversation with Ali Cehreli about the right ways of 
hashing values / objects. This is related to the D language when 
using associative arrays but applies for any language as well.

One of the points was, we have the following class:

==
class Student // class representing a student
{
     string firstName; // the first name of the student
     string lastName; // the last name of the student
}
==

Let s be a Student:

==
auto s = new Student("Jean", "Martin");
==

We want to be able to get the hash of s. Therefore, we 
re-implement the toHash method of the Student class :

==
class Student
{
     string firstName;
     string lastName;

     override size_t toHash() const
     {
         //...
     }
}
==

The original solution proposed was:

==
     override size_t toHash() const
     {
         return (typeid(firstName).getHash(&firstName) +
                 typeid(lastName).getHash(&lastName));
     }
==

However, with this solution, we get the same hash for new 
Student("Jean", "Martin") and new Student("Martin", "Jean"). We 
did an experiment of performance of associative arrays in D when 
the hash function is not well designed (returning the same hash 
for too many values). When the hash function returns the same 
hash for too many values, performance are dramatic (See the end 
of the post for more information).

So here is the second solution that was proposed and that avoids 
having the same hash for two different names:

==
     override size_t toHash() const
     {
         auto h = firstName ~ ":" ~ lastName; // we suppose that 
":" is not a valid character in a name
         return typeid(h).getHash(&h);
     }
==

A ":" was added so new Student("Martin", "Jean") gets a different 
hash than new Student("Mar", "tinJean")).
Let's call the following solution "second bis solution" :

==
     override size_t toHash() const
     {
         auto h = firstName ~ lastName;
         return typeid(h).getHash(&h);
     }
==

This solution suppose that being named Mar tinJean instead of 
Martin Jean is really strange and therefore quite unusual.
However, these two solutions imply string concatenations each 
time we need the hash.
Ali agreed that concatenating strings each time would indeed be 
inefficient. He thought we might cache the value (third solution) 
:

==
class Student
{
     string firstName;
     string lastName;
     size_t cachedHash;

     override size_t toHash() const
     {
         if(cachedHash is null)
         {
             auto h = firstName ~ ":" ~ lastName;
             cachedHash = typeid(h).getHash(&h);
         }
         return cachedHash;
     }
}
==

This solution doesn't make compromise on the "quality" of the 
hash and is fast after the first usage but needs to keep the hash 
as part of the class. The hash is calculated for each new object 
that is used as index in an associative array, even if the hash 
for this specific name has already been calculated in another 
object.

Questions are :
  - what is the most efficient solution, and in which case ?
  - Is it preferable to try to make the hash unique (second bis 
solution), or to try to make the hash easier to evaluate and risk 
in rare case to get the same hashes for two different objects 
(second solution)?
  - Is solution 3 a good practice? Preferable to the others 
solutions? When?
  - Is solution 1 preferable to the others solutions, given that 
first name / last name inversions are quite "rare" ?
  - how compares solution 1 to solution 2 bis ?

It would also be interesting to have ideas for the general case, 
i.e. random objects and not just names that have particularities 
like "First names are not often last names and vice versa", or 
for other specific situations.
Questions are oriented for usage in associative arrays in D, but 
still apply to other use cases of hashes.


For those who are interested, here is Ali's experiment on 
performance of associative arrays in D depending on the design of 
the hash function (I took the liberty to modify it slightly).

==
import std.stdio;
import std.random;
import std.string;

class Clock
{
     int hour;
     int minute;
     int second;

     static size_t opCmpCount = 0;
     static size_t opEqualsCount = 0;
     static size_t toHashCount = 0;

     override equals_t opEquals(Object o) const
     {
         ++opEqualsCount;

         auto rhs = cast(const Clock)o;

         return (rhs &&
                 (hour == rhs.hour) &&
                 (minute == rhs.minute) &&
                 (second == rhs.second));
     }

     override int opCmp(Object o) const
     {
         ++opCmpCount;

         /* Taking advantage of the automatically-maintained
          * order of the types. */
         if (typeid(this) != typeid(o)) {
             return typeid(this).opCmp(typeid(o));
         }

         auto rhs = cast(const Clock)o;
         /* No need to check whether rhs is null, because it is
          * known on this line that it has the same type as o. */

         return (hour != rhs.hour
                 ? hour - rhs.hour
                 : (minute != rhs.minute
                    ? minute - rhs.minute
                    : second - rhs.second));
     }

     override string toString() const
     {
         return format("%02s:%02s:%02s", hour, minute, second);
     }

     this(int hour, int minute, int second)
     {
         this.hour = hour;
         this.minute = minute;
         this.second = second;
     }

     override hash_t toHash() const
     {
         ++toHashCount;
         return hour + minute + second; // method 1
         // return hour + 60 * minute + 3600 * second; // method 2
     }

     static void printCounts()
     {
         writefln("opEquals: %8s", opEqualsCount);
         writefln("opCmp   : %8s", opCmpCount);
         writefln("toHash  : %8s", toHashCount);
     }
}

Clock randomClock()
{
     return new Clock(uniform(0, 24), uniform(0, 60), uniform(0, 
60));
}

void main()
{
     enum count = 10_000;
     Clock[Clock] aa;

     foreach (i; 0 .. count) {
         auto entry = randomClock();
         aa[entry] = entry;
     }

     foreach (i; 0 .. count) {
         auto result = (randomClock() in aa);
     }

     Clock.printCounts();
}
==

We both get the following results for the method 1:

opEquals:        0
opCmp   :  1438438
toHash  :    20000


and the following results for the method 2:

opEquals:        0
opCmp   :     1681
toHash  :    20000

Apart from the fact associative arrays in gdc and dmd don't use 
the opEquals method, we see that using method 1 implies approx. 
856 times more comparisons than method 2. I calculated that 
method 1 gives 139 different hashes for 80063 different elements, 
which means each hash represents an average of approx. 576 
elements. Method 2 gives exactly one hash for one element.
This seems to be an extreme case, we might think results would be 
completely different from a function giving hashes that 
"sometimes" represents 2 elements.