Thanks for the fast reply,
On Fri, Mar 19, 2010 at 3:07 PM, Robert Dewar <de...@adacore.com> wrote:
>> "In many situations, hash tables turn out to be more efficient than
>> search trees or any other table lookup structure."
>
> The above quote from Wikipedia is indeed misleading because it does
> not make a clearer contrast between average behavior and worst case
> behavior (the situation is similar to comparing quick sort with heap
> sort, they are both NlogN on average, but the constant is smaller
> for quick sort, so it is generally better, but the worst case is
> N**2 for quick sort and NlogN for heap sort.
>
> So this does not get around the possibility of a bad luck worst case.
> It is one thing for a program to compiler slowly because by bad luck
> it has identifier names that hash badly, it is QUITE another to hit
> bad luck at execution time which results in a particular program
> running horribly slow. I am dubious about introducing this kind of
> uncertainty.
I am not interested in making compile time shorter.
I am here talking about the speed at run-time not at compile-time.
I have already mentioned it earlier.
I assume that by "hash badly" you mean a hash function generates an
identical result even from different key values.
For the hash table as alternative way of switch statement, it does not
have "hash badly" situation at run-time.
It is because the hash table I'm talking about is a perfect hash table.
Let's say we adopt this hash function.
It is also from the same web site.
public int hash32shiftmult(int key, int c2=0x27d4eb2d )
{
key = (key ^ 61) ^ (key >>> 16);
key = key + (key << 3);
key = key ^ (key >>> 4);
key = key * c2;
key = key ^ (key >>> 15);
return key;
}
Now we have a switch statement that has 400 cases or whatever.
switch ( valueFormUser )
{
case 0: do1(); break;
case 1: do2(); break;
case 2: do3(); break;
...
case 399: do399(); break;
default: break;
}
In the case the conflict happened, we change the value of "c2" until
none of values of cases conflict.
In other words, we change c2 value until we get "hash32shiftmult( 0,
c2 ) != hash32shiftmult( 1, c2 ) != hash32shiftmult( 2, c2 )...."
Therefore we will have "Perfect hash table", so that there is no
conflict during run-time.
In other words, we will have fixed constant cost for hash table
resolving; there is no 'hash badly" case.
In fact, it will make compile time longer, if it is your interest.
But again, I am talking about run-time speed.
> A quote from this article:
>
>> " ... the switch very efficiently, even constructing a hash table if this
>> method of switching is ..."
Yes, it does. Such a old paper mentioned it and we are still not doing it.
So it makes me wonder why.
Thanks
Jay
