java LinkedHashMap访问（按索引与性能）

Question

我想讨论一点特定集合LinkedHashMap针对特定需求的性能，以及Java8或Java9的新特性如何在这方面有所帮助

假设我有以下LinkedHashMap：

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

使用默认构造函数意味着该映射在迭代时遵循插入顺序

--编辑-- 这里要明确的是，我知道映射不是通过索引访问的正确数据结构，碰巧这个类实际上需要两个删除方法，一个是按产品，按正确的方式，这是键，另一个是按位置，或索引，这不是常见的，所以我关心的是性能。顺便说一句，这不是我的要求

我必须通过索引实现一个removietem（）方法。对于那些不知道的人，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;
}

关于这两种解决方案的考虑

S1:我知道ArrayList具有快速迭代和访问功能，因此我认为这里的问题是正在创建一个全新的集合，因此如果我有一个巨大的集合，内存将受到影响

S2:我知道LinkedHashMap的迭代速度比HashMap快，但不如ArrayList快，因此我相信如果我们有大量的集合，而不是内存，这里的迭代时间会受到影响

考虑到所有这些，并且我的考虑是正确的，我能说这两种解决方案都有O（n）复杂性吗

使用Java8或Java9的最新特性，在性能方面是否有更好的解决方案

干杯

Answer 1

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

对。平均复杂度是相同的。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?

Java8和Java9没有提供任何性能改进

如果您想要比O（N）平均复杂度更好，则需要不同的数据结构

另一件需要注意的事情是，索引地图的条目集通常不是一件有用的事情。每当从集合中删除一个条目时，其他条目的部分的索引值将发生变化

很难有效地模仿这种“不稳定”的索引行为。如果您想要稳定的行为，那么可以使用用于位置查找/插入/检索的HashMap<Integer,K>来扩充主HashMap<K,V>/LinkedHashMap<K,V>。但即使这样也有点尴尬。。。考虑如果需要在i和i + 1位置的条目之间插入新条目会发生什么情况

Answer 2

As said by 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值，可以简化逻辑：

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;
}

您可以使用流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;
}