Java相当于C++ std :: map？

Question

我正在寻找一个具有C++ std :: map常用实现特性的Java类(据我所知,它是一个自平衡二进制搜索树):

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

我正在寻找开源或设计文档的实现; 我可能最终会支持原始键/值.

这个问题的风格类似于:Java等价于std :: deque,其答案是"来自Java的原始集合的ArrayDeque".

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简介:"Arrays ...是唯一支持存储原始数据类型的集合."