Реализация стойких хэш-таблиц

Question

В программе, над которой я работаю, я разрабатываю большое «дерево потоков» (не более k детей на узел), где каждый поток вносит некоторые изменения в хеш-таблицу, унаследованную от ее родителя. Есть ли способ реализовать хеш-таблицу, которая несколько «настойчива» (в смысле http://en.wikipedia.org/wiki/Persistent_data_structure)?

А именно, существует ли способ реализовать сопряжение значений ключа с по крайней мере O (log n) поиском, вставкой и удалением, которое является полностью постоянным, но является «пространственно эффективным» (в худшем случае), поскольку обычный хеш-стол?

Answer 1

«Как экономичный по площади, как обычный хеш-стол», является довольно неопределенной спецификацией, поскольку «обычная» может означать связь или зондирование в зависимости от того, кого вы спрашиваете. Я не думаю, что кто-либо разработал простые для понимания постоянные хеш-таблицы.

Самый простой способ получить постоянную карту значений ключа со сложностью, которую вы хотите, - использовать постоянное двоичное дерево поиска. Поиск - это знакомый алгоритм из эфемерных (непостоянных) 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), используйте красно-черное дерево. См. Также литературу по структурам данных в функциональном программировании, например. работы Окасаки.

Answer 2

Clojure реализовал целый набор постоянных структур данных, таких как хэш-карты. Это с открытым исходным кодом, так что, может быть, вам стоит взглянуть?

http://clojure.org/data_structures

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

Answer 3

А именно, есть способ реализовать ключ-значение сопряжения с, по меньшей мере, O (Log п) поиска, вставки и удаления, полностью повторяется, но как «экономичный по площади» (в худшем случае) как обычный хеш-стол?

Да. В разделе 5 Driscoll et al. "Making Data Structures Persistent" показан способ создания полностью стойких красно-черных деревьев с временем O (lg n) и сложностью пространства O (1) для вставки, удаления и поиска.

Их структура данных не сходится постоянно. Подробнее о сохранении см. В разделе Kaplan's survey on the topic.

Answer 4

Вы изучали источник jdbm2? http://code.google.com/p/jdbm2/

Answer 5

Есть ли способ реализовать ключ-значение сопряжения с, по меньшей мере, O (Log п) поиска, вставки и удаления, полностью повторяется, но как «пространство-эффективным» (в худшем случае) как обычный хеш-стол?

Действительно есть. Много способов.

E.g.в Haskell, простой Data.Map, через размер сбалансированных бинарных деревьев (или деревьев ограниченного баланса), как описано в:

• Стивен Адамс, «Эффективные наборы: уравновешивание», журнал функционального программирования 3 (4): 553-562, октябрь 1993 года, 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).

Для улучшения постоянных факторов, попробуйте, например. a Data.HashMap структуры данных с той же общей сложностью.

Альтернативные структуры включают в себя:

• настойчивые попытки, которые улучшили использование пространства над хеш-таблицы, так как хранение ключей плотно.