Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site loral.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!sdcsvax!sdcc6!loral!ian
From: ian@loral.UUCP (Ian Kaplan)
Newsgroups: net.lang.pascal
Subject: Minimal Perfect Hashing Functions
Message-ID: <684@loral.UUCP>
Date: Mon, 26-Nov-84 22:24:29 EST
Article-I.D.: loral.684
Posted: Mon Nov 26 22:24:29 1984
Date-Received: Wed, 28-Nov-84 02:34:46 EST
Distribution: net
Organization: Loral Instruments, San Diego
Lines: 66


  A little background regarding this posting:

    A month or two ago there was some discussion in this news group
    regarding mimimal perfect hasing functions.  For readers who are not 
    familiar with this arcane topic, a perfect hasing function is a 
    hash function which will always return the item in the hash table (or 
    the fact that it is not there) in one probe.  A minimal perfect hashing 
    function produces a hash table which has no "holes".  In a 
    previous article I posted a list of article references discussing
    minimal perfect hasing functions (MPH).  Send me a note if you would 
    like a copy.

    MPHs are classically of interest to people who work on compilers and
    data bases.  For example it is possible to produce a MPH table for the
    reserved words in Pascal.  Such a table occupies a minimal amount of
    space, and is very fast.  On a Pascal compiler I worked on it noticably
    increased the speed of the compiler.  (The compiler previously used a
    binary tree search).

  One of the most recent articles on MPH algorithms is

    Chang, C. C. "The study of an ordered minimal perfect hashing 
    scheme" in the Comm. of the ACM, V27, 4 (April 1984) 384-387

  I found Mr. Chang's article very difficult and I did not entirely
  understand it.  Mr. Chang reported an algorithm which would construct a
  MPH table without huristic search (which is used by other algorithms).
  This looked really interesting.   Since reading Mr. Chang's article I
  have been hoping to find someone wiser to explain it to me.  Well in this
  months issue of the CACM (Nov. 1984, pgs 1156-1157) there was some
  discussion of Mr. Chang's algorithm.  In response to a letter from Paul
  Pritchard of Cornell University (a wise man), Mr. Chang wrote:

    "Finally, I never claimed that my minimal perfect hashing function is
     practical.  In fact, I have been searching through the literature in
     vain for a practical minimal perfect hashing function.  If someone
     knows of any practical minimal perfect hashing function, I hope
     they'll bring it to my attention."

  So if any of you out there are still trying to figure out this algorith,
  you can now move on to more productive things.  I think that two things
  can be learned from the above paragraph: 
  
  1.  A general MPH function probably does not exist.

  2.  It is amazing what some achademics will publish and what referees 
      will let by.  What was the point of Chang's article?  Why did a "flag
      ship" journal like the CACM publish it?  Perhaps the referees did not
      understand the article either.

  For those of you who have little interst in this arcane topic, I hope
  that you have not read this far.  Since the original discuassion began
  here and there is not an obviously better news group, I submitted it
  here.

			     Ian Kaplan
			     Loral Data Flow Group
			     Loral Instrumentation

			     ucbvax!sdcsvax!sdcc6!loral!ian

			     8401 Aero Dr.
			     San Diego, CA
			     92123
			     (619) 560-5888 x4812