Re: Scheme style auto-resizing hashtable (fwd)

[Dirk Herrmann <dirk@ida.ing.tu-bs.de>]

On 4 Nov 1998, Bruce Stephens wrote:

> Jay Glascoe <jglascoe@jay.giss.nasa.gov> writes:
> 
> > Okay, I'm still open minded.  If everyone wants "hash-table", then
> > I'll go with "hash-table".  But I still plan on consulting some
> > other languages to see (a) what they call their hash tables, and (b)
> > whether any of them actually have a data structure named
> > "dictionary" that orders its entries.
> 
> What's wrong with "map"?  I know the STL version has various
> properties which imply ordering, but that doesn't mean a scheme
> version needs to.  (I was surprised to find that the STL map has
> ordering; it feels overconstrained to me.  Iterators are fine, but I'd
> expect them to traverse the keys in arbitrary order.)  

Maybe I should state my point more clearly. A hash-table is a
reasonably well understood concept in computer science. If your library
provides you a hash-table, the basic assumption is that you can insert,
delete and access items in O(1), but that ordered access to elements is
not automatically provided (you would have to sort the elements by
yourself).

On the other hand, maps and dictionaries can be implemented in several
ways. It is possible to use a hash-table to implement a map, but you could
also use a tree, an alist and several other data structures. The
consequence is, that without additional information you don't know about
the performance a map provides to you. 

If your code _depends_ on the fact, that access times of O(1) are
provided, you rather explicitly use a hash-table. The first reason is,
that you by doing this have automatically put some documentation into the
code that warns other people of time critical parts (self documenting
code). The second reason is, that if you use a map or a dictionary, there
is nothing granting the implementation as a hash-table. If guile chooses
hash-tables to implement a dictionary datatype, other schemes may choose
differently.

Summarized: 

* Only by writing 'hash-table' you are guaranteed to get a hash-table. *

Sorry for repeating myself.
Dirk Herrmann