java - Java 等效于 C++ std::map？

Question

我正在寻找一个具有 C++ std::map 通常实现特性的 Java 类（据我了解，一个自平衡二叉搜索树）：

1. 插入/删除/搜索的 O(log n) 性能
2. 每个元素由唯一的键和映射的值组成
3. 键遵循严格的弱排序

我正在寻找具有开源或设计文档的实现；我可能最终会推出自己对原始键/值的支持。

这个问题的风格类似于：Java 等效于 std::deque，其答案是“ArrayDeque from Primitive Collections for Java”。

Answer 1

ConcurrentSkipListMap是一个由跳过列表（具有 O(log n) 性能的自平衡树状结构）支持的排序映射。通常，CSLM 的边界比 TreeMap（这是一个自平衡的红黑树 impl）更严格，因此它可能会执行得更好，并且具有线程安全和并发的好处，而 TreeMap 不是。CSLM 是在 JDK 1.6 中添加的。

Trove有一组原始类型的集合和常见 Java 集合类型的一些其他有趣的变体。

其他感兴趣的集合库包括Google Collection 库和Apache Commons Collections。

Answer 2

标准Java 库中最接近二叉树的类是java.util.TreeMap，但它不支持原始类型，除了装箱（即int 包装为Integer，double 包装为Double 等）。

java.util.HashMap 可能会为大型地图提供更好的性能。理论上它是 O(1)，但其精确的性能特征取决于密钥类的哈希码生成算法。

根据Collections 简介：“数组......是唯一支持存储原始数据类型的集合。”

Answer 3

您也可以查看 commons-collections FastTreeMap。

我怀疑你会发现许多支持原始类型的集合而没有装箱，所以就忍受它吧。这不是必需的，因为autoboxing。

如果您真的想使用原语（在进行了显示性能不足的基准测试之后！），您可以查看源代码FastTreeMap并添加处理原语的方法。