Re: Scheme style auto-resizing hashtable (fwd)

[hjstein@bfr.co.il (Harvey J. Stein)]

Jay Glascoe <jglascoe@jay.giss.nasa.gov> writes:

 > On Wed, 4 Nov 1998 Chris.Bitmead@misys.com.au wrote:
 > 
 > >  > Paper dictionaries do tend to be in alphabetical order, but that is
 > >  > merely an implementation detail. The reason it is in alphabetical
 > >  > order is *not* so you can read all the entries in alphabetical
 > >  > order, but rather to facilitate random access.
 > > 
 > > >True for word -> meaning mapping, but dictionaries can also be used
 > > >for word -> spelling.  If one can at least spell the beginning of the
 > > >word, one looks it up & scans the word until finding the wanted one.
 > > 
 > > But having a dictionary in alphabetical order for spelling correction is
 > > still an implementation detail. And it's a very poor implementation at
 > > that.
 > 
 > so, let's say I have an entry in my dictionary with key "foobar", but I
 > can only remember "foo.." and then my memory gets fuzzy  ;)  I guess a
 > dictionary with ordered entries could give me a list of all keys from
 > "foo" to "fop" to help me find it (in O(log n) time).  neat!

Yes.  O(log n + number_of_matches) to be more precise.

 > But with a dictionary implemented as a hash table I could do a swift
 > "dictionary->key-tree my-dictionary string<?" type thing and then climb
 > the tree, looking for "foo..."'s and whatnot, to my heart's content.

But this'd be O(n*log n)

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il