LinkedHashMap按索引删除的性能分析及Java8/9优化方案咨询

首先直接回答你的第一个问题：两种方案的时间复杂度确实都是O(n)，我们来拆解一下细节：

• 方案1：把keySet()转为ArrayList的过程需要遍历整个LinkedHashMap的所有键，这一步是O(n)；后续的get(position)是ArrayList的O(1)操作，remove(key)是LinkedHashMap基于哈希表的O(1)操作，整体复杂度由遍历步骤主导，最终为O(n)。缺点是会额外创建一个包含所有键的ArrayList，大数据量下内存开销会很明显。
• 方案2：通过循环遍历entrySet()直到找到对应索引的元素，最坏情况下需要遍历整个集合（比如删除最后一个元素），所以也是O(n)。虽然没有额外内存开销，但遍历的时间成本在大数据量下依然很高。

接下来聊聊Java 8/9能不能给出更优的实现——遗憾的是，从时间复杂度上来说，没办法做到比O(n)更好，因为LinkedHashMap的底层是哈希表+双向链表，但它并没有暴露链表的节点或索引直接访问的接口，所以不管用什么方式，按索引查找元素都需要遍历到对应位置。不过Java 8的Stream API可以让代码更简洁优雅，性能上和方案2相当：

public boolean removeItem(int position) {
    return items.entrySet()
                .stream()
                .skip(position)
                .findFirst()
                .map(entry -> items.remove(entry.getKey()) != null)
                .orElse(false);
}

这段代码用skip(position)跳过前position个元素，findFirst()获取目标entry，然后执行删除操作。本质上和方案2的遍历逻辑一致，只是用Stream的方式简化了代码，可读性更好。

如果你的场景需要频繁按索引进行访问或删除操作，其实LinkedHashMap并不是最适合的选择。你可以考虑自己封装一个组合结构：用ArrayList存储有序的键，同时维护一个HashMap<K,V>来映射键值对。这样：

• 按索引获取键：arrayList.get(position)，O(1)
• 按索引删除：map.remove(arrayList.remove(position))，删除ArrayList元素的时间是O(n)（因为需要移动后续元素），但如果删除操作不频繁，这个结构会比LinkedHashMap更高效。

最后补充一点：Java 9并没有针对LinkedHashMap的索引操作新增API，所以核心优化还是基于Java 8的Stream来简化代码，或者考虑更换更适合的数据结构。

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