在我正在开发的一个程序中，我开发了一个大型的“线程树”（每个节点最多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);
}
请注意，insert 例程返回一个新树，这似乎效率低下，但它只会更改它所遍历的那些节点。这是平均O（lg n），所以它平均进行O（lg n）分配。这与它所获得的一样节省空间。
要获得最坏情况的 O（lg n） 行为，请使用红黑树。另请参阅有关函数式编程中数据结构的文献，例如Okasaki的作品。
有没有办法实现至少O（log n）查找，插入和删除的键值对，该匹配是完全持久的，但与普通哈希表一样“节省空间”（最坏的情况）？
确实有。多种方式。
例如，在Haskell中，简单的Data.Map，一个大小平衡的二叉树（或有界平衡树），如下所述：
提供以下 API，满足您的条件：
insert :: Ord k => k -> a -> Map k a -> Map k a -- O(log n)
lookup :: Ord k => k -> Map k a -> Maybe a -- O(log n)
delete :: Ord k => k -> Map k a -> Map k a -- O(log n)
同时完全坚持。空间使用量为 O（n）。
为了获得更好的常数因子，请尝试例如具有相同整体复杂性的Data.HashMap数据结构。
替代结构包括：
