Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!algor2.algorists.com!jeffrey
From: jeffrey@algor2.algorists.com (Jeffrey Kegler)
Newsgroups: comp.lang.c
Subject: Re: Perfect HASH functions.....
Message-ID: <1989Sep21.025732.12047@algor2.algorists.com>
Date: 21 Sep 89 02:57:32 GMT
References: <9900014@bradley>
Reply-To: jeffrey@algor2.UUCP (Jeffrey Kegler)
Organization: Algorists, Inc.
Lines: 29

In article <9900014@bradley> vijay@bradley.UUCP writes: 

>Does anyone out there have a perfect hash function? The key is a
>string of characters (maximum length is 4, minimum is 2) that make up
>the opcode set of an assembler that I am in the process of writing.
>I also tried to read some articles on the subject in ACM, but you
>need a PHD in maths to make any sense out of them!!

I wrote one of those articles (_Communications of the ACM_, June
1986), so maybe I can help.  Perfect hashing is almost never
practical.  For any number of keys, some type of faster and better
method can be devised.  [ The secret to this is realizing perfect hashes
do not run in constant time. ]  In your case a binary search looks
like a winner.

If you do come up with a perfect hash of your opcodes, and code it up,
what happens when an opcode is added (or deleted)?  You need a new
perfect hash.  It certainly makes the job of maintaining the assembler
interesting.

Another interesting approach for the opcode search is a
self-organizing search, which will take advantage of the fact the some
of the opcodes are used far more often than others.

-- 

Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc.
jeffrey@algor2.ALGORISTS.COM or uunet!algor2!jeffrey
1762 Wainwright DR, Reston VA 22090