When I work with maps, I tend to prefer ones whose elements can be iterated through in the same order they were inserted. It makes them feel more deterministic and easier to test. For this reason and others I've always been a sucker for LinkedHashMap in Java.
In the FP world, for lookups there is a preference for trees over maps. True, in Scala there is an immutable version of LinkedHashMap called ListMap, but it doesn't use hashes and seems too slow for most practical uses.
If I want to get the advantages of immutability, how can I satisfy my thirst for data structures that remember insertion order as well as having fast lookup? Has somebody written something in a library somewhere?
Finit maps (hashtables, dictionaries) usually do not guarantee correct order iteration. It is a common thing for most of libraries and languages. So, if you want to iterate through it, I would recomend you to store keys (pointers) into additional data structure that supports insert-order iteration. Thus, you can iterate through helper array and lookup into finit map for details about the entry.
Regarding finit maps. Scala (just like Closure) uses HAMT (Hash Array Mapped Tree) data structure for hashtable implementation. And it realy fast. There is also Fast Mergeble Integer Maps (by C. Okasaki) which can be used as finit maps. And, you were right about trees. Haskell uses Red-Black tree as finit map implementaions. It also fast and it almost O(1). For example, for storing all possible keys in such map in JVM platform you need to alocate 2147483647 nodes. So, to look up through the whole tree you need only log_2(2147483647)=31 steps. Not so slow, huh?