マップを扱うときは、要素が挿入されたのと同じ順序で反復できるマップを好む傾向があります。これにより、より決定論的でテストしやすくなります。この理由やその他の理由から、私は常に Java の LinkedHashMap の吸盤でした。
FP の世界では、ルックアップではマップよりもツリーが優先されます。確かに、Scala には ListMap と呼ばれる LinkedHashMap の不変バージョンがありますが、これはハッシュを使用しておらず、ほとんどの実用的な用途には遅すぎるようです。
不変性の利点を利用したい場合、挿入順序を記憶し、検索を高速化するデータ構造への渇望を満たすにはどうすればよいでしょうか? 誰かがどこかの図書館で何かを書いたことがありますか?
Finit マップ (ハッシュテーブル、辞書) は通常、正しい順序の繰り返しを保証しません。これは、ほとんどのライブラリと言語に共通することです。したがって、それを反復処理する場合は、挿入順序の反復をサポートする追加のデータ構造にキー (ポインター) を格納することをお勧めします。したがって、ヘルパー配列を反復処理し、finit マップを参照してエントリの詳細を確認できます。
有限マップについて。Scala (Closure と同様) は、ハッシュテーブルの実装に HAMT ( Hash Array Mapped Tree ) データ構造を使用します。そして、それは本当に速いです。Finit マップとして使用できるFast Mergeble Integer Map (C. Okasaki による)もあります。そして、あなたは木について正しかった。Haskell は赤黒木を有限マップの実装として使用します。それはまた速く、それはほとんどO(1)です。たとえば、JVM プラットフォームでこのようなマップにすべての可能なキーを格納するには、2147483647 個のノードを割り当てる必要があります。したがって、ツリー全体を調べるには、ステップのみが必要log_2(2147483647)=31です。そんなに遅くないでしょ？