持久哈希表实现

Question

在我正在开发的程序中,我开发了一个大的"线程树"(每个节点最多k个子节点),其中每个线程对从其父节点继承的哈希表进行一些修改.有没有办法实现一个有点"持久"的哈希表(在http://en.wikipedia.org/wiki/Persistent_data_structure意义上)？

也就是说,有没有办法实现一个键值配对,至少O(log n)查找,插入和删除是完全持久的,但是像普通哈希一样"节省空间"(最坏情况) - 表？

Answer 1

"作为普通哈希表的空间效率"是一个相当模糊的规范,因为"普通"可能意味着链接或探测取决于你问谁.我认为还没有人设计易于理解的持久性哈希表.

获得具有所需复杂性的持久键值映射的最简单方法是使用持久二进制搜索树.Lookup是来自短暂(非持久)BST的熟悉算法.但是插入更改,变成类似(伪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);
}

请注意,insert例程返回一个新树,这可能看起来效率低下,但它只会更改它遍历的那些节点.这平均为O(lg n),因此它平均进行O(lg n)分配.这就像它获得的空间效率一样.

要获得最坏情况的O(lg n)行为,请使用红黑树.另请参阅函数式编程中的数据结构文献,例如Okasaki的作品.