This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
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