Re: Size of hash tables was Re: Masters course ...

Stephan Eggermont <stephan@stack.nl>
7 Jan 2003 23:30:45 -0500

          From comp.compilers
Related articles
Masters course with compiler specialization jeremy.wright@microfocus.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 etechweb@yahoo.com (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 ... joachim_d@gmx.de (Joachim Durchholz) (2002-12-30)
Re: Size of hash tables was Re: Masters course ... neeri@iis.ee.ethz.ch (Matthias Neeracher) (2003-01-04)
Re: Size of hash tables was Re: Masters course ... bonzini@gnu.org (2003-01-04)
Re: Size of hash tables was Re: Masters course ... stephan@stack.nl (Stephan Eggermont) (2003-01-07)
| List of all articles for this month |
From: Stephan Eggermont <stephan@stack.nl>
Newsgroups: comp.compilers
Date: 7 Jan 2003 23:30:45 -0500
Organization: Eindhoven University of Technology, The Netherlands
References: 02-11-060 02-12-056 02-12-092 02-12-107 02-12-127
Keywords: symbols, theory
Posted-Date: 07 Jan 2003 23:30:45 EST

Joachim Durchholz <joachim_d@gmx.de> wrote:
> 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". 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?


They only have roughly the same execution cost for 1-bit numbers.
For 32-bit or 128-bit (OIDs) the difference is large.


Stephan

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.