Постоянная реализация хэш-таблицы
В программе, над которой я работаю, я разрабатываю большое "дерево потоков" (не более k детей на node), где каждый поток вносит некоторые изменения в хеш-таблицу, унаследованную от ее родителя. Есть ли способ реализовать хеш-таблицу, которая несколько "постоянна" (в смысле http://en.wikipedia.org/wiki/Persistent_data_structure)?
А именно, существует ли способ реализовать спаривание значений ключа с по крайней мере O (log n) поиском, вставкой и удалением, которое является полностью постоянным, но является "эффективным с точки зрения пространства" (в худшем случае) обычная хеш-таблица?
Ответы
Ответ 1
"Как экономичная по площади, как обычная хеш-таблица", довольно неопределенная спецификация, поскольку "обычная" может означать связь или зондирование в зависимости от того, кого вы спрашиваете. Я не думаю, что кто-либо разработал простые для понимания постоянные хеш-таблицы.
Самый простой способ получить постоянную карту ключевых значений со сложностью, которую вы хотите, - использовать постоянное двоичное дерево поиска. Поиск - это знакомый алгоритм из эфемерных (непостоянных) BST. Вставьте изменения, однако, и сделайте что-то вроде (псевдо-Java):
// overwrites the value for k if it 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), используйте красно-черное дерево. См. Также литературу по структурам данных в функциональном программировании, например. работы Окасаки.
Ответ 2
Есть ли способ реализовать сопряжение значений ключа с по крайней мере O (log n) поиском, вставкой и удалением, которое является полностью постоянным, но является "экономным по площади" (в худшем случае) как обычный хеш -стол?
Действительно, есть. Много способов.
например. в Haskell, простой Data.Map
, сбалансированные по размеру бинарные деревья (или деревья ограниченного баланса), как описано в:
- Стивен Адамс, "Эффективные множества: балансирующий акт", журнал функционального программирования 3 (4): 553-562, октябрь 1993 года, http://www.swiss.ai.mit.edu/~adams/BB/.
- J. Nievergelt и E.M. Reingold, "Бинарные деревья поиска ограниченного баланса", журнал 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
структуры данных с той же общей сложностью.
Альтернативные структуры включают:
- постоянные попытки, которые улучшают использование пространства поверх хэш-таблиц, поскольку хранилище ключей плотно.
Ответ 3
Clojure реализовал целый набор постоянных структур данных, таких как хэш-карты. Это с открытым исходным кодом, так что, возможно, вам стоит взглянуть?
http://clojure.org/data_structures
http://code.google.com/p/clojure/source/browse/trunk/src/jvm/clojure/lang/PersistentHashMap.java
Ответ 4
А именно, существует ли способ реализовать спаривание значений ключа с по крайней мере O (log n) поиском, вставкой и удалением, которое является полностью постоянным, но является "эффективным с точки зрения пространства" (в худшем случае) обычная хеш-таблица?
Да. Раздел 5 Driscoll et al. "Создание постоянных структур данных" показывает технику создания полностью стойких красно-черных деревьев с временем O (lg n) и сложностью пространства O (1) для вставки, удаления и поиска.
Их структура данных не сходится постоянно. Подробнее о сохранении см. Каплан по теме.
Ответ 5
Вы пробовали или рассматривали источник jdbm2? http://code.google.com/p/jdbm2/