Постоянная структура данных (в Scala), которая поддерживает быстрый поиск и порядок вставки?

Question

Когда я работаю с картами, я склонен отдавать предпочтение тем, элементы которых можно перебирать в том же порядке, в котором они были вставлены. Это заставляет их чувствовать себя более детерминированными и их легче тестировать. По этой и другим причинам я всегда был любителем LinkedHashMap в Java.

В мире FP для поисков предпочтение отдается деревьям, а не картам. Правда, в Scala есть неизменяемая версия LinkedHashMap, называемая ListMap, но она не использует хэши и кажется слишком медленной для большинства практических применений.

Если я хочу получить преимущества неизменяемости, как я могу удовлетворить свою жажду структур данных, которые помнят порядок вставки, а также имеют быстрый поиск? Кто-нибудь что-то написал в библиотеке?

Answer 1

Конечные карты (хеш-таблицы, словари) обычно не гарантируют правильную последовательность итераций. Это обычная вещь для большинства библиотек и языков. Поэтому, если вы хотите выполнить итерацию, я рекомендую вам хранить ключи (указатели) в дополнительной структуре данных, которая поддерживает итерацию в порядке вставки. Таким образом, вы можете выполнять итерацию по вспомогательному массиву и искать в карте конечных элементов сведения о записи.

По поводу конечных карт. Scala (как и Closure) использует структуру данных HAMT ( Hash Array Mapped Tree) для реализации хеш-таблиц. И это очень быстро. Существует также Fast Mergeble Integer Map s (by C. Okasaki), которую можно использовать в качестве конечных карт. И вы были правы насчет деревьев. Haskell использует красно-черное дерево в качестве конечных реализаций карты. Это также быстро, и это почти O(1), Например, для хранения всех возможных ключей в такой карте на платформе JVM необходимо выделить 2147483647 узлов. Итак, чтобы посмотреть сквозь все дерево, вам нужно только log_2(2147483647)=31 шаги. Не так медленно, а?