|Masters course with compiler specialization email@example.com (Jeremy Wright) (2002-11-12)|
|Re: Masters course with compiler specialization Trevor.Jenkins@suneidesis.com (2002-12-11)|
|Re: Masters course with compiler specialization firstname.lastname@example.org (2002-12-19)|
|Size of hash tables was Re: Masters course with compiler specializat Trevor.Jenkins@suneidesis.com (2002-12-22)|
|Re: Size of hash tables was Re: Masters course ... email@example.com (Joachim Durchholz) (2002-12-30)|
|Re: Size of hash tables was Re: Masters course ... firstname.lastname@example.org (Matthias Neeracher) (2003-01-04)|
|Re: Size of hash tables was Re: Masters course ... email@example.com (2003-01-04)|
|Re: Size of hash tables was Re: Masters course ... firstname.lastname@example.org (Stephan Eggermont) (2003-01-07)|
|From:||Matthias Neeracher <email@example.com>|
|Date:||4 Jan 2003 22:45:56 -0500|
|Organization:||Integrated Systems Laboratory, ETH, Zurich|
|References:||02-11-060 02-12-056 02-12-092 02-12-107 02-12-127|
|Posted-Date:||04 Jan 2003 22:45:56 EST|
Joachim Durchholz <firstname.lastname@example.org> writes:
> Trevor Jenkins wrote:
>> Since the publication of Maurer's paper "An improved hash code for
>> scatter storage" in the Comm of the ACM (vol 11, Jan 1968, pp 35--38)
>> it is taken as gospel that hash tables only work if the size is a
>> prime number.
> Not "only work". Just "distribute their keys in a more random fashion,
> assuming you don't have a priori knowledge about key distribution".
Agreed up to this point.
> I don't see how this argument has been invalidated. Particularly on modern
> hardware, where division and bit masking have roughly the same execution
> cost. Could anybody clarify?
I disagree about "roughly the same execution cost". On a PowerPC 750
(a.k.a. G3), an integer divide takes 19 cycles (and to get the
remainder, you need to multiply back and subtract, pushing the total
to about 25 cycles), while a logical and takes 1 cycle.
I don't know about other architectures, but I'd be surprised if the situation
were fundamentally different on most of them.
Matthias Neeracher <email@example.com> http://www.iis.ee.ethz.ch/~neeri
Return to the
Search the comp.compilers archives again.