0

我需要一个数据结构在 Log N 时间内执行 get / find 并从 get 操作返回的对象开始迭代。迭代器应该按照元素插入数据结构的相同顺序进行迭代。

我可以使用 TreeSet 实现这一点吗？还是其他数据结构？

谢谢！

4

3 回答 3

1

如果您从 a 开始SortedMap<Integer, Object>并使用键来跟踪插入顺序，您将能够使用快速tailMap操作来满足您的需要。

如果您需要通过键（或者可能通过对象本身）找到对象的位置，那么引入另一个WeakHashMap<Object, Integer>将从您的键映射到对象位置的方法。然后，您将使用检索到的序列号作为前一个映射的键。

于 2012-07-09T14:23:22.710 回答
1

此答案假定您希望按值获取/查找项目，而不是按插入序列号访问。我假设这个值与插入项目的顺序完全无关。

与标准 Java 基础类最接近的是LinkedHashSet。这允许按插入顺序进行快速搜索和迭代。但它不会给你一个从给定位置开始的迭代器，所以你必须自己实现它。要么基于LinkedHashSet，要么使用您自己的 set 实现。我想最简单的方法是使用 aHashSet并自己实现链接。这样，您可以使用 set 方法查找起始元素，并使用它在链接之后构造一个迭代器。您可以将链接隐藏在包装器对象中，因此您不必在 API 中公开它们。

于 2012-07-09T14:25:35.173 回答
0

如果您使用的是 Java 6，则可以查看ConcurrentSkipListSet和ConcurrentSkipListMap。

于 2012-07-09T14:22:48.327 回答