Re: Scheme style auto-resizing hashtable (fwd)

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> On Fri, 6 Nov 1998, Maciej Stachowiak wrote:
> 
> > 
> > jglascoe@jay.giss.nasa.gov writes:
> > > 
> > > so what do I have here?  "dictionary" and "meaningful identifiers". hmm.
> > > I also considered using "hash-table" (used by CL, so I just said "No."),
> > > "assoc-array" (one letter longer than "dictionary", you lose), and even
> > > "auto-hash" (where did that come from?).
> > > 
> > 
> > A dictionary could be implemented as a hash table, an association list,
> > a procedure, a red-black tree, an AVL tree, a B-Tree, an ordered
> > association list, etc. To reserve the name `dictionary' for the
> > hashtable implementation seems arrogant to me. 
> > 
> 
> the great Larry Wall wrote that the three virtues of a programmer are
> hubris, laziness, and impatience.  I believe all Schemers on this mailing
> list are guilty on all three counts (some more guilty than others,
> perhaps).
> 

I certainly hope so :-)

> I say this: the whole dictionary => ordered entries concept is more than a
> little tenuous.  If, at sometime in the future, somebody writes a
> collection type data structure with ordered elements, then I propose they
> name the type either "ordered-collection" or "telephone-book"!
> 

Note that my objection had nothing to do with the ordering (I
personally don't think "dictionary" implies an ordering). It had to do
with the fact that "dictionary" is typically the generic name for any
data structure that maps keys to values, since it is possible to
implement this in a number of ways in Scheme, and many of the
implementations are useful, it is inappropriate and misleading to name
_one_ of those data structures "dictionary". Since it is, in fact, a
hash table, and hash tables have a useful property that programers are
interested in (constant-time access) that other dictionary data
structures do not have, then it seems that a name reflecting its
hash-table nature would be best.


> > I'll comment on the latest revision of your suggested API in a later
> > message.
> > 
> >  - Maciej
> > 
> 
> as always, thanks for your input Maciej.
> 

You're welcome, but I really need to start talking less and coding
more :-)

> BTW, how about simply "table"?  that's what Dylan calls its hash tables.

I think the "hash" should be there to emphasize the "insert, delete
and lookup in amortized average-case constant time" property as
opposed to other dictionary-capable data structures.

 - Maciej