时间戳

首页 > 解决方案 > LinkedHashMap 按索引访问与性能

java - LinkedHashMap 按索引访问与性能

问题描述

我想讨论一下针对特定需求的特定集合 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;
}

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

S1：我知道 ArrayLists 具有快速迭代和访问，所以我认为这里的问题是正在创建一个全新的集合，所以如果我有一个巨大的集合，内存会受到影响。

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

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

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

干杯!

标签： javaperformancejava-8java-9linkedhashmap

解决方案

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

推荐阅读