Anders Thulin wrote:
Guest wrote:
The only overhead is:

HashIndex = Hash % TableSize;

and later:

All four cases behave the same regardless of table size.

No, there's more to it. You show it yourself when you say:

1) Check one entry.
2) Check two entries.

no further overhead here, true, except that the second may increase
code space, and so cause other kinds of overhead. If it's
implemented as a 1..2 loop, there is obviously counting overhead.

Yes but that's insignificant and independent of table size.

3) Check one hash line, which may contain two or more entries.

and here you have (I presume) a bucket search, which may be more or
less complex depending on how you implement it. I don't see how you
can claim no overhead in this situation.

Because the buckets are of constant size, independent of the size of
the hash table.

4) One small table and one large table.

But why stop there? The table is not static -- you don't only
do searches. You also have to insert new stuff, and weed out old.

Insertion overwrites old data; it's not deleted `manually'. The hash
table is operating as a cache, not a dictionary: if the data you want
isn't in its `primary' location, you look in a constant number of
other places for it and then give up, deleting the stalest or
shallowest data you have and replacing it with the new evaluation.

Now all that adds up: code has to execute to search the table,
code hash to execute to change the table.

Yes but the speed of this code is completely independent of the size
of the hash table.

If the hash table is poorly implemented

.... then you've already lost. Any code might have been badly written
and behave stupidly as a result. Yes, it's possible that the hash
table was written by an idiot but, if it was, the engine will probably
be weak for other reasons, too.

In a well-written engine, the optimal hash table size really is `as
big as you can have it without swapping.'


Dave.

--
David Richerby Disgusting Atlas (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a map of the world but it'll turn
your stomach!