基本上我在寻找java中最好的数据结构,我可以存储对并通过值检索前N个元素.我想在O(n)时间做到这一点,其中n是数据结构中的entires数.
示例输入将是,
<"john", 32>
<"dave", 3>
<"brian", 15>
<"jenna", 23>
<"rachael", 41>
如果N = 3,如果我想降序,我应该能够返回rachael,john,jenna.
如果我使用某种hashMap,插入速度很快,但按顺序检索它们会变得很昂贵.如果我使用一些保持订单的数据结构,那么插入变得昂贵,而检索更便宜.我无法找到能够做得非常好而且速度非常快的最佳数据结构.
任何输入都表示赞赏.谢谢.
[更新]
让我以其他方式提出问题,如果这样做更清楚.我知道我可以在恒定时间O(1)插入hashMap.现在,我怎样才能在O(n)时间内按值排序检索元素,其中n =数据结构中的entires数量？希望它有意义.
如果要排序,则必须放弃不变的O(1)时间.
这是因为与插入未排序的键/值对不同,排序将最低限度地要求您将新条目与某些内容进行比较,并且赔率可能是许多事情.一旦你有一个算法,需要更多的时间与更多的条目(由于更多的比较),你有超过"恒定"时间.
如果你能做得更好,那么一定要做到!有一个Dijkstra奖等待你,如果不是菲尔兹奖章开机.
不要绝望,你仍然可以将关键部分作为HashMap,并使用树类实现的排序部分,它将为您提供O(log n).TreeMap可能就是你想要的.
---更新以匹配您的更新---
不,你不能在O(n)时间迭代一个hashmap.这样做会假设你有一个清单; 但是,该列表必须已经排序.使用原始HashMap,您必须在整个地图中搜索下一个"较低"值.搜索地图的一部分不会,因为您未检查的一个元素可能是正确的值.
现在,有一些数据结构可以做很多折衷,可能会让你更接近.如果你想自己动手,也许定制的Fibonacci堆可以给你一个接近你想要的摊销性能,但它不能保证最差的性能.在任何情况下,某些操作(如extract-min)仍然需要O(log n)性能.