Re: % in hash table

Article View: comp.arch

Article #12602

#12602

From: James Davenport
Date: Wed, 04 Oct 1995 10:13

19 lines
1422 bytes

In the referenced article, haertel@ichips.intel.com (Mike Haertel) writes:
>In article <jgkDFv094.JKJ@netcom.com>, Joe Keane  <jgk@netcom.com> wrote:
>People who do hashing usually like primes.  There are some primes of the
>form 2^n +- 1; remainders modulo such primes still do not require the full
>force of a fully general remainder routine.  Most compilers I've seen do not
>optimize this case, but they could--it's only a couple extra shifts and
>adds over mod 2^n.
>--
The point about compilers often not noticing "near misses" of powers of
2 is extremely valid.
But there's much less need to use primes than many people think:
there is a reluctance to do trivial number theory and a mystical
belief in the power of prime numbers. For a case where primes
are not actually needed, see
Hopgood,F.R.A. & Davenport,J.H.,
The Quadratic Hash Method when the table size is a power of 2.
Computer Journal 15(1973) pp 314-5.

James Davenport - jhd@maths.bath.ac.uk

Technical Details

Message-ID: <DFx5r6.A7@bath.ac.uk>

Path: arc1-ca.pugleaf.net!bath.ac.uk!masjhd

References: <43tqr6$3au@mikasa.iol.it> <DFLzD9.Anx@uns.bris.ac.uk> <jgkDFv094.JKJ@netcom.com> <44sjp4$c71@news.jf.intel.com>

Show Full Headers

Complete Article Headers

Newsgroups: comp.arch,comp.arch.arithmetic,comp.lang.c
Path: arc1-ca.pugleaf.net!bath.ac.uk!masjhd
From: masjhd@bath.ac.uk (James Davenport)
Subject: Re: % in hash table
Message-ID: <DFx5r6.A7@bath.ac.uk>
Keywords: hash
Organization: School of Mathematical Sciences, University of Bath, UK
References: <43tqr6$3au@mikasa.iol.it> <DFLzD9.Anx@uns.bris.ac.uk> <jgkDFv094.JKJ@netcom.com> <44sjp4$c71@news.jf.intel.com>
Date: Wed, 4 Oct 1995 10:13:53 GMT

Reply to Parent Message