Perfect HASH functions.....

[Jeffrey Kegler]

In article <9900014 at bradley> vijay at 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 at algor2.ALGORISTS.COM or uunet!algor2!jeffrey
1762 Wainwright DR, Reston VA 22090