Persistent Hash Table Implementation

Question

In a program I'm working on, I develop a large "thread tree" (at most k children per node), where each thread makes some modifications to a hash table inherited from its parent. Is there a way to implement a hash table that is somewhat "persistent" (in the sense of http://en.wikipedia.org/wiki/Persistent_data_structure) ?

Namely, is there a way to implement a key-value pairing with at least O(log n) lookup, insertion, and deletion that is fully persistent, but is as "space-efficient" (worst-case) as an ordinary hash-table?

Answer 1

"As space-efficient as an ordinary hash-table" is a rather vague specification, since "ordinary" may mean linked or probed depending on who you ask. I don't think anyone has designed easy-to-understand persistent hash tables yet.

The easiest way to get a persistent key-value map with the complexity that you want is to use a persistent binary search tree. Lookup is the familiar algorithm from ephemeral (non-persistent) BSTs. Insert changes however, and becomes something like (pseudo-Java):

// overwrites the value for k if it's already in the tree
Node insert(Node node, Key k, Value v)
{
    if (k < node.key)
        return new Node(node.key, node.val, insert(node.left, k, v), node.right);
    else if (k > node.key)
        return new Node(node.key, node.val, node.left, insert(node.right, k, v));
    else
        return new Node(k, v, node.left, node.right);
}

Note that the insert routine returns a new tree, which may seem inefficient, but it only changes those nodes it traverses. This is on average O(lg n), so it does O(lg n) allocations on average. This is about as space-efficient as it gets.

To get worst-case O(lg n) behavior, use a red-black tree. See also the literature on data structures in functional programming, e.g. the works of Okasaki.