どのように不変なリストが動作するか（再帰的なリンクリスト）と、それらのメリットを変更可能なリストよりも知っています。 ）仕事は？不変マップにはどのようなデータ構造が使用されていますか？
私は、新しいマップを生成するときに元のマップを邪魔しないという利点を知っていますが、基礎となるデータ構造はどのように機能し、どのようなパフォーマンス特性を持っていますか？人々がこれらを実装するために使用する標準的なデータ構造はありますか？CLRS/wikipediaで調べることができますか？
永続ハッシュマップはHash trieと呼ばれる構造を使用して実装されています。 originally proposed by Phil Bagwell（EPFLのScalaグループのメンバー）が、実際にClojureによって最初に実装されました。 2.8は2010年
に出てきたとき、それはハッシュトライの仕組みは（そのようなバンカーのキューとして他のものと一緒に）非常に明快に説明しているダン・スピーバックによってgreat talk on functional data structuresありスカラ座をヒット！彼はまた話の中で漸進的なビッグ・オー・パフォーマンスをとてもうまく説明します。
昨年10月、フィリップ氏はLondon scala Lift Offで別の講演をしましたが、今回は並列永続データ構造になりました。
永続的なソートされたマップはRed-Black tree
一般に、永続的なデータ構造は*構造的な共有*に依存します（例えば、永続的な短所リストはその末尾を共有します）。通常は、ツリーを使用します。永続的な短所リストがどのように機能するかを理解していれば、中途半端になっています。リストはすべて縮退したツリーで、どこにでも1つのブランチしか存在しません。 （または、ツリーは、各セルが複数の後継を持つリストの一般化です。） –
興味深い情報は、その理解をハッシュベースのアクセスにどのように関連付けるのかということです –
これはツリー（赤黒）またはハッシュマップです。それらのアクセス特性は基本的な実装に依存します。ツリーは読み込みアクセスの場合はO（log n）です。ハッシュマップはO（1）です。
CLRSを経由して実装され、ほとんどすべての他のデータ構造/アルゴリズムの教科書は、*大きく*可変性や不純物に偏っています。クリス・オカサキ*は、文字通り、彼の以前の論文研究に基づいた機能的データ構造に関する本を書いた。あなたが見なければならない他の作品はPhil BagwellとRich Hickeyです。 –