java - Java 小地图与大地图表现

Question

我有一个不同对象的列表，例如：

Object1
Object2
...
ObjectN

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

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

如果我使用 a ，我HashMap相信Map<Object, String>由于.O(1)ObjectTreeMap

需要注意的是，对象的数量不在一个已知的区间内，也无法近似。

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

任何帮助将不胜感激。

score 0 · Accepted Answer

你们所有的实现都需要获取所有元素

获取具有某种类型的所有元素并进行我的计算或

显然，Map<Type, List>在这种情况下更好。

获取所有元素，获取它们的类型，然后计算我的数据。

这等于

 foreach types do
      do condition (1)

所以，Map<Type, List>比较好

score 0 · Accepted Answer

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

基于红黑树的 NavigableMap 实现。地图根据其键的自然顺序排序，或者由地图创建时提供的比较器排序，具体取决于使用的构造函数。此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。

TreeMap<TYPE, List<Object>>使用or 没有区别TreeMap<Object, TYPE>。性能差异取决于 equals 和 hashcode 函数的实现。在这种情况下，不是关于 Mapping 策略的选择。选择最适合您的软件设计需求的方式。

2 回答 2