在我正在研究的程序中，我开发了一个大的“线程树”(每个节点最多k个子节点)，其中每个线程都对从其父级继承的哈希表进行了一些修改。有没有一种方法可以实现某种“持久”(就http://en.wikipedia.org/wiki/Persistent_data_structure而言)的哈希表？
也就是说，有一种方法可以实现具有至少O(log n)查找，插入和删除的键-值配对，该键-值配对是完全持久的，但与普通哈希一样“节省空间”(最坏的情况)表？
最佳答案
“像普通散列表一样节省空间”是一个相当模糊的规范，因为“普通”可能意味着链接或探查，具体取决于您询问的人。我认为还没有人设计出易于理解的持久性哈希表。
获得具有所需复杂性的持久键值映射的最简单方法是使用持久二进制搜索树。查找是短暂(非持久)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);
}
请注意，插入例程会返回一棵新树，该树似乎效率低下，但它只会更改它遍历的那些节点。这平均为O(lg n)，因此平均分配O(lg n)。这几乎与节省空间有关。
要获得最坏情况下的O(lg n)行为，请使用一棵红黑树。另请参见有关函数式编程中数据结构的文献，例如冈崎的作品。
关于java - 持久哈希表实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4860493/