按索引访问 LinkedHashMap 与性能

Question

我想讨论一个特定集合 LinkedHashMap 的一些性能，以满足特定要求，以及 Java 8 或 9 的新特性如何对此有所帮助。

假设我有以下 LinkedHashMap：

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

使用默认构造函数意味着此 Map 在迭代时遵循插入顺序。

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

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

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

解决方案1：

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

    return items.remove(key) != null;
}

解决方案2：

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 具有快速迭代和访问，所以我相信这里的问题是正在创建一个全新的集合，所以如果我有一个巨大的集合，内存会受到影响。

S2：我知道 LinkedHashMap 迭代比 HashMap 快，但不如 ArrayList 快，所以我相信如果我们有一个巨大的集合，这里的迭代时间会受到影响，而不是内存。

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

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

干杯!

Answer 1

正如 Stephen C 所说，时间复杂度是相同的，因为在任何一种情况下，你都有一个线性迭代，但效率仍然不同，因为第二个变体只会迭代到指定的元素，而不是创建一个完整的副本。

您可以通过在找到条目后不执行额外查找来进一步优化它。要使用指向 中实际位置的指针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;
}

这遵循原始代码的逻辑，false如果键被映射到null. 如果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;
}