在Java中比较两个列表的有效方法是什么？

Question

我有一个程序，它从db获取java对象的列表，并将它与已经检索的旧列表进行比较，并找到它中的delta（差异）元素并返回。 我想知道是否有最好的方法来做到这一点，而不是仅仅使用Set方法Union（），Intersection（）等，并避免内存不足的错误？ 列表的大小可以是200k。 我在我的项目中使用Spring 3.2.8.RELEASE版本。

public class Tester { 

    private List<AddressInfo> oldListOfAddresses; 

    @Scheduled(cron="0 1 6 * * ?") // 6 AM everyday 
    public Map<String, AddressInfo> getCompany() { 
     try { 
      Map<String, AddressInfo> companyMap = new HashMap<>(); 
      String sql = "Some sql query which return Address Info."; 
      List<AddressInfo> newListOfAddresses = jdbcTemplate.query(sql, new Object[0], 
        new FacilityNewMapper()); 
      if (newListOfAddresses == null || newListOfAddresses.size() = 0) { 
       throw new FacilityLookUpException("List of clinic Info from facilities is empty..."); 
      } else { 

       // I have to find the delta of new list and old list here. 
       // I need an efficient (Space and Time) way of finding delta. 
       List<AddressInfo> deltaList = newListOfAddresses - oldListOfAddresses; //Something like this 

       for (AddressInfo comp : deltaList) { 
        if (comp != null) { 
         companyMap.put(comp.getLocationId(), comp); 
        } 
       } 
       oldListOfAddresses = newListOfAddresses; 
      } 
      return companyMap; 
     } catch (Exception e) { 
      throw new CompanyLookUpException(
        "List of company addresses is empty..." + e.getMessage()); 
     } 
    } 
} 

AddressInfo bean。

public class AddressInfo{ 

    private String locationId; 
    private String streetName; 
    private String city; 
    private String state; 
    private String country; 

    public String getLocationId() { 
     return locationId; 
    } 
    public void setLocationId(String locationId) { 
     this.locationId = locationId; 
    } 
    public String getStreetName() { 
     return streetName; 
    } 
    public void setStreetName(String streetName) { 
     this.streetName = streetName; 
    } 
    public String getCity() { 
     return city; 
    } 
    public void setCity(String city) { 
     this.city = city; 
    } 
    public String getState() { 
     return state; 
    } 
    public void setState(String state) { 
     this.state = state; 
    } 
    public String getCountry() { 
     return country; 
    } 
    public void setCountry(String country) { 
     this.country = country; 
    } 
    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((city == null) ? 0 : city.hashCode()); 
     result = prime * result + ((country == null) ? 0 : country.hashCode()); 
     result = prime * result + ((locationId == null) ? 0 : locationId.hashCode()); 
     result = prime * result + ((state == null) ? 0 : state.hashCode()); 
     result = prime * result + ((streetName == null) ? 0 : streetName.hashCode()); 
     return result; 
    } 
    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     AddressInfo other = (AddressInfo) obj; 
     if (city == null) { 
      if (other.city != null) 
       return false; 
     } else if (!city.equals(other.city)) 
      return false; 
     if (country == null) { 
      if (other.country != null) 
       return false; 
     } else if (!country.equals(other.country)) 
      return false; 
     if (locationId == null) { 
      if (other.locationId != null) 
       return false; 
     } else if (!locationId.equals(other.locationId)) 
      return false; 
     if (state == null) { 
      if (other.state != null) 
       return false; 
     } else if (!state.equals(other.state)) 
      return false; 
     if (streetName == null) { 
      if (other.streetName != null) 
       return false; 
     } else if (!streetName.equals(other.streetName)) 
      return false; 
     return true; 
    } 

} 

Answer 1

最好的方法确实是使用set操作。将旧列表添加到集合中，将允许您迭代新列表，并且对于每个项目，检查构造的集合是否包含它，如果没有，则将其添加到结果中。这会给你一个O(n*log(n))的运行时间，而不是暴力破解方法的O(n^2)。

Answer 2

我不这么认为（注：我假设列表的顺序没有重要性）。例如，不使用该集合的最快方式是对两个将花费你O（nlogn）的列表进行排序，然后对它们进行迭代比较每个元素并保存那些没有一对的元素。在Set的情况下，基本上遍历每个元素并在第二个集合中查找它，以便迭代为O（n），搜索为O（1）。最后，我们有O（nlogn）> O（n）的一组获胜

Answer 3

假设AddressInfo实现equals和hashCode得当，并在每个列表中的项目是独一无二的，下面的函数可以找到线性时间三角洲：

Set<AddressInfo> findDiff(final List<AddressInfo> newListOfAddresses, final List<AddressInfo> oldListOfAddresses) { 
    Map< AddressInfo, Boolean > map = new HashMap<>(newListOfAddresses.size()); 

    for (AddressInfo addressInfo : newListOfAddresses) { 
     map.put(addressInfo, TRUE); 
    } 

    for (AddressInfo addressInfo : oldListOfAddresses) { 
     map.remove(addressInfo); 
    } 

    return map.keySet(); 
} 

Answer 4

这应该适用于创建两个列表之间的区别。

这里我创建一个集合并添加newList的所有元素。 然后，无论哪个元素是oldList的一部分，我将它们删除。

Set<AddressInfo> findDiffOfTwoList(List<AddressInfo> newList, List<AddressInfo> oldList) { 
    Set<AddressInfo> set = new HashSet<>(); 
    set.addAll(newList); 
    for(AddressInfo address:oldList){ 
     set.remove(address); 
    } 
    return set; 
}