当我使用地图时，我倾向于选择那些元素可以按照插入顺序进行迭代的地图。这让他们感觉更有确定性并且更容易测试。由于这个原因和其他原因，我一直是 Java 中 LinkedHashMap 的傻瓜。
在 FP 世界中，对于查找而言，树优先于地图。诚然，在 Scala 中有一个不可变的 LinkedHashMap 版本，称为 ListMap，但它不使用哈希，而且对于大多数实际用途来说似乎太慢了。
如果我想获得不变性的优势，我如何才能满足我对能够记住插入顺序和快速查找的数据结构的渴望？有人在某处的图书馆里写过东西吗？
Finit 映射（哈希表、字典）通常不保证正确的顺序迭代。对于大多数库和语言来说，这是很常见的事情。因此，如果您想遍历它，我建议您将键（指针）存储到支持插入顺序迭代的附加数据结构中。因此，您可以遍历辅助数组并查找 finit 映射以获取有关条目的详细信息。
关于有限映射。Scala（就像 Closure 一样）使用 HAMT（哈希数组映射树）数据结构来实现哈希表。而且它真的很快。还有可以用作有限映射的Fast Mergeble Integer Map s（由 C. Okasaki 编写）。而且，你对树木的看法是对的。Haskell 使用红黑树作为有限映射实现。它也快和它差不多O(1)。例如，要在 JVM 平台的此类映射中存储所有可能的键，您需要分配 2147483647 个节点。因此，要查看整棵树，您只需要log_2(2147483647)=31几步。没那么慢吧？