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?