Can it be?
Set set1 = new HashSet(5);
Set set2 = new HashSet(5);
// add of bunch of strings to both sets
assert set1.equals(set2) == false;
Yes it can!
We actually had this problem in an integration test. The cause was that the strings to one set were added concurrently. Interestingly, the sets seemed to be the same, when printed they contained the same strings, just in a different order (which is also interesting). However, the internals were apparently so damaged that an equals invocation return false.
We replaced the HashSet with a ConcurrentSkipSet, and all was fine again.
Conclusion: Okay, so this is a boring conclusion, but just be careful with using normal collections in concurrent situations.