あるマップの実装がある場合、私は思ったんだけど：効率的で不変なマップの実装ですか？
、性能のハッシュマップと比較することができる機能的なデータ構造はありますか？
Clojureには不変のマップがあります。 （link）。使用している基本データ構造がわからないClojureのソースコードは、より多くの情報を提供します！
Scalaもimmutable mapsですが、ハッシュテーブルよりも遅いです。私はあなたの質問への答えがいいえ、あなたはO（1）予想時間の挿入/クエリ操作で不変のマップの実装を見つけることはできませんと思う。
さて、私は現在Scalaを試していて、一般的にはパフォーマンスに満足していません。 – Phil
とにかく人と共有するだけで、Tearsを使ったScalaのPersistent Vectors実装に関する2つの興味深いブログエントリです。彼らは最近のClojureの実装、最近のScalaリリースの新しいIntMapについても言及しています。これらのデータ構造のために
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis
、私は整数ではなく、まだ文字列としてキーを使用してテストしました。実際のアプリケーションでは文字列をキーとして使用するため、実装がハッシュマップよりも効率的かどうかはわかりません。文字列のHashCodeをキーとして使用し、永続的なベクトルを使用してマップをサポートするとどうなりますか？私はPersistent Vectorを実装するために32-wayトライを使用します。私は衝突が非常に稀で、メモリはそれに応じて消費されるだろうと思う。しかし、私は実際の量の更新をコピーする必要があるか分からない。
すぐに結果を掲載します。
私はそれを読んだことはありませんが、一部の人々はこの種のものの聖書としてPurely Functional Data Structuresと考えています。
マップ/ハッシュテーブルについては何も持っていません。 –
ご協力いただきありがとうございます。私はすぐにClojureをチェックアウトするつもりです。 – Phil
Clojureの不変のマップは、32ウェイのハッシュ・アレイ・マップ試行（http://en.wikipedia.org/wiki/Hash_array_mapped_trie）を使用します。それらは素晴らしいデータ構造です - 変更可能なHashMapとほぼ同じくらい高速ですが、永続的で不変であるという利点があります。 – mikera