java - 对 1,000,000 个对象进行排序(不按键)- Java

Question

我有大约 1,000,000 个对象需要以某种形式的数据结构存储。它们必须通过键 (ID) 唯一 - 但根据它们的日期进行排序。因此，我试图想出一种以某种形式的数据结构存储它们的最佳方法。性能(根据执行时间)是主要目标，然后是内存使用。我的想法是将对象放入一棵树中，这样当它们进入数据结构时可以根据它们的日期进行排序，然后我可以按顺序返回它们。但是 - 我认为根据它的 ID 查找单个对象会非常慢。我确实想到了一个将 ID 链接到日期的二级结构，这样我就可以减少查找单个对象所花费的时间，或者只是通过这个 ID 存储所有内容(可能在 HashTable 中)然后进行排序当我想归还所有 1,000,000 个对象时(尽管这似乎需要很长时间)。

要点:

之后可能会添加对象，因此大约 1,000,000 个对象不是固定的。它们不会被更新或删除。我可能不使用 Java 的内置比较器。我正在优化返回数据的效率 - 无论这是按顺序排列的完整集合(按日期)，还是从其 ID 获得的单个对象。

Answer 1

如果在内存使用之前您最关心的是性能，我会选择 2 种数据结构:

ArrayList<YourClass> instancesByDate;

和

HashMap<SomeId,YourClass> instancesById;

这为您提供了最快的日期遍历和 O(1) 查找(显然取决于 hashCode())。