LinkedHashMap 按索引访问与性能

Question

我想讨论一下特定 collection、LinkedHashMap 的性能，以满足特定需求，以及 Java 8 或 9 个新功能如何帮助解决这个问题。

假设我有以下 LinkedHashMap:

private Map<Product, Item> items = new LinkedHashMap<>();

使用默认构造函数意味着此 Map 在迭代时遵循 insertion-order。

--已编辑-- 在这里要说清楚，我知道地图不是索引访问的正确数据结构，碰巧这个class实际上需要两种删除方法，一种是通过产品，正确的方法，哪个是关键，另一个是位置或索引，这并不常见，所以这是我对性能的关注。顺便说一句，这不是我的要求。

我必须通过 index 实现 removeItem() 方法。对于那些不知道的人，LinkedHashMap 没有有某种可用的 map.get(index); 方法。

所以我将列出几个解决方案：

方案一：

public boolean removeItem(int position) { List<Product> orderedList = new ArrayList<>(items.keySet()); Product key = orderedList.get(position); return items.remove(key) != null; }

方案二：

public boolean removeItem(int position) { int counter = 0; Product key = null; //assuming there's no null keys for(Map.Entry<Product, Item> entry: items.entrySet() ){ if( counter == position ){ key = entry.getKey(); break; } counter++; } return items.remove(key) != null; }

关于这 2 个解决方案的注意事项。

S1: 我知道 ArrayLists 有快速迭代和访问，所以我相信这里的问题是正在创建一个全新的 collection，所以内存如果我有一个巨大的 collection.
就会受到损害
S2: 我知道 LinkedHashMap 迭代比 HashMap 快但不如 ArrayList 快，所以我相信如果我们有巨大 collection，但不是内存。

考虑到所有这些，并且我的考虑是正确的，我可以说这两种解决方案都具有 O(n) 复杂度吗？

对于这种情况，在性能方面是否有更好的解决方案，使用 Java 8 或 9 的最新功能？

干杯！

Answer 1

Considering all of that, and that my considerations are correct, can I say that both solutions have O(n) complexity?

是的。平均复杂度是 same.m 在第一个解决方案中，new ArrayList<>(entrySet) 步骤是 O(N)。

在第二个解决方案中，循环是 O(N)。

虽然最佳情况的复杂性有所不同。在第一个解决方案中，您总是复制整个列表。在第二个解决方案中，您只需要迭代到什么程度。所以最好的情况是它可以在第一个元素处停止迭代。

但是虽然这两种情况的平均复杂度都是 O(N)，但我的直觉是第二种解决方案最快。（如果这对您很重要，请对其进行基准测试...）

Is there a better solution for this case in terms of performance, using the latest features of Java 8 or 9?

Java 8 和 Java 9 没有提供任何性能改进。

如果您想要更好的 O(N) 平均复杂度，您将需要不同的数据结构。

另一件需要注意的事情是，索引 Map 的条目集通常不是一件有用的事情。每当从集合中删除一个条目时，其他条目的 some 的索引值 change ....

有效地模仿这种 "unstable" 索引行为很困难。如果你想要稳定的行为，那么你可以用一个 HashMap<Integer,K> 来增加你的主要 HashMap<K,V> / LinkedHashMap<K,V> ，你可以用它来进行位置查找/插入/检索。但即使这样也有点尴尬......考虑如果你需要在位置 i 和 i + 1.

的条目之间插入一个新条目会发生什么

Answer 2

，时间复杂度是一样的，都是线性迭代，但是效率还是有区别的，因为第二种变体只会迭代到指定的元素，而不是创建完整副本。

您可以通过在找到条目后不执行额外的查找来进一步优化它。要使用指向 Map 中实际位置的指针，您必须显式使用它的 Iterator：

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.values().iterator();
    for(int counter = 0; counter < position; counter++) it.next();
    boolean result = it.next() != null;
    it.remove();
    return result;
}

如果键映射到 null，这将遵循原始代码的逻辑 return false。如果地图中从来没有 null 个值，则可以简化逻辑：

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.entrySet().iterator();
    for(int counter = 0; counter <= position; counter++) it.next();
    it.remove();
    return true;
}

您可以使用 Stream API 检索特定元素，但随后的 remove 操作需要查找，这使得在已经有的迭代器上调用 remove 效率较低大多数实现中对地图中位置的引用。

public boolean removeItem(int position) {

    if(position >= items.size() || position < 0)
        return false;

    Product key = items.keySet().stream()
        .skip(position)
        .findFirst()
        .get();

    items.remove(key);
    return true;
}

LinkedHashMap 按索引访问与性能

LinkedHashMap access by index vs Performance

java

performance

linkedhashmap

java-8

java-9