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