如何在Java TreeMap中从指定key开始迭代，获取大于给定值的最小K个key

确实存在时间复杂度为O(logn + K)的高效实现，核心是利用TreeMap的范围视图特性与顺序迭代能力，不需要额外复制大量元素。 #

常见误解澄清 #

很多开发者认为tailMap开销过大，其实是对Java TreeMap实现的误解：TreeMap的tailMap/headMap/subMap返回的都是轻量视图，不会复制底层的任何元素，仅会存储原Map的引用、范围边界参数，创建开销为O(1)，仅在内部定位范围起始点时产生一次O(logn)的查找成本。 #

最优实现代码 #

直接获取tailMap的 entry 迭代器，遍历K次即可：

import java.util.*;

public class TreeMapHelper {
    public static <K extends Comparable<K>, V> List<Map.Entry<K, V>> getKMinEntriesAfter(TreeMap<K, V> originMap, K givenValue, int k) {
        List<Map.Entry<K, V>> result = new ArrayList<>(k);
        // 第二个参数false表示不包含等于givenValue的元素，对应"大于指定值"的要求
        Iterator<Map.Entry<K, V>> tailIterator = originMap.tailMap(givenValue, false).entrySet().iterator();
        
        while (tailIterator.hasNext() && result.size() < k) {
            result.add(tailIterator.next());
        }
        return result;
    }
}

时间复杂度分析 #

• 调用tailMap时，内部定位起始元素的查找开销为O(logn)
• TreeMap的迭代器是基于红黑树的中序遍历实现，每次next()操作的平摊时间复杂度为O(1)，K次迭代总开销为O(K)
• 整体时间复杂度为O(logn + K)，符合要求，且仅会产生存储K个结果的额外内存开销。

不使用tailMap的替代实现 #

如果不想调用tailMap，也可以通过higherKey配合迭代器实现，但性能和上面的方案没有本质差异：

public static <K extends Comparable<K>, V> List<Map.Entry<K, V>> getKMinEntriesAfter(TreeMap<K, V> originMap, K givenValue, int k) {
    List<Map.Entry<K, V>> result = new ArrayList<>(k);
    K currentKey = originMap.higherKey(givenValue);
    if (currentKey == null) {
        return result;
    }
    Iterator<Map.Entry<K, V>> iterator = originMap.entrySet().iterator();
    // 先定位到currentKey对应的entry位置
    while (iterator.hasNext()) {
        Map.Entry<K, V> entry = iterator.next();
        if (entry.getKey().equals(currentKey)) {
            result.add(entry);
            break;
        }
    }
    // 继续迭代剩下的K-1个元素
    while (iterator.hasNext() && result.size() < k) {
        result.add(iterator.next());
    }
    return result;
}

注意：这种方案需要额外的遍历定位起始位置，不如直接使用tailMap的方式简洁高效

内容的提问来源于stack exchange，提问作者ChuNan