如何用Java的Map优化员工列表匹配，将O(N²)降至O(N)时间复杂度

问题描述 #

我有两个EmployeeDatas类型的列表：

List<EmployeeDatas> allEmployees;
List<EmployeeDatas> currentEmployees;

class EmployeeDatas {
    String name;
    String lastName;
    String joiningDate;
    String promotionDate;
}

需求是对比两个列表，判断是否存在四个字段完全匹配的元素，存在返回true，否则返回false。原来的实现用了双层嵌套循环，时间复杂度为O(N²)：

for (EmployeeDatas allEmployee : allEmployees) {
    for (EmployeeDatas currentEmployee : currentEmployees) {
        if (allEmployee.name.equals(currentEmployee.name) &&
            allEmployee.lastName.equals(currentEmployee.lastName) &&
            allEmployee.joiningDate.equals(currentEmployee.joiningDate) &&
            allEmployee.promotionDate.equals(currentEmployee.promotionDate)) {
            return true;
        }
    }
}
return false;

想问能不能用Map把时间复杂度优化到O(N)？

解决方案 #

当然可以，甚至用HashSet会比Map更简洁（本质和Map的键查找逻辑一致），核心是先让EmployeeDatas正确重写equals()和hashCode()方法，这样才能正确判断两个对象是否“字段完全匹配”。

步骤1：重写EmployeeDatas的equals和hashCode #

Java默认的equals()比较对象引用，我们需要改成按四个字段的值判断相等；hashCode()要和equals()保持一致，才能正确放入哈希集合/哈希表：

class EmployeeDatas {
    String name;
    String lastName;
    String joiningDate;
    String promotionDate;

    // 按需添加构造方法、getter/setter

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        EmployeeDatas that = (EmployeeDatas) o;
        return Objects.equals(name, that.name) &&
               Objects.equals(lastName, that.lastName) &&
               Objects.equals(joiningDate, that.joiningDate) &&
               Objects.equals(promotionDate, that.promotionDate);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, lastName, joiningDate, promotionDate);
    }
}

提示：可以直接用IDE自动生成这两个方法，避免手动编写出错。

步骤2：用HashSet实现O(N)复杂度的匹配逻辑 #

把其中一个列表转成HashSet，然后遍历另一个列表检查元素是否存在：

public boolean hasMatchingEmployee(List<EmployeeDatas> allEmployees, List<EmployeeDatas> currentEmployees) {
    // 构建HashSet，时间复杂度O(M)，M为allEmployees的长度
    Set<EmployeeDatas> allEmployeeSet = new HashSet<>(allEmployees);
    
    // 遍历currentEmployees，每个元素查找时间O(1)，总时间O(N)
    for (EmployeeDatas emp : currentEmployees) {
        if (allEmployeeSet.contains(emp)) {
            return true;
        }
    }
    return false;
}

如果一定要用Map实现 #

逻辑和Set一致，把元素作为Map的键，值用任意占位符即可：

public boolean hasMatchingEmployeeWithMap(List<EmployeeDatas> allEmployees, List<EmployeeDatas> currentEmployees) {
    Map<EmployeeDatas, Boolean> employeeMap = new HashMap<>();
    for (EmployeeDatas emp : allEmployees) {
        employeeMap.put(emp, Boolean.TRUE);
    }
    
    for (EmployeeDatas emp : currentEmployees) {
        if (employeeMap.containsKey(emp)) {
            return true;
        }
    }
    return false;
}

时间复杂度分析 #

• 构建Set/Map的时间为O(M)（M是第一个列表的长度）
• 遍历第二个列表的时间为O(N)（N是第二个列表的长度）
• 总时间复杂度为O(M+N)，属于O(N)级别，比原O(M*N)的嵌套循环高效很多，元素越多优化效果越明显。

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