基本上我正在寻找java中的最佳数据结构，我可以存储对并按值检索前N个元素。我想在 O(n) 时间内执行此操作，其中 n 是数据结构中的整数数。
示例输入是，
<"john", 32>
<"dave", 3>
<"brian", 15>
<"jenna", 23>
<"rachael", 41>
如果 N=3，如果我想要降序排列，我应该能够返回 rachael、john、jenna。
如果我使用某种 hashMap，插入速度很快，但按顺序检索它们会很昂贵。如果我使用一些保持有序的数据结构，那么插入变得昂贵，而检索更便宜。我无法找到既能做得很好又能很快做的最好的数据结构。
任何意见表示赞赏。谢谢。
[更新]
让我以其他方式问这个问题是否更清楚。我知道我可以在恒定时间 O(1) 插入 hashMap。现在，我如何在 O(n) 时间内按值从排序顺序中检索元素，其中 n=数据结构中的整数个数？希望这是有道理的。
如果要排序，则必须放弃恒定的 O(1) 时间。
这是因为与插入未排序的键/值对不同，排序将最低限度地要求您将新条目与某物进行比较，并且赔率是与许多东西的比较。一旦你有一个算法需要更多的时间和更多的条目（由于更多的比较），你已经超过了“恒定”时间。
如果你能做得更好，那么一定要这样做！有一个 Dijkstra 奖在等着你，如果不是菲尔兹奖章的话。
不要失望，您仍然可以将关键部分作为 HashMap 进行，而排序部分使用类似树的实现，这将为您提供 O(log n)。TreeMap 可能是您想要的。
--- 更新以匹配您的更新 ---
不，您不能在 O(n) 时间内迭代哈希图。这样做会假设您有一个列表；但是，该列表必须已经排序。使用原始 HashMap，您必须在整个地图中搜索下一个“较低”值。搜索地图的一部分是不行的，因为您没有检查的一个元素可能是正确的值。
现在，有一些数据结构可以做出很多权衡，这可能会让你更接近。如果您想自己滚动，也许自定义斐波那契堆可以为您提供接近您希望的摊销性能，但它不能保证最坏情况下的性能。在任何情况下，某些操作（如 extract-min）仍然需要 O(log n) 性能。