[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-
