Author: Ricardo Gibert
Date: 15:21:15 05/29/99
Go up one level in this thread
Despite what hyatt implies, 'mapping' is not mutually exclusive of 'hashing'. His definition of hashing is really a better definition of a many to one mapping. Hashing is a key scattering function to distribute keys more evenly. Computer scientists aren't very good at formalizing terminology, since they are of a more practical bent like engineers. Hyatt's error is the same one made by many others e.g. Sedgewick, Horowitz, etc. Knuth & Wirth are better examples of computer scientists that use terminology & definitions more correctly. > Another example is the term "perfect hash function". Not an oxymoron. A hash function is perfect if it does not produce a collision. It is minimal perfect if it does not produce any "gaps" either. Such "hash" functions exist, but usually change with each additional key and are costly to compute. Algorithm's to find such "hash" functions are known that are polynomially bound. Not practical for an application unless the key set is small and for the most part fixed. > What you are looking for are digital search trees (or radix serching), which following Hyatt's "definition", will 'hash' the keys the way you want ;-). This has other drawbacks, however. You may take a look at an article by Bentley in Dr Dobb's on trinary search trees, which is a radix search method. Very interesting. I believe he indicates it to be more efficient than hashing if I remember correctly. Hard to believe. The advantage of hashing is, it is simple and the hash value can be computed "differentially", which I imagine is useful chesswise. > By the way, I don't mean to be too hard on Professor Hyatt. He is an outstanding computer scientist AND individual. The time he spends patiently answering other peoples questions is amazing and commands respect, BUT as professor of computer science, he should be a bit more careful. I hope a little scolding will do some good and he takes this in the spirit intended.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.