Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[REBOL] Re: Sort by first part of line

From: joel:neely:fedex at: 5-Sep-2002 17:18

Hi, Gregg and all... Having a furiously busy week... not much time to keep up with the list, I'm afraid! :-( Gregg Irwin wrote:
> ... rather than doing comparisons of items in a linear or tree > structure, you generate a location from the item/key and that's > where the items lives. To find an item, you just go to the > location returned by your "hash function" for that item. > > Since you'll rarely get a totally unique set of results, the > hashing process also has to handle "collisions", where two keys > generate the same result when hashed. >
Good summary! I might only add that one can think of a hashed structure as a collection of "buckets", where the keying function tells which bucket to look in, and should uniformly distribute the items across all buckets (usually in a pseudo-random fashion). There's a whole art devoted to constructing "perfect hash functions" for specific sets of values (e.g. the key words in a programming language), but perfection normally breaks when more key values are added to the set.
> <<..., and could hash be used to speed up sort? >> >
No. Because hashing essentially randomizes the keys across the collection of buckets, the keys that end up in the same bucket normally don't have a nice relationship vis-a-vis some obvious sort order. -jn-