Hash tables using VLists

Question

Phil Bagwell, in his 2002 paper on the VList data structure, indicates that you can use a VList to implement a persistent hash table. However, his explanation of how that worked didn't include much detail, and I don't understand it. Can anybody give me a more detailed explanation, or even examples?

Further, it appears to me from what I can see that this data structure, while it may have the same big-O complexity as a Hashtable, will be slower because it does additional lookups. Does anybody care to do a detailed analysis of just how much slower, preferably including cache behaviour? How does the performance relationship between the two change in the case of having no collisions or many?

Answer 1

I had a look at this paper, and it appears very preliminary. The fact that no later version has been published, and that the original appeared in IFL (which is a work-in-progress sort of meeting), suggests that you may be wasting your time.

Answer 2

Hrmm there seem to be a number of issues with the data structures proposed by the paper in question.

Off the cuff, the naive vlists mentioned first seem to need unique references in order to get anything near the time guarantees proposed. You lose the ability for the most part to share tails. You can share the tiny nodes towards the back of the list, but you wind up having to duplicate the largest vlist node the moment you cons something onto the cdr of vlist that is still active. That cost is proportional to the cost of copying the whole list.

With the 2d modifications mentioned later it becomes constant again, but its a pretty large constant, since you wind up at least copying the head of a list of pages (or worse, a vlist) and the first page in your list.

The functional hash list stuff in there didn't seem to make much sense to me to be honest. It was just a brief blurb that seemed to be bolted onto an otherwise unrelated paper, without enough detail to really make out how practical it is.