在Java中访问/修改数据的最快数据结构是什么？

Question

大家好，这里是Stackoverflow！

在编写项目时，我想知道哪种数据结构最快，以便在需要频繁访问/编辑数据时提供最佳性能？

举个例子来解释一下。我有一个名为User的类和一个名为Event的类。一个User可以有很多个Event。直到现在，我使用ArrayList来实现这种情况：

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

由于我有大量的用户（数百万），每个用户可能会拥有数千个事件，并且，而且我必须使用process()方法访问用户的每个事件，因此，像HashMaps等结构将没有帮助（如果我错了，请告诉我）。但是，很明显，对于这么多元素来说，良好的性能是必要的。

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

非常感谢，

Marco。

- smellyarmpits

---

取决于您如何处理事件。顺序重要吗？如果是，那么它是FIFO还是LIFO数据结构？ - m0skit0

我宁愿将这个委托给数据库。 - LeleDumbo

我同意LeleDumbo的观点，如果你有数百万用户，那就等于是在呼唤一个数据库。 - user520288

@m0skit0 不，我访问数据的顺序并不重要，因为我必须访问每个事件。 - smellyarmpits

@MarcoGalassi：你需要随机访问这些事件吗？例如：“给我UID为0x69696969的事件”？还是你只是把它们当作未排序的一堆？ - thkala

我不会将事件存储在数据结构中，相反，我会在当前线程或线程池中处理每个事件。你不能比什么都不做更轻量级了。 ;) - Peter Lawrey

Answer 1

这似乎更适合数据库处理，特别是如果您需要持久性和/或数据可能不适合计算机的主内存。然而，如果您坚持要在自己的代码中完成此操作，您可能需要查看LinkedHashMap类 LinkedHashmap 。它允许使用恒定（即O（1））复杂度直接访问其元素，同时还结合了内部链接列表，以便快速迭代所有元素。当然，是否使用HashMap结构取决于您想做什么。例如，如果您想基于某种标识符搜索事件，则HashMap非常理想。

另一方面，如果您只需要根据插入顺序访问事件，则最好使用ArrayList，因为它支持对其内容进行带有恒定复杂度的索引访问。如果您只需要将它们作为队列或堆栈处理，Java有几个实现Deque接口的实现可能会引起您的兴趣。

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

- thkala

---

我认为使用数据库并不能解决性能问题。如果我使用数据库，难道不会因为需要从中检索数据而产生额外的性能问题吗？我的意思是，如果我访问本地机器上的数据而不是数据库，那应该会更快。不是吗？ - smellyarmpits

@MarcoGalassi：1. 您始终可以在同一主机上运行数据库。2. 您确定您的数据始终适合可用内存吗？如果要使用磁盘，最好让数据库来处理-它比您更擅长。3. 您的持久性和一致性要求是什么？您需要事务吗？当您的程序终止时会发生什么。如果它崩溃了会怎样？ - thkala

@MarcoGalassi：我忘记了最重要的参数：在实际尝试应用程序之前，您似乎假定存在性能问题。过早地进行优化是万恶之源 - 在分析器告诉您之前，永远不要优化任何东西... - thkala

Answer 2

有两件事：

1- 在当前情况下，如果并发用户不是一个问题，那么您可以轻松地选择ArrayList作为更快、更简单的数据结构；但如果并发用户是一个问题，那么您可以轻松地选择Vector来存储您的事件。

2- 您可以使用队列数据结构，它将帮助您进行动态操作，如插入/删除，这比ArrayList和Vector更快，因为它使用迭代器。

希望对您有所帮助。

- user1455795

Answer 3

如果您的数据适合存储在主内存中，最好的解决方案是使用Java集合和普通数组（取决于需要随机访问、顺序性、持久化更改或其他需求）。如果您的数据增长超过单个系统内存，那么使用可集群化的NoSQL解决方案会获得更好的性能（同样，选择正确的工具取决于您对数据的处理方式）。

- Konstantin Pribluda