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.

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.

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.
In the single entry case, it's easy, but in the bucket hash it
tends to get hairy: a fast search usually means a slow insert.


Now all that adds up: code has to execute to search the table,
code hash to execute to change the table. As long as that code
executes faster than the code the hash replaces, all is fine. But
does it? If the hash table is poorly implemented, you may turn
out to have a bucket hash with linear searches of the buckets,
and one that resizes by increasing bucket chain length only.
I've seen those in actual use -- and turned out by professional
programmers, too.

It doesn't matter one whit what theory says, if the programmer
didn't do a good job implementing it.

In this particular case, we don't have a single clue to what code
base the question applies to. I assume it applies to code base,
of course -- if the question is purely theoretical, one of the
standard books on search algorithms will probably be the best source for
a reply.

--
Anders Thulin anders*thulin.name http://www.anders.thulin.name/