java - Java中哪种Map数据结构可以最有效地获取最高元素？

Question

TreeMap 具有 O(log n) 性能(最好情况)，但是，因为我需要有效地进行以下操作:

• 获取最高元素
• 获取 XY 最高元素
• 插入

另一种可能性是使用以下内容创建一个 PriorityQueue:

• 使用“index”元素作为 PriorityQueue 的顺序
• equals 实现仅检查“索引”元素相等性 但这将是一种黑客行为，因为“equals”方法很容易出错(如果在 PriorityQueue 之外使用)。

有更好的结构吗？

您可以跳过下面的更多详细信息，因为第一个答案对此细节提供了很好的答案，但是，我将使其保持活跃以进行理论讨论。

注意:我可以使用非标准数据结构，在这个项目中我已经使用了 UnrolledLinkedList 因为它很可能是其他用途中最有效的结构。

这是用例(如果您感兴趣的话):我正在为一款电脑游戏构建人工智能，其中

  OffensiveNessHistory myOffensiveNess = battle.pl[orderNumber].calculateOffensivenessHistory();

可能的实现:

public class OffensiveNessHistory {
  PriorityQueue<OffensiveNessHistoryEntry> offensivenessEntries = new PriorityQueue<OffensiveNessHistoryEntry>();
..

或

public class OffensiveNessHistory {
  TreeMap<Integer, OffensiveNessHistoryEntry> offensivenessEntries = new TreeMap();
..

我想检查第一名玩家的进攻和防守历史，以计算预测我是否应该采取最具进攻性或最具防御性的 Action 。

Answer 1

首先，您应该考虑结构的大小(仅针对几个条目进行优化可能不值得)和操作的频率。

如果读取比写入更频繁(我假设是这种情况)，我会使用一种针对插入成本优化读取的结构，例如一个排序的 ArrayList，您可以在使用二分搜索找到的位置插入。这将是搜索的 O(log n) + 将其他条目向右移动的成本，但这意味着良好的缓存一致性和 O(1) 查找。

标准的 PriorityQueue 内部也使用数组，但需要您使用迭代器来获取元素 n(例如，如果您当时需要中值或最低条目)。

可能有一些结构可以在保持 O(1) 读取的同时进一步优化写入，但除非这些写入非常频繁，否则您甚至可能不会注意到任何性能提升。

最后也是最重要的，您应该尽量不要根据猜测进行优化，而应该首先进行分析。代码的其他部分可能会消耗性能，并且可能导致数据结构的优化毫无用处。