[beders]

I suggest you check out efficient mutable data-structures which are safe by default. Clojure and ClojureScript come to mind.

[UncleMeat]

They are still less efficient. Compare even modern stuff like HAMTs to ordinary sets. Close, but no cigar.