Эффективная реализация неизменной карты?

Question

Мне интересно, есть ли реализация карты, которая:

• Неизменный , чтобы я мог использовать его в функциональное программирование и без усилий обеспечить транзакции и параллелизм.
• Fast . Я проверил двоичный Деревья поиска (RB, AVL) и попытки, но ни один из них, казалось, не был так быстр, как Хеш-таблицы. Есть карта реализация, которая поддерживает постоянное время для обновлений и поиска? (или хотя бы очень быстрое логарифмическое время)

Короче говоря, существует ли функциональная структура данных, которая может сравниться с Hash Maps по производительности?

Answer 1

Clojure имеет неизменные карты. ( ссылка ). Не уверен, какую базовую структуру данных он использует. Исходный код Clojure даст вам больше информации!

Answer 2

Scala также имеет неизменных карт , но они медленнее хеш-таблиц. Я подозреваю, что ответ на ваш вопрос - нет, вы не найдете неизменную реализацию карты с O (1) ожидаемым временем операций вставки / запроса.

Answer 3

Я не читал это, но я думаю, что некоторые люди считают чисто функциональные структуры данных библией для такого рода вещей.

Answer 4

В любом случае, просто чтобы поделиться с людьми, это две интересные записи в блоге о реализации Persistent Vectors в Scala с использованием Tries. Они также упоминают реализацию Clojure, а также новый IntMap в последних выпусках Scala.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

Для этих структур данных я протестировал ключ как целые числа, но пока не строки. Поскольку мое настоящее приложение будет использовать строки в качестве ключей, я не уверен, будет ли реализация более эффективной, чем Hash Map. Что если я использую HashCode строки в качестве ключа, а затем использую постоянный вектор для поддержки карты? Я буду использовать 32-полосную схему для реализации Постоянного вектора. Я думаю, что столкновение будет очень редким, и память будет расходоваться только соответственно. Но я не уверен, сколько нужно копировать в обновлениях.

Я скоро опубликую свои результаты.