6 Apr 1996 22:14:35 -0500

Related articles |
---|

Is Minimal Perfect Hashing the wrong algorithm? cef@geodesic.com (Charles Fiterman) (1996-04-02) |

Re: Is Minimal Perfect Hashing the wrong algorithm? fjh@cs.mu.OZ.AU (1996-04-04) |

Re: Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-06) |

Re: Is Minimal Perfect Hashing the wrong algorithm? krotoff@boy.nmd.msu.ru (Alexander Krotoff) (1996-04-07) |

Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-08) |

Re: Is Minimal Perfect Hashing the wrong algorithm? dave@occl-cam.demon.co.uk (Dave Lloyd) (1996-04-08) |

Re: Is Minimal Perfect Hashing the wrong algorithm? yuen@elec.uq.oz.au (1996-04-10) |

Re: Is Minimal Perfect Hashing the wrong algorithm? det@platsol.com (Dave Toland) (1996-04-11) |

From: | preston@tera.com (Preston Briggs) |

Newsgroups: | comp.compilers |

Date: | 6 Apr 1996 22:14:35 -0500 |

Organization: | /etc/organization |

References: | 96-04-012 |

Keywords: | theory |

Charles Fiterman <cef@geodesic.com> writes:

*>Many compiler writers use Minimal Perfect Hashing to generate some*

*>hash tables such as a key word table.*

*>But this algorithm minimizes table size. Shouldn't it minimize lookup*

*>time with a cap on table size?*

I think it's even worse than you suggest. Given some unknown

alphabetic token, we first look in this minimal table to see if it's a

keyword. If it isn't, we assume it's an identifier. Since the

minimal table is dense, every identifier will collide with some

keyword and we'll have to do a string compare to resolve the question

of "keyword or id?"

If I hashed keywords, I'd make the table very sparse. Then most

identifiers would hash to an empty location and no string compare

would be required.

The cost in space would be pretty minimal. Imagine a language with 50

keywords. If the hash table is an array of 4-byte pointers to

strings, then a 1 Kbyte table would get the density down to 20%.

Preston Briggs

[I just stick the keywords in the symbol table so with one probe I've got

whatever it is. I thought that was what everyone did. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.