Author: Robert Hyatt
Date: 20:33:06 05/29/99
Go up one level in this thread
On May 29, 1999 at 22:29:15, Ricardo Gibert wrote: >Section 4.6 in Algoritms + Data Structures = Programs by Wirth is correct. >> >The 1983 edition of Algoritms by Sedgewick gives the typical incorrect >exposition of the topic, which you seem to echo rather closely. >> >The 1984 Edition of Fundamentals of Computer Algorithms by Horowitz & Sahni I >have is also incorrect. >> >I'll check Knuth when I pass by the bookstore today. I'm pretty sure he gets it >right. He is very meticulous & comprehensive of course. Not very good at >explanations though. Not a good writer. He seems to set the standard, >nevertheless. I'll probably wind up posting a quote from Wirth even though it >looks like it will be overly long. They don't let you use a copier in bookstores >unfortunately. >> >Just think about what you are saying. "M mod N" would then be hashing a >function according to you. M mod N is most definitely a hashing function. It is a poor one because only the low order bits play a part in the result. But hashing it is. As is the Zobrist approach... as is the approach of summing the characters in a name, and so forth... But as I said, what would be the purpose of mapping an N bit value into an N bit value? It still gets used as an index into a hashed 'thing'. > A poor one, because of all the collisions. Hashing >is a strategy to spread out keys to avoid collisions when you map from M to N. >Mapping function is the term you defined. All B-trees are mapping functions >too, but are not hash functions as you imply. They fit your "definition". B trees have nothing to do with hashing. They don't 'map' anything at all by my definition. ie the idea of 'hash=F(value)' where value is bigger than the result 'hash'. >> >What happens in computer science, as in many fields, is terminology & >definitions are used "loosely". It's is very awkward & laborious to be precise >all the time. Particularly in conversation. The trouble is the listener/reader >does not know when the writer/speaker is being precise or is using the term >loosely. So the facts get "hashed" and you have many books treating topics >incorrectly. I can give many examples in sorting & numerical analysis if you >are interested. I don't see a 'loose definition'. Unless you map from large -> small value, collisions don't make sense. If if you get collisions when mapping from X to X' where the lengths are the same, I fail to see the purpose. In the books I have, typically in data structures, hashing includes a discussion about collisions, chaining, buckets and ways to handle collisions. Collisions only make sense when mapping large things to a small address space. I am used to the idea of a mapping function X'=F(X). And for this mapping function to be called a 'hashing function' then X' < X for all X. usually significantly less than... as in chess board -> 64 bits or 32 bits. >> >By the way, I used to drive my college profs crazy with this type of problem. >So you have my sympathies!
This page took 0 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.