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

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

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

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

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

В любом случае, чтобы поделиться с людьми, это две интересные записи в блоге о реализации постоянных векторов в 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

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

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