当我使用映射时，我倾向于选择那些元素可以按插入顺序迭代的映射。这让他们感觉更确定，更容易测试。由于这个原因和其他原因，我一直很喜欢Java中的LinkedHashMap。
在FP世界中，对于查找，树比映射更受青睐。的确，在Scala中有一个不可变的LinkedHashMap版本，叫做ListMap，但是它不使用哈希，对于大多数实际用途来说似乎太慢了。
如果我想获得不变性的优势，我如何才能满足我对数据结构的渴望，既能记住插入顺序，又能快速查找?有人在图书馆里写了什么吗?
有限映射(哈希表、字典)通常不能保证正确的顺序迭代。对于大多数库和语言来说，这是很常见的事情。因此，如果您想遍历它，我建议您将键(指针)存储到支持插入顺序迭代的其他数据结构中。因此，您可以遍历helper数组并在finit map中查找有关条目的详细信息。
关于有限映射。Scala(就像Closure一样)使用HAMT(哈希数组映射树)数据结构来实现哈希表。而且速度非常快。也有快速可合并整数映射(C. Okasaki)，它可以用作有限映射。而且，关于树，你是对的。Haskell使用红黑树作为有限映射的实现。它也很快，几乎是O(1)。例如，为了在JVM平台上存储这种映射中所有可能的键，您需要分配2147483647个节点。因此，要查找整个树只需要log_2(2147483647)=31步。没那么慢吧?