Unruh, Erwin wrote:
Hi,
the discussion so far did omit one specific aspect. When comparing two
implementations for a switch, you have to compare the full code. For the hash
you have to include the code to calculate the hash function. This might be more
code than a simple tree lookup.
The example function:
public int hash32shift(int key)
{
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >>> 12);
key = key + (key << 2);
key = key ^ (key >>> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >>> 16);
return key;
}
has 12 operations. Add a table and verification you get to about 18. That is
worse than a tree search with 9 levels. So for all switches with less than 512
elements, the hash is not faster.
You can't just count operations on modern machines, so this conclusion
is not valid, yes, of course the code for computing the hash has to be
taken into account, but nothing else than actual benchmarks will give
an accurate comparison.
Erwin
