Author: Robert Hyatt
Date: 15:23:24 05/31/99
Go up one level in this thread
On May 30, 1999 at 11:59:17, Ricardo Gibert wrote: >Oops! I forgot to include a couple of points. Sorry. Since, you haven't >answered my prevoius post yet, you are technically still left with the last >word. >> >As you 'should' well know some hash tables are variable in size and in such >cases it is silly to limit them with a many-to-one mapping in such cases, M=N >and even M<N is possible. >> possible != sensible, however. >The fundamentally, the error you are making is the scattering out of keys is in >and of itself a desirable property, distinct from a one-to-many mapping. For >example, just this property is used in skip lists. Hashing there is a way of >using probability to keep the tree balanced. Many-to-one business is irrelevant >there. No.. that is an argument you are making up. If the size of the indexed table is larger than the key being used to access it, distributing the data better has _no_ useful effect at all. It hurts performance (cache issue) and since you have more memory than stuff to put in it, who cares where it goes? In hashing there is typically no "tree". Which is the _point_ of hashing in the first place... that idea of transforming a long identifier into a short index for direct access of an entry. Every text I own mentions hashing and collisions together (along with solutions like chaining, buckets, rehashing, etc.) In any sort of tree that doesn't make a lot of sense... And that will also be my last word on the subject. Anyone interested in this can find Knuth's books easily in any university library, or any good book on data structures at the same place. >> >OK that's all folks. I mean it this time
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.