Java 中访问/修改最快的数据结构

Question

你好，Stackoverflowers！

当我编写一个项目时，我想知道如果我必须访问/编辑大量数据，哪种数据结构可以让我获得最佳性能？

让我用一个例子来解释一下。我有一个名为 User 的类和一个 Event 类。一个用户可以有许多事件。到目前为止，我已经用ArrayList实现了这种情况：

public class User{
    ArrayList<Event> events;
    public void process(){
    }
    ...
}
public class Event{
    event data like event time etc.
}

由于我有很多用户（数百万），每个用户可能有数千个事件，而且，我必须使用 process() 方法访问用户的每个事件，我认为使用 HashMaps 等结构不会有帮助（如果错了请告诉我）。然而，很明显，有了这么多的元素，就需要良好的性能。

那么，您认为处理事件最快的数据结构是什么？

非常感谢，

马可.

Answer 1

这听起来像是一项更适合数据库的工作，特别是如果您想要持久性和/或您的数据可能不适合计算机的主内存。

但是，如果您坚持在自己的代码中执行此操作，则可能需要查看该类LinkedHashMap。它允许以恒定（即 O(1)）复杂度直接访问其元素，同时还组合内部链表以允许对所有元素进行快速迭代。

当然，一个HashMap结构是否有帮助取决于你想要做什么。例如，如果您想根据某种标识符搜索事件，那么 aHashMap是理想的选择。

另一方面，如果您只需要根据事件的插入顺序访问事件，那么您不能做得比更好ArrayList，因为它支持以恒定的复杂性对其内容进行索引访问。如果您只需要在队列或堆栈中处理它们，Java 有几种Deque您可能感兴趣的接口实现。

最后，如果您想随机插入键并让底层结构自行对它们进行排序，您可能会发现该类TreeMap很有用。