java - 树集的性能问题#add

Question

在我的应用程序中，我使用像有序队列一样的TreeSet。我已经分析了我的应用程序，并且花费了 25% 的 cpu 时间向 TreeSet 添加元素，但只花费了 2% 的时间弹出最后一个元素。对于有序队列有更好的集合吗？添加到 LinkedList 并在每次需要使用队列时对其进行排序是否会提高性能？

Answer 1

您应该使用PriorityQueue而不是 TreeSet 因为这是为队列设计的。

TreeSet 在将其用作队列时存在性能问题，因为其内部树结构不适合用作队列。这是因为它的内部结构是基于TreeMap，withs使用了red black tree ，并且这棵树需要移动许多元素以适应替换顶部元素的插入。在某些情况下，这需要完全重建树。

使用 PriorityQueue 很简单:

PriorityQueue<YourObject> queue = new PriorityQueue<>();

与TreeSet不同，PriorityQueue允许重复的元素，并以先进先出的顺序将它们返回。

如果您需要踩踏安全解决方案，您应该使用PriorityBlockingQueue相反。