Java 1.8 : partial traverse of NavigableMap with amortized O(1) to find following entry?

Question

我满足于 O(log n) 第一次操作来找到我的起点

NavigableMap<Double,MyThing> navlevel = new TreeMap<>();

但是在手写的 C++(或者我想是手写的 Java)中，一旦我发现一个指向有问题的 MyThing 的节点，我就可以在该节点上执行“下一个”操作，该操作将分摊到几个指针操作。 (如果有正确的链接，请向右走，然后一直向左走；否则转到您的父级，直到找到来自父级左子节点的节点。)

    Map.Entry<Double,MyThing> entry =
        navthing.ceilingEntry( dSomeValue );

    while ( entry != null ) {

        MyThing level = entry.getValue();

        // Process and break on some condition.

        // vvvvvvvvv This I'm sure is O( log n ) and I want it to be faster!
        entry = navthing.higherEntry( entry.getKey() );
    }

Answer 1

根据您的需要，使用 tailMap 方法或类似方法获取 SortedMap，然后迭代 SortedMap 条目集，如下所示:

NavigableMap<String, String> original = new TreeMap();
original.put("1", "A");
original.put("2", "B");
original.put("3", "C");

//this headmap1 will contain "2" and "3"
SortedMap<String, String> submap1 = original.tailMap("2");
for(Map.Entry<String, String> entry : submap1.entrySet()) {
  String key = entry.getKey();
  String value = entry.getValue();

  System.out.println(key + " => " + value);
}