java - 从特定位置(键)向后有效地迭代/子映射 TreeMap

Question

我需要的是一个从请求的键向后包含 n 个条目的值的子列表。由于 map 非常大，我想知道“floorKey”是否是完成此任务的最有效方法。

这段代码可以写得更快吗？

        TreeMap qMap = new TreeMap();
        Object key = "startKey";

        for (int i=0; i<2000; i++) {
            key = qMap.floorKey(key);
        }

        // get a collection holding last 2000 history objects at startkey
        Collection neededValues = qMap.subMap(key, "startKey").values(); 

编辑:

根据@Thilo的回答，我做了一个快速的干燥测试，是的，他的方法更快:

public static void main(String[] args) {
        TreeMap a = new TreeMap();
        for (int i=0; i<5000000; i++) a.put("a"+i, i);

        int i=2000;
        Object dummy;

        System.out.println("start a");
        long start = new Date().getTime();
        NavigableSet keys = (NavigableSet) a.navigableKeySet().headSet("a"+670812); // some random position
        Iterator goBack = keys.descendingIterator();

        while (goBack.hasNext() && i>0) {
            dummy = goBack.next();
            i--;
        }

        System.out.println("run a " + (new Date().getTime() - start));
        System.out.println("start b");

        start = new Date().getTime();
        Object key = "a"+670812;
        for (i=0; i<2000; i++) {
            key = a.floorKey(key);
        }

        Object dummy2 = a.subMap(key, "a" + 670812).values();
        System.out.println("run b " + (new Date().getTime() - start));
    }

打印

start a
run a 6
start b
run b 7

Answer 1

您可以获得 NavigableSet来自您的TreeMap。

类似(没有尝试)

NavigableSet<T> keys = qMap.navigableKeySet().headSet("startKey");
Iterator<T> goBack = keys.descendingIterator();

不确定这是否会对性能产生很大影响。至少它似乎摆脱了对 FloorKey 的 2000 次调用。