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