最适合使用的集合？[关闭]

Question

我正在阅读日志文件，但并非所有行都希望立即处理。我正在使用队列/缓冲区来存储等待处理的行。

该队列会定期扫描特定行 - 当找到它们时，会将它们从队列中删除（它们可以位于队列中的任何位置）。当没有找到特定的行时，将从队列的开头逐一取出行进行处理。

因此，队列需要以下内容：

• 能够调整大小（或给人这种印象）
• 从任何地方删除元素
• 添加元素（将始终位于队列末尾）
• 快速扫描
• 根据性能，有一个指示上次扫描到达位置的指针。

我最初编写代码时，我对 Java 或 API 的经验很少，只是使用了 ArrayList，因为我知道它会起作用（不一定是因为它是最佳选择）。

它的性能现在变得很差，需要处理越来越多的日志 - 那么，您建议在这种情况下使用什么集合？我也总有可能写自己的。

谢谢

Answer 1

LinkedHashSet 可能会让人感兴趣。它实际上是一个 HashSet，但它还维护一个 LinkedList 以允许可预测的迭代顺序 - 因此也可以用作 FIFO 队列，还有一个额外的好处，即它不能包含重复的条目。

因为它也是一个 HashSet，所以如果可以匹配，搜索（而不是扫描）可以是 O(1) equals()

Answer 2

LinkedList 可能是最合适的。它具有所有请求的属性，并允许在恒定时间内从中间删除链接，而不是 ArrayList 所需的线性时间。

如果您有一些特定的策略来查找下一个要删除的元素，那么 PriorityQueue 甚至排序集可能更合适。

Answer 3

快速扫描通常意味着某种基于散列的实现，ConcurrentSkipListMap 可能是一个很好的实现。Log(n) 对 containskey、remove 和 get 方法进行排序，以便您可以拥有与其关联的某种优先级。

Answer 4

我不想对正在读取的行进行排序（它们需要保持原始顺序）。但是，我可能会根据每个记录行所具有的会话 ID（每个会话有多个记录行）来阻止这些行。

想一想，我可能会有：

HashMap<String,LinkedList<String>>

并提供会话 ID 作为键，并使用属于该会话的行填充 LinkedList。

Map 将提供一种快速的方法来搜索与会话 X 相关的行，然后链接列表将提供最佳性能来添加/删除行（搜索性能是查找与会话 x 相关的行，因此实际的行可以从头到尾读取和删除与会话 x 相关的内容 - 推送/弹出）。

有没有比链接列表更好的集合，它可以调整大小，在末尾添加行并始终从开头获取？我相信队列集合无论如何都扩展了链表？

Answer 5

因为您需要从集合中删除和添加元素，并搜索特定值，所以更好的结构可能是实现 SortedSet 的结构，例如 TreeSet。此类保证添加、删除和包含的 log(n) 性能。

Answer 6

我猜想一些线程将写入队列，而另一个线程将从队列中读取。

在这种情况下，您应该查看 java.lang.concurrent 包中的队列。

您可以使用 PriorityBlockingQueue 让它为您排序元素，或者如果您想迭代它并自己选择要删除的元素，则可以使用 LinkedBlockingQueue。

Answer 7

我同意 AVI 和链接列表将是你最好的选择。您可以轻松调整大小、快速添加到列表末尾、从任何地方快速删除。搜索速度不会很快，但也不会比任何其他未排序的列表差。

Answer 8

番石榴 可能有帮助。

Guava 项目包含我们在基于 Java 的项目中依赖的几个 Google 核心库：集合、缓存、原语支持、并发库、通用注释、字符串处理、I/O 等等。