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

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

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