Summary
From Wikipedia: "Hash tables are not persistent data structures, in the sense that there is no simple space-efficient way to update a hash table while retaining access to the previous copy of the hash table.". This is false, and Wikipedia should know why.

Wikipedia and I have a hate-hate relationship. What drives me nuts about it, is the sheer idea that an anarchic shoutocracy (whoever shouts the loudest is right) can be trusted to provide the reader with anything resembling fact. Truthfully, you shouldn't trust anything you read on the internet (including this).

Enough bitching, and now on to something useful. The indexable stack data structure I "invented" recently, actually was already described by a fellow named Phil Hagwell under the rather bizarrely named "VList". Ironically this data structure is described at http://en.wikipedia.org/wiki/VList! Anyway Phil's original paper is here in PDF format. I posted this article at CodeProject.com which briefly explains why this data structure provide constant indexing most of the time.

What is relevant about this structure is that you can use it to create a persistent hash-table, despite the entirely stupid claim in the Wikipedia entry.

Talk Back!

Have an opinion? Readers have already posted 40 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.