Re: Switch statement code generation

Hans Aberg <haberg_20080406@math.su.se>
Tue, 17 Nov 2009 10:16:59 +0100

          From comp.compilers

Related articles
[13 earlier articles]
Re: Switch statement code generation DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-11-11)
Re: Switch statement code generation derek@knosof.co.uk (Derek M. Jones) (2009-11-11)
Re: Switch statement code generation anton@mips.complang.tuwien.ac.at (2009-11-11)
Re: Switch statement code generation idbaxter@semdesigns.com (Ira Baxter) (2009-11-14)
Re: Switch statement code generation cfc@shell01.TheWorld.com (Chris F Clark) (2009-11-15)
Re: Switch statement code generation pertti.kellomaki@tut.fi (Pertti Kellomaki) (2009-11-16)
Re: Switch statement code generation haberg_20080406@math.su.se (Hans Aberg) (2009-11-17)
| List of all articles for this month |

From: Hans Aberg <haberg_20080406@math.su.se>
Newsgroups: comp.compilers
Date: Tue, 17 Nov 2009 10:16:59 +0100
Organization: A noiseless patient Spider
References: 09-11-046 09-11-051
Keywords: code
Posted-Date: 17 Nov 2009 11:26:11 EST

Pertti Kellomaki wrote:
>> [I gather that finding a perfect hash function that runs quickly is
>> not always easy, and that a slightly imperfect hash, e.g., into a
>> hash table with no collisions but a few empty slots can often be
>> a lot faster. -John]
>
> Is there a technical term for such slightly imperfect hashes?
> Mathematically it would be an injection I suppose, but I have
> not seen that term used in connection with hashing.


The Wikipedia perfect hash function page says this is the definition of
a perfect hash function. It is called a minimal perfect function if the
image is an interval.


It also mentions some libraries implementing minimal perfect hash functions:
      http://cmph.sourceforge.net/
      http://sux4j.dsi.unimi.it/
The latter also implements monotone minimal perfect hash functions, that
is, the order of the keys are preserved.


      Hans



Post a followup to this message

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