Java - HashSet contains() method is not working?

Question

I am having trouble with HashSets. My program performs a Breadth First Search and I made a hashset to keep track of visited states. States are represented by int[] array. However, HashSet's contains method does not seem to be working as expected. Basically, it is not filtering out int[] arrays that should already have been added.

Here are the relevant parts of my code:

private boolean notVisitedAndNotNull(PuzzleState nextPS) {
    if (nextPS != null && !this.visited.contains(nextPS.getStateArray)) 
        return true;
    return false;
}

private void addToQueue(PuzzleState nextPS) {
    if (notVisitedAndNotNull(nextPS))
        queue.add(nextPS);
}

private boolean solveByBFS() {
    queue.clear();
    queue.add(this.initialState);
    long startTime = System.currentTimeMillis();

    while(!queue.isEmpty()) { 
        if (queue.size() > maxQueueSize)
            maxQueueSize = queue.size();

        this.currentState = queue.poll();

        if (this.currentState.equals(finalState)) { 
            System.out.println("Successful! Ending Time: " + startTime);
            return true;
        }

        visited.add(this.currentState.getStateArray()); //this adds int[] array

        this.addToQueue(this.currentState.moveUp());
        this.addToQueue(this.currentState.moveDown());
        this.addToQueue(this.currentState.moveRight());
        this.addToQueue(this.currentState.moveLeft());

    }
    return false;
}

I apologize for posting so much code. I searched a bit and it seems that in order for HashSet to work correctly, I would have to implement hashCode and equals of HashSet. I'm not sure if this is possible for an int[] array. Is it better to just use a HashMap then and use toString method on int[] array to serve as a key?

Ok, I got this working now. Here is the code I added if anyone is interested:

@Override
public boolean equals(Object o) {
    if (o instanceof PuzzleState) {
        return (Arrays.equals(((PuzzleState) o).getStateArray(), this.getStateArray()));
    }
    return false;
}

@Override
public int hashCode() {
    return Arrays.hashCode(this.getStateArray());
}

Have you changed the `PuzzleState` `equals` and/or `hashCode` methods, if so, how...? — MadProgrammer, Sep 12 '14 at 03:38
@MadProgrammer I'm doing that right now. I understand the problem now. Thank you — mrQWERTY, Sep 12 '14 at 03:48
Also would I have to override both? Or do I just have to override one? For instance, I don't think its necessary to override 'hashCode' but it is necessary to override 'equals'. — mrQWERTY, Sep 12 '14 at 03:54
Yes. There is a contractual requirement between `hashCode` and `equals` — MadProgrammer, Sep 12 '14 at 03:56

score 2 · Accepted Answer · edited May 23 '17 at 12:05

2

Array equality is by reference only. You are asking if the set contains exactly the same array object, it does not examine the contents of the array to see if a "similar" array exists.

Community

1
1

answered Sep 12 '14 at 03:38

William Price

4,033
1
35
54

Interesting, because if I create an `Class` and override it's `equals` and `hashCode`, I can add once instance of the `Class` to the `HashSet` and use another instance in `contains` and it will return `true`... – MadProgrammer Sep 12 '14 at 03:54
Yes, but Java's `int[]` doesn't implement `equals` and `hashCode` in a way that would work as such. From the OP's code: `visited.add(this.currentState.getStateArray()); //this adds int[] array` – William Price Sep 12 '14 at 03:56

Java - HashSet contains() method is not working?

1 Answers1