如何提升ArrayList中查找并使用重复元素的执行效率

原代码采用嵌套循环实现，时间复杂度为O(n²)，数据量较大时性能会大幅下降；同时后续循环调用ArrayList.remove(Object)方法每次都会触发元素移位操作，也会带来额外的O(n)开销，两部分叠加是运行效率低的核心原因。

核心优化思路 #

• 用HashMap存储已出现的属性对应的首条实例，仅需单次遍历列表即可完成重复识别，时间复杂度降至O(n)
• 直接构建去重后的新列表，一次性覆盖原列表内容，避免多次删除元素的性能损耗

优化后代码 #

注意将代码中的PropertyType替换为你实际的someClassProperty属性的类型：

public int removeDuplicateElements(){
    // key为去重判定属性，value为该属性首次出现的元素实例
    Map<PropertyType, SomeType> firstOccurrence = new HashMap<>();
    List<SomeType> reservedElements = new ArrayList<>();
    int duplicateTotal = 0;

    for (SomeType current : ListWithDuplicates) {
        PropertyType currentProp = current.getProperty();
        if (!firstOccurrence.containsKey(currentProp)) {
            // 该属性第一次出现，加入保留列表
            firstOccurrence.put(currentProp, current);
            reservedElements.add(current);
        } else {
            // 判定为重复，调用对应函数
            firstOccurrence.get(currentProp).someFunction(current);
            duplicateTotal++;
        }
    }

    // 一次性更新原列表，避免多次删除的开销
    ListWithDuplicates.clear();
    ListWithDuplicates.addAll(reservedElements);

    return duplicateTotal;
}

注意事项 #

如果someClassProperty是自定义类型，需要先补全该类的hashCode()和equals()方法，否则HashMap的key匹配逻辑会失效。

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