1

I am being challenged (or confused) by this problem:

I have a List<CustomObject> in which each element has around 20 fields/attributes. In this list I might have sort of duplicate items. Four particular fields may be different, if the others match I would regard them to be equal enough and I want to merge them into a single element.

The question is how to identify these "sort of duplicate" elements. Here are a few approaches I am thinking of:

  1. Use a HashMap and use a concatenated string of all similar attributes as "key". Then store the "sort of duplicates" in separate lists per "key". The problem I feel is that the key values will be quite big (like around 3000+ characters, this could be clumsy).

  2. Override the Equals method and make a Set<CustomObject> to store the CustomObject. If it exists, override the 4 fields based on business logic and save this new object. A lookup cost for if exists.

  3. N x N approach. Looping through N x N doesn't make sense to me and will become expensive as the number of items in the list increases.

I would appreciate any other thoughts on how resolve this.

5
  • Merging, as stated in the title, appears not to be the issue, but rather detecting which records are duplicates (modulo differences). The issue seems to be more that of having a viable primary key, which could be a collection of real-world items or a unique computer generated id. I would study this from a database perspective and user-id perspective as these domains have to address the same.
    – Erik Eidt
    Mar 13, 2022 at 0:48
  • By "except 4 fields every field would be same" do you mean that any 4 fields are not required to match between similar object, or that 4 specific fields (the same for all objects) are not required to match? If the latter, I may need to amend my answer. Mar 13, 2022 at 18:16
  • @DavidPement "these 4 fields are specific". In other words, I know what these fields are.
    – kosa
    Mar 13, 2022 at 21:37
  • @ErikEidt I agree. This should be well addressed in database, unfortunately it was not well designed and not in a position to refactor the DB, so trying to see if I we can address this at application layer. Thanks!
    – kosa
    Mar 13, 2022 at 21:38
  • 1
    @kosa I updated my answer based on your feedback. Mar 14, 2022 at 3:25

3 Answers 3

1

Edited to address the issue of 4 specific fields allowed to mismatch.

@Hans-Martin Mosner is right that the remaining fields form a unique key. It's best to address this with the database, but it sounds like you can't in your circumstances. In this case, Option 1 seems to be the superior choice.

Option 3 is obviously undesirable because of its O(N^2) complexity, but why not Option 2? The main reason is that once we add an object to a set, we cannot retrieve it without iterating through the collection at O(N). So there's no way to "merge" two equal objects in O(1) (the main reason for preferring 2 to 3), other than simply replacing the existing object. This doesn't sound like what you wanted. You can use a modified form of Option 2 by using a HashMap<CustomObject, CustomObject>, but this is basically Option 1 except you're not keeping a list.

So what does this key look like?

If you want the key to be a CustomObject (for either Option 1 or modified Option 2), then we'll need to override hashCode() to use all and only the fields that we care about (e.g. like this). This is an especially nice option if you've already overridden equals(obj).

If you want a String key, then you can concatenate all the field values that we care about (including a separator to prevent values from one field flowing into another). E.g. assuming that field1, ... fieldN have a suitable toString():

String getKey(CustomObject obj) {
   return obj.getField1() + "|" + ... + "|" obj.getFieldN();
}

Original answer assuming any 4 fields were allowed to mismatch.

As ugly as it seems, I think the most viable algorithm proposed is Option 3*. Here's why.

The Problem of Option 1

Let's suppose we have our list and we're going through elements one by one. We encounter the problem on the first element. How do we even know what the "concatenated string of all similar attributes" is for this element? We have nothing to compare against. In order to determine this, we need to scan through the rest of the elements and compare them to this particular element. It's up to you if we break once we find a match, or look for a better candidate / all candidates.

Okay, on to the next element. If it was marked as a duplicate already, then we might be able to skip this. Otherwise, then we are in exactly the same situation as before: we have to run through each of the subsequent elements looking for a potential match.

(You see where this is going, don't you?)

The Problem of Option 2

So you've decided to stick our objects in a Set. Great, we've got 2 popular choices: a HashSet and a TreeSet.

If we choose a HashSet, then we need to define a hashcode, particularly one such that equal objects have the same hashcode. Because of our fuzzy version of equality, defining a suitable hashcode is going to be really difficult. Given what I know of the problem, the only consistent hash seems to be a constant. (You may be able to do better, but it's not an easy task.) Practically this means that set.contains(myObj) will have linear lookup time, so we're back to O(N^2) for overall complexity.

If we choose a TreeSet, then we need to define an ordering. Again, good luck with finding one that works with our fuzzy equality. Worst case for this will also give us linear lookup time.

Aside

The problem of detecting duplicates is hard. For example, what potential duplicates do we have among this data?

A = { a: 1, b: 1 }, B = { a: 1, b: 2 }, C = { a: 2, b: 1 }, D = { a: 2, b: 2 }

Pairwise, A and D are each similar to both B and C. But B and C are not similar to each other; nor are A and D similar.

*Technically, option 3 takes N(N+1)/2 steps and not N^2, but I'm assuming that you are referring to the big-O.

2
  • My only concern is, with option1, the "key string" (which is combination of all other fields except the 4) would be around 2000+ characters. I am thinking does it make sense to have a key with that much length. Thoughts?
    – kosa
    Mar 14, 2022 at 16:20
  • 1
    You'd have to benchmark it to say for sure, but at that point it seems better to use a CustomObject key with a good hashcode. Mar 14, 2022 at 16:34
4

This sort of problem is much easier solved if you know the meaning of those records and the process by which duplicates happen. Look at the actual fields and decide which ones should be "keys" and which ones should be "values", then you have basically solved it (you need to decide on a proper database representation but that's an implementation issue).

So if you already know the 4 fields that are variable, all others constitute the primary key. You could either simply concatenate them to form a hash key, or build a hierarchical map structure, or let a relational database engine figure out the details. All of these might be viable solutions depending on your problem details which you omitted from the question.

5
  • Thank you! "cocatenate them to form a hash key", you mean create a hash from the "concatenated string" and use it as map key?
    – kosa
    Mar 13, 2022 at 21:41
  • Yes, probably concatenate using some separators so that ('userK', 'osaka') and ('userKosa', 'ka') don't yield the same hash key. With hash key I don't mean that you should hash the key, but that the key is used in a hashmap (which does the hashing to find an entry quickly but also does a true equality comparison to differentiate between entries having different keys that yielded the same hash). Mar 14, 2022 at 15:23
  • My only concern is, with option1, the "key string" (which is combination of all other fields except the 4) would be around 2000+ characters. I am thinking does it make sense to have a key with that much length. Thoughts?
    – kosa
    Mar 14, 2022 at 16:20
  • 2000+ characters for about 16 fields? ~120 characters per field? WTH are you doing? It would be really helpful to know the semantics of your records, this looks rather unusual, and I doubt that you will get an answer fitting the problem if you keep all the problem details secret. Mar 14, 2022 at 22:52
  • 6 fields are date fields, remaining are group codes. Due to nature of sensitivity I can't provide exact details, but I can put it in different form here. We have a line item stored as row in table. Each time someone modifies the 4 fields listed, instead of updating the existing record, new record will be created. Now, the report screen we are working needs to look at all these records (which are replicas of original record) and identify who inserted first and what date as well as who inserted last and last updated date etc.,
    – kosa
    Mar 14, 2022 at 23:12
0

The simplest solution would be to implement a method:

bool EqualsEnough(CustomObject other)
{
    return this.A == other.A &&
        this.B == other.B &&
        ... ;  // compare each property pair that matters
}

This may look expensive but it probably isn't. If you start with pairs that are least likely to match, most comparisons will return early with false.

2
  • Comparing is not a problem. While doing this, which approach works best is what I came for. Overriding equals? Keeping it in Map? loop through all the elements N X N times. Thank you!
    – kosa
    Mar 14, 2022 at 23:16
  • @kosa Just pick the first and look for equal enough others, merge as you go. Repeat with the next. I did not see that to be a problem. May the real question be how to produce a "sort of key/id" ? Mar 15, 2022 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.