Java HashSet contains returns false, even with overridden equals() and hashCode()

Question

I initialize the HashSet like this:

private HashSet<Rule> ruleTable = new HashSet<Rule>();

The equals() and hashCode() methods of my TcpRule object (sub-class of abstract class Rule) look like this:

@Override
public int hashCode() {
    // Ignore source Port for now
    return (this.getSrcPool() + ":" + this.getDstPool() + ":" + this.getProtocol() + ":" + this.dstTcp).hashCode();
}

@Override
public boolean equals(Object obj) {
    if (!(obj instanceof TcpRule))
        return false;
    if (obj == this)
        return true;

    TcpRule r = (TcpRule) obj;
    return (this.getSrcPool().equals(r.getSrcPool()) && this.getDstPool().equals(r.getDstPool()) && this.getProtocol().equals(r.getProtocol()) && this.getSrcTcp() == r.getSrcTcp() && this.getDstTcp() == r.getDstTcp());
}

I have even written a simple unit test, which does not give any error:

@Test
public void equalsTest() {
    Pool srcPool = new Pool("PROXY");
    Pool dstPool = new Pool("WEB");
    int srcTcp = 54321;
    int dstTcp = 80;

    TcpRule r1 = new TcpRule(srcPool, dstPool, srcTcp, dstTcp);
    TcpRule r2 = r1;
    assert r1.equals(r2);

    TcpRule r3 = new TcpRule(srcPool, dstPool, srcTcp, dstTcp);
    TcpRule r4 = new TcpRule(srcPool, dstPool, srcTcp, dstTcp);
    assert r3.equals(r4);
}

@Test
public void hashCodeTest() {
    Pool srcPool = new Pool("PROXY");
    Pool dstPool = new Pool("WEB");
    int srcTcp = 54321;
    int dstTcp = 80;

    TcpRule r1 = new TcpRule(srcPool, dstPool, srcTcp, dstTcp);
    TcpRule r2 = new TcpRule(srcPool, dstPool, srcTcp, dstTcp);
    assert r1.hashCode() == r2.hashCode();

    HashSet<Rule> rules = new HashSet<Rule>();
    rules.add(r1);
    assert rules.contains(r1);

    assert rules.contains(r2);
}

In my application, I have an add() method where I simply add a Rule object to the HashSet:

@Override
public void add(Rule rule) {
    ruleTable.add(rule);
}

In another method, I check if a rule exists in the HashSet:

    @Override
public boolean isPermittedTcp(IpAddress sourceAddress, IpAddress destinationAddress, short srcTcp, short dstTcp) {
    Pool sourcePool = poolService.getPool(new Host(sourceAddress));
    Pool destinationPool = poolService.getPool(new Host(destinationAddress));
    Rule r = new TcpRule(sourcePool, destinationPool, srcTcp, dstTcp);
    log.info("Checking: " + r.toString());
    log.info("Hash-Code: " + r.hashCode());
    log.info("Hashes in ruleTable:");
    for(Rule rT : ruleTable) {
        log.info("" + rT.hashCode());
    }
    if(ruleTable.contains(r)) {
        log.info("Hash found!");
    } else {
        log.info("Hash not found!");
    }
    return ruleTable.contains(r);
}

The log messages indicate that the hash of the Rule object (r.hashCode()) is -1313430269, and that one hash in the HashSet (rT.hashCode() in the loop) is also -1313430269. But ruleTable.contains(r) always returns false. What am I doing wrong?

I have found similar questions on StackOverflow, but these mostly involve the equals() or hashCode() methods not being (correctly) overridden. I think I have implemented this two methods correctly.

Atherton

And does rT.equals(r)? – Glenine

Your test uses int whereas your code uses short. Are you sure the objects aren't using ints and you are comparing using shorts? – Foxtrot

your test uses the same instances of Pool, are you sure equals works well on Pool? – Glenine

You have an extra condition in equals this.getSrcTcp() == r.getSrcTcp() which is not part of hash code - maybe thats the issue, hashcode is same, but equals is false – Suricate

@6ton: That's allowed... – Bobbery

It would really help if you'd post a short but complete example demonstrating the problem... – Bobbery

Yep. Your Rule.equals() depends on the equals() for Pool and for whatever getProtocol() returns, and we can't see the code for those. (Or for the get*() methods, for that matter, but I'm assuming those are simple return <field>; getters.) Trim the example down to enough to reproduce the problem in code you can post completely. – Rabjohn

btw, once you figure out your problem, you may want to revise how you implemented your hashCode() method. Concatenating strings to calculate a hashcode is more expensive than it needs to be. Read here for other ideas. – Irremovable

@JonSkeet I posted code in the answer to prove – Suricate

@JonSkeet you are correct, it is allowed. But 6ton's observation is also correct, that the hashcode() method's implementation is leading the OP astray. There is a discrepancy in the OP's thought process, and the discrepancy between hashcode() and equals() illuminates it. Code must do more than satisfy the minimum requirements of the language in order to be considered good. – Leonleona

@ErickG.Hagstrom: To be considered good, I agree - but I'd rather find the cause of the initial problem first, to get to code which works, then improve it. (Red, green, refactor FTW...) – Bobbery

Thank you guys for your answers! 6ton pointed me to the right direction. I'd like to "ignore" srcTcp in the lookup in the ruleTable for now, so I did not included srcTcp in the hashCode()-method. But now I see it too: the equals()-method will fail, even if the hash value is the same, which will return false for the contains()-method. Sorry for wasting your time! – Atherton

Answer 1

Your problem is that hashCode() and equals() do not agree.

Your hashCode() implementation is based on the toString() of the pool, but your equals() uses .equals() of the pool class.

Change your .equals() to compare the strings used to generate the hash code.

Griselgriselda

Answer 2

There are some possibilities:

• Rule is mutable, after adding a rule to the set some key (w.r.t. hash or equals) field was changed;
• If two objects are equal they should have the same hashCode;
• Bug, like a comparison in equals using == i.o. equals.

Here I would guess you have two Pool instances without equals on pool name or hashCode on pool name.

Gym

Answer 3

You have an extra condition in equals this.getSrcTcp() == r.getSrcTcp() which is not part of hash code - maybe thats the issue, hashcode is same, but equals is false. Check if this field is different in the values you are comparing.

Inspite of comments, I think the reason this does not work is because the equals & hashCode implementations do not use the same fields.

Code to simulate the problem:

import java.util.HashSet;

/**
 * @author u332046
 *
 */
public class HashCodeCollisionTest {
    public static class KeyDemo {
        String id;

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((id == null) ? 0 : id.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;
            KeyDemo other = (KeyDemo) obj;
            if (id == null) {
                if (other.id != null)
                    return false;
            } else if (!id.equals(other.id))
                return false;
            return true;*/
            return false;
        }

        public KeyDemo(String id) {
            super();
            this.id = id;
        }
    }

    static HashSet<KeyDemo> set = new HashSet<>();

    public static void main(String[] args) {
        set.add(new KeyDemo("hi"));
        set.add(new KeyDemo("hello"));

        System.out.println(set.contains(new KeyDemo("hi")));
    }
}

This prints false. Uncomment the equals code and it prints true

Suricate

You haven't proved what you think you've proved. Your equals method always returns false, so obviously it's never going to print "true". A better test would be to uncomment all of the code in equals, but make hashCode() return 0 - so the same value for all instances. – Bobbery

Also read the documentation for Object.hashCode: "It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables." – Bobbery

I was trying to make a point that both need to be congruent. HashMap.getEntry does check for equality if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) – Suricate

No, they don't. It's always valid to return 0 from hashCode() for example - that's always a valid but inefficient implementation. It's entirely valid (although unusual) for hashCode() to check fewer fields than equals. The reverse is not true. – Bobbery

Well, its valid but pointless for any practical purpose. I haven't really seen a real world case where you would want them to behave differently – Suricate

I find this funny, because you are both right and wrong. You are wrong that both equals and hashCode need to be calculated based on the exact same list of fields (@Jon Skeet is 100% in the right, as usual). And yet, it could very well be that you are right that the differing fields are what's causing OP to scratch his head in disbelief. But it wouldn't be because HashSet is doing something wrong. It would be because perhaps OP is making the incorrect assumption that having equal hashCodes automatically means that the HashSet.Contains() check will return true. – Irremovable

@6ton: Suppose you have a field where computing a decent hash code might be very expensive, but equality checks are usually cheap - and where instances very rarely differ by only that field. In that case, it would make sense not to include it in the hash code. – Bobbery

@Irremovable I am not saying they must be calculated based on same fields, but practically they should be and 99.99% of the time are. When they are not it results into this discussion :) – Suricate