16

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

也就是说，有没有一种方法可以实现一个键值对，它至少具有 O(log n) 的查找、插入和删除，它是完全持久的，但与普通哈希一样“节省空间”（最坏情况）-桌子？

4

4 回答 4

5

“与普通哈希表一样节省空间”是一个相当模糊的规范，因为“普通”可能意味着链接或探测，具体取决于您询问的对象。我认为还没有人设计出易于理解的持久哈希表。

获得具有所需复杂性的持久键值映射的最简单方法是使用持久二叉搜索树。查找是来自短暂（非持久）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 ) 行为，请使用红黑树。另请参阅有关函数式编程中数据结构的文献，例如 Okasaki 的作品。

于 2011-02-01T11:19:12.273 回答
2

有没有办法实现一个键值对，至少 O(log n) 查找、插入和删除是完全持久的，但与普通哈希表一样“节省空间”（最坏情况）？

确实有。很多种方法。

例如，在 Haskell 中，简单Data.Map的、大小平衡的二叉树（或有界平衡树）如下所述：

  • Stephen Adams，“高效集合：平衡行为”，函数式编程杂志 3(4):553-562，1993 年 10 月，http ://www.swiss.ai.mit.edu/~adams/BB/ 。
  • J. Nievergelt 和 EM Reingold，“有界平衡的二叉搜索树”，SIAM 计算杂志 2(1)，1973 年 3 月。

提供以下 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具有相同整体复杂性的数据结构。

替代结构包括：

  • 持久性尝试，它提高了哈希表的空间使用率，因为密钥存储是密集的。
于 2011-05-30T15:24:43.800 回答
1

也就是说，有没有一种方法可以实现一个键值对，它至少具有 O(log n) 的查找、插入和删除，它是完全持久的，但与普通哈希一样“节省空间”（最坏情况）-桌子？

是的。Driscoll 等人的“使数据结构持久化”的第 5 节展示了一种制作完全持久的红黑树的技术，该技术具有 O(lg n) 时间和 O(1) 空间复杂度，用于插入、删除和查找。

它们的数据结构不是一致持久的。有关持久性的更多信息，请参阅Kaplan 关于该主题的调查。

于 2011-03-24T03:14:59.710 回答
1

Clojure 实现了一整套持久性数据结构，例如哈希映射。它是开源的，所以也许你应该看看？

http://clojure.org/data_structures

http://code.google.com/p/clojure/source/browse/trunk/src/jvm/clojure/lang/PersistentHashMap.java

于 2011-02-01T17:39:29.530 回答