Java nested loops prevent duplicate

Question

This object is a pack of gum. Every gum is of a unique kind. We set up a pack that can hold 12 gums. We populate the pack with new gum objects. We must check the pack to see if this kind of gum has already been put in the pack. Each gum in the pack must be of a unique kind.

public PackOfGum()
{
  pack = new Gum[12];
  // Successfully populate pack with gum
  for (int i=0; i<12; i++) {
    pack[i] = new Gum();


    // Failure preventing duplicate gums. Idea is to look in the pack
    // at all of the gums that came before this one, and see if this one
    // matches any of them. While yes and it is a duplicate, then choose
    // a new gum.
    for (j=0; j<i; j++) {
      while (pack[i] == pack[j]) {
        pack[i] = new Gum();
      }
    }
  }
}

I'm failing to correctly check all of the previous gums and compare them to the current gum. How should this be done properly?

I'm not sure I understand your question correctly. But if you just want to store a non duplicate collection of guns then you can use java.util.Set for storing it. You will need to implement the equals method in the Gum class for defining the equality condition. — Arun Iyer, Sep 21 '16 at 02:37
A question: how do you compare Gum objects? using its memory address or its value? — MaxZoom, Sep 21 '16 at 02:40
what is the definition of "kind" of gum? You are now comparing if two Gum reference is referring to same Gum object instance. Given that you are creating a new Gum instance for every element in the array, it will always be different. — Adrian Shum, Sep 21 '16 at 04:35

score 1 · Answer 1 · edited May 23 '17 at 12:32

You need to provide your own implementation of equals() in your Gum class.

@Override
public boolean equals(Object other) 
{
    if (!(other instanceof GumClass))
    {
        return false;
    }
    GumClass that = (GumClass) other;
    // Custom equality check here.
    return this.field1.equals(that.field1)
     && this.field2.equals(that.field2);
}

You should also override hashCode() if there's any chance of your objects being used in a hash table. A reasonable implementation would be to combine the hash codes of the object's fields with something like:

@Override
public int hashCode() 
{
    int hashCode = 1;
    hashCode = hashCode * 37 + this.field1.hashCode();
    hashCode = hashCode * 37 + this.field2.hashCode();
    return hashCode;
}

See this question for more details on implementing a hash function

@Hector Implementing `hashCode` without implementing `equals` doesn't break the contract. Although it is kind of silly. — ajb, Sep 21 '16 at 03:40

score 0 · Answer 2 · answered Sep 21 '16 at 03:30

There are a number of things missing from your question. For one thing, since you haven't given us the Gum class, I can't figure out how each new Gum() is going to create a unique Gum. Does Gum have some kind of flavor instance variable that gets initialized to a random flavor? Maybe, but you haven't given us that info. Also, as the other answer points out, using == to compare gums isn't going to work. Assuming that each Gum has a flavor, you will need to provide an equals() method that compares the flavor fields for equality (and a hashCode function that returns the same hash value for any Gum objects with the same flavor).

The problem I most wanted to point out was the flaw in your loop logic. You're going through the array of existing Gum objects, and whenever you find a duplicate, you create a new Gum. That won't get the job done. Suppose your array consists of flavors A, B, C, D, E. Suppose your new Gum() generates a gum with flavor C. You go through the array, and you find that it matches pack[2]. So you generate another Gum--say your random Gum generator generates a Gum with flavor B. Now your loop won't find it, since you're still going forward through the array, and you will only be looking at D and E. So you'll end up with a duplicate in your pack.

So what do you do? One option is that whenever you find a duplicate, you generate a new Gum and then start over at the beginning of the array. That's a pretty slow way to do things, but it will work. Some better options:

Maintain a Set of all the Gum's that are already in the pack. Now instead of going through the array to see if a Gum is a duplicate, just see if the set contains it. If you use a HashSet, you'll be able to do this test in constant time instead of searching through an array. (If you use a HashSet, you will definitely need a working hashCode function.)
Keep an array of all the Gum flavors that haven't been used. If you start with 12 flavors, then the first new Gum() will use a random number from 0 to 11, the second will use a random number from 0 to 10, the third from 0 to 9, and so on. Each time, you will use the array and the random number to choose the right flavor, then do a swap to move that flavor to the end of the array. For example, if the array starts out A,B,C,D,E,F,G,H,I,J,K,L and your random number is 4, that's flavor E, and you swap that with L to make your array A,B,C,D,L,F,G,H,I,J,K,E. The next random number only goes from 0 to 11, so it won't pick E. Whatever it does pick, you swap that with K. And so on.

Java nested loops prevent duplicate

2 Answers2