How to efficiently compare two lists of Products

Question

I'm trying to write a method that checks in an efficient way if 2 lists of products are equals.

List firstList = getProductsListFromSomewhere();
List secondList = getProductsListFromSomewhereElse();

public boolean areListsEqual(List firstList, List secondList) {
    ...
}

Constraints and conditions

The same product can appear multiple times in the list. Ex. (Product A, Product B, Product A, Product C)
This could represent a problem if I use an HashSet to store the content of the first list and then parse the second list to check if each Product is in the set because I can't put duplicates in the HashSet.
The two lists are considered equals if they contains the same products and those appear the same number of times but their order is NOT relevant.
So for example those two lists
(Product A, Product B, Product A, Product C)
(Product C, Product A, Product A, Product B)
are considered equals.

But those two
(Product A, Product B, Product A, Product C)
(Product A, Product B, Product C)
are considered different

The object Product is defined as follows (note its code is autogenerated so I can't write the methods equals and hashcode inside its class)

class Product {
    private String name;
    private Integer quantity;
    private List discountsList;

    //some other field not needed for the comparison
}

Two products are considered equals if they have the same name, the same quantity and the same discountsList
Also for the lists of discounts comparison the element's order is NOT relevant
Discount is defined like this (also in this case the class is autogenerated and I can't write the methods equals and hashcode)
```
class Discount {
    String code;

    //some other field not needed for the comparison
}
```
Two discounts are considered equals if they have the same code

Requirements and preferences

The comparison has to be efficient (I guess I have to use some kind of hashing)
The code should be as clean as possible (I would prefer to avoid to use things like reflection to parse the structure etc)
If possible I would prefer NOT to use external libraries

My (not valid :( ) approach
I started to write a draft of a possible solution but I found different blockers to my approach and I don't know if I should refine it in some way or completely rethink about it.
My idea is to extend the Product class inside the class that should perform the comparison:

List firstList = getProductsListFromSomewhere();
List secondList = getProductsListFromSomewhereElse();

public boolean areListsEqual(List firstList, List secondList) {
    ...
}  

private class ComparableProduct extends Product {

  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final ComparableProduct other = (ComparableProduct)obj;
    if (!Objects.equals(this.name, other.name)) {
      return false;
    }
    if (!Objects.equals(this.quantity, other.quantity)) {
      return false;
    }
    if (!Objects.equals(this.discountList, other.discountList)) {
      return false;
    }
    return true;
  }

  @Override
  public int hashCode() {
    int hash = 3;
    hash = 79 * hash + Objects.hashCode(this.name);
    hash = 79 * hash + Objects.hashCode(this.quantity);
    hash = 79 * hash + Objects.hashCode(this.discountList);
    return hash;
  }
}

This approach obviously doesn't work because the Discount object is compared without defining the equals and hashCode methods but I can't extend Discount because the discountList defined in the Product object is of Discount type so I can't use the ComparableDiscount eventually created.
Furthermore I don't know exactly what is the best way/data structure to use, once the hashing mechanism is defined, to check that the two lists are equals

Would you help me to complete this part of code in the best possible way?

user_585411 · Answer

The easiest approach is to write a function that takes a Product and generates a unique string representation of it. Be sure that if you consider two the same, you must get the same string out. (For example sort the discount codes.)

Now you can turn a List of Product objects into a List of strings. You can now compare two of these lists fairly easily.

One tip if these can be big is to actually work with an MD5 hash of the description rather than the description itself. Those will be shorter and the odds of a collision are astronomically low.

If you want to actually identify the differences, you should store a map of the string representing the product to the product object. That way once you know which strings are in one list but not the other, then you can turn strings back into objects before returning them.

How to efficiently compare two lists of Products

1 Answers