持久哈希表实现

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

也就是说，是否有一种方法可以实现至少O（log n）查找，插入和删除的键值对，这种查找，插入和删除是完全持久化的，但与“空间效率”（最坏情况）一个普通的散列表？

来源

2011-02-01 ManRow

在那篇维基百科文章中，有至少5种不同的持久性，你在寻找什么样的持久性？ – 2011-02-01 08:49:31

完整的持久性，只是更新原来的文章 – ManRow 2011-02-01 09:03:53

如果我很好地理解你的问题，如果你想要每个孩子，从父母继承哈希表，你可以每次创建/添加一个孩子时，做一个哈希表的深层副本。 – Muggen 2011-02-01 09:04:38

“作为一个普通的散列表空间效率”是一个相当模糊的规范，因为“普通”可能意味着链接或探索取决于你问谁。我认为任何人都没有设计易于理解的持久散列表。

获得持久键值映射的最简单方法是使用持久化二叉搜索树。查找是来自短暂（非永久）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）行为，请使用红黑树。另见关于函数式编程中数据结构的文献，例如冈崎的作品。

来源

2011-02-01 11:19:12

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

http://clojure.org/data_structures

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

来源

2011-02-01 17:39:29

即，是否有实现与至少O（log n）的查找，插入和缺失也就是充分持久一个键 - 值对的一种方式，但是作为一个普通的哈希表“空间效率”（最坏情况）？

是的。 Driscoll等人的"Making Data Structures Persistent"的第5部分展示了一种用于插入，删除和查找的具有O（lg n）时间和O（1）空间复杂度的完全持久的红黑树的技术。

他们的数据结构不是很持久。有关持久性的更多信息，请参见Kaplan's survey on the topic。

来源

2011-03-24 03:14:59 jbapple

您是否尝试过或查看过jdbm2的源代码？ http://code.google.com/p/jdbm2/

来源

2011-05-30 14:13:12 John

是否有实现与至少O（log n）的查找，插入和删除，它完全持久键值配对的方式，但作为“空间效率”（最坏情况）作为一个普通的散列表？

确实有。很多方法。

E.g.

斯蒂芬亚当斯“的高效集：：一个平衡的行为”，[功能编程3的（4在Haskell，简单Data.Map，一个大小平衡二进制树（或有界平衡的树）由如所描述的）：553-562，1993年10月，http://www.swiss.ai.mit.edu/~adams/BB/。
J. Nievergelt和EM莱因戈尔德，计算的SIAM杂志 “有限的平衡二叉搜索树” 2（1），1973年三月

提供以下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-30 15:24:43

持久哈希表实现

回答

相关问题