Re: Switch statement code generation

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

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