
Re: Persistent HashTables and Why Wikipedia Still Sucks at Computer Scienc

Posted: Nov 25, 2005 6:04 AM


> > I hear you, but I think you're the one proposing > something > > new. Can you give three definitions of a hash table > from > > different sources that describe the same behavior but > > don't appeal to an implementation? > > Nope. > > > I have three data structures/algorithms books on my > shelf. > > The Rivest book, Mark Weiss's, and another. None of > them > > m give a formal definition of a hash table, all give > > examples of implementation and analysis for the those > > particular implementations. > > I am alone in the cold then. I guess some day I should > stop talking about it and actually formalize this stuff in > that book I've always wanted to write. Maybe that way > programmers won't have these kinds of debates anymore.
I'm with Michael on this one (and was about to reply the same, until I saw it had already been said): All the definitions I've seen (including doing a search now), points out that the "hash" in "hash table"/"hash map" comes from it being the name of an implementation method or data structure, that works by applying a mathematical function (a hash function) to the item being searched for, to locate it. A "map", on the other hand, is more general, and for example std::map in C++ is typically implemented as a (red/black) tree, as a hash map would hardly satisfy the complexity requirements (such as the map being sorted).
It's similar to a linked list: You could hardly call a data structure a linked list, if it didn't mean you had nodes linking to the next one. The names describe the data structure, not (just) the operations you may perform with it.
You can, however, say that your type (whatever the data structure is called, such as VList) performs such and such compared to a hash map data structure. The abstract _operation_ is key/value mapping; the _implementation_ may be many things, with varying space/time performance characteristics, all satisfying the requirement, such as arrays (for numerical indexes, only), trees, hash tables, etc.
Regards,
Terje

