Какая структура данных используется для неизменяемых карт?

Question

Я знаю, как работают обычные изменяемые карты (с использованием хеш-таблиц), и знаю, как работают неизменяемые списки (рекурсивные связанные списки) и как они превосходят изменяемые списки (добавление в постоянное время, не портя оригинал), но как работают неизменяемые карты (например,Скала) работа?

Я знаю преимущество, заключающееся в том, что при создании новых карт не возникает проблем с исходной картой, но как работает базовая структура данных и какие у них характеристики производительности, например, по сравнению с изменяемыми хеш-таблицами?Есть ли какая-то стандартная структура данных, которую люди используют для их реализации, которую я мог бы посмотреть в CLRS / wikipedia?

Answer 1

Постоянные Хеш-карты реализованы с использованием структуры, называемой Хеш-три . Он был первоначально предложенным Филом Багвеллом (который является членом группы Scala в EPFL), но на самом деле сначала был реализован Clojure. Когда в 2010 году вышло 2.8 , оно стало популярным.

* * * * * * * * * * * * * Дэн Спивак (Dan Spiewak) рассказывает о отличных разговорах о функциональных структурах данных, где механика хеш-три объясняется чрезвычайно доходчиво (наряду с другими вещами, такими как очереди банкиров)! Он также очень хорошо объясняет асимптотику биг-О в своем выступлении.

В октябре прошлого года Фил выступил с докладом на лондонском Scala Lift Off , на этот раз о параллельных постоянных структурах данных.

Постоянно отсортированные карты реализуются через Красно-черный дерево

Answer 2

Это может быть дерево (красно-чёрное) или хэш-карта. Их характеристики доступа зависят от базовой реализации. Дерево O (log n) для доступа на чтение; хеш-карта O (1).