1

我想知道是否有更有效的方法可以从我的 LinkedHashMap 中获取时间戳大于指定时间的对象。即比以下更好的东西：

    Iterator<Foo>  it = foo_map.values().iterator();
    Foo foo;

    while(it.hasNext()){
        foo = it.next();
        if(foo.get_timestamp() < minStamp) continue;

        break;
    }

在我的实现中，我的每个对象基本上都具有三个值：“id”、“timestamp”和“data”。这些对象是按照它们的时间戳顺序插入的，所以当我在集合上调用迭代器时，我会得到有序的结果（根据链接的 hashmap 合约的要求）。地图以对象的 id 为键，因此我可以通过 id 快速查找它们。

但是，当我通过时间戳条件查找它们时，我会得到一个带有排序结果的迭代器。这是对通用哈希图的改进，但我仍然需要在大部分范围内按顺序迭代，直到找到具有比指定时间戳更高的时间戳的下一个条目。

由于结果已经排序，是否有任何算法可以将迭代器（或集合传递给），它可以比顺序搜索更快？如果我使用树形图作为替代方案，它会提供整体速度优势，还是在后台做基本相同的事情？由于集合已经按插入顺序排序，我认为树形图有更多我不需要的开销？

4

1 回答 1

2

没有更快的方法......如果你只使用LinkedHashMap.

如果你想要更快的访问，你需要使用不同的数据结构。例如，TreeSet带有适当比较器的 a 可能是您问题的这方面的更好解决方案。例如，如果您的 TreeSet 按日期排序，则tailSet使用适当的虚拟值调用可以为您提供大于或等于给定日期的所有元素。

由于结果已经排序，是否有任何算法可以将迭代器（或集合传递给），它可以比顺序搜索更快？

不是为了一个LinkedHashMap。

但是，如果有序列表是一个ArrayList替代，那么您可以在列表上使用“二分搜索”......前提是您可以锁定它以防止在搜索时进行并发修改。（实际上，无论您如何实现并发性都是一个需要考虑的潜在问题……包括您当前的线性搜索。）

如果你想保持id查找的能力，那么你需要两个数据结构；例如 aTreeSet和 aHashMap共享它们的元素对象。假设存在随机插入和/或随机删除，ATreeSet可能比尝试维护顺序更有效。ArrayList

于 2013-08-08T01:23:12.627 回答