Java Small Map 与 Large Map 性能

Question

我有一个不同对象的列表，如下所示:

Object1
Object2
...
ObjectN

每个对象都有一个TYPE ，可以是多个值之一(不超过 10)。这意味着有很多对象具有相同的类型。

这些对象将根据类型进行映射。哪种方法在速度方面更有效？有一个TreeMap<TYPE, List<Object>>或有 TreeMap<Object, TYPE> 。使用的 map 不会是HashMap ，但是 TreeMap ，原因超出了本问题的目的。

如果我使用HashMap ，我相信实现 Map<Object, String> 会更快由于O(1) Object的访问时间.但是，我无法判断我是否使用 TreeMap哪种方法可以提供更好的性能。

请注意，对象的数量不在已知区间内，无法估算。

编辑:实现取决于此选择。我可以获取具有某种类型的所有元素并进行计算，也可以获取所有元素，获取它们的类型，然后计算我的数据。

任何帮助将不胜感激。

Answer 1

TreeMap 内部实现为红黑树，因此任何操作的时间复杂度都是 O(logn)。所以HashMap对于索引的访问速度更快。但使用 HashMap 时，您无法以有序的方式存储数据，因此搜索操作将是 O(n)。来自文档:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

如果使用 TreeMap<TYPE, List<Object>> 没有区别或TreeMap<Object, TYPE> 。性能差异取决于 equals 和 hashcode 函数的实现。不涉及本例中映射策略的选择。选择最适合您的软件设计需求的方式。