java.util.Set.contains(Object o) 的奇怪行为

The doc http://docs.oracle.com/javase/6/docs/api/java/util/Set.html#contains(java.lang.Object) about java.util.Set.contains(Object o) says:

当且仅当该集合包含元素 e 且满足以下条件时返回 true (o==null ? e==null : o.equals(e))。

也就是说，这是一个 POJO（如您所见，我覆盖了它equals方法）：

public class MonthAndDay {

    private int month;
    private int day;

    public MonthAndDay(int month, int day) {
        this.month = month;
        this.day = day;
    }

    @Override
    public boolean equals(Object obj) {
        MonthAndDay monthAndDay = (MonthAndDay) obj;
        return monthAndDay.month == month && monthAndDay.day == day;
    }

}

那么请问为什么会打印以下代码false代替true?

Set<MonthAndDay> set = new HashSet<MonthAndDay>();
set.add(new MonthAndDay(5, 1));
System.out.println(set.contains(new MonthAndDay(5, 1)));
// prints false

解决方案是重写contains(Object o)方法，但原来的应该（几乎）完全相同，我错了吗？

Set<MonthAndDay> set = new HashSet<MonthAndDay>() {

    private static final long serialVersionUID = 1L;

    @Override
    public boolean contains(Object obj) {
        MonthAndDay monthAndDay = (MonthAndDay) obj;
        for (MonthAndDay mad : this) {
            if (mad.equals(monthAndDay)) {
                return true;
            }
        }
        return false;
    }

};
set.add(new MonthAndDay(5, 1));
System.out.println(set.contains(new MonthAndDay(5, 1)));
// prints true

当你覆盖equals(Object)你还需要覆盖hashcode().

具体来说，必须实施这些方法，以便如果a.equals(b) is true, then a.hashcode() == b.hashcode() is all true。如果不遵守这个不变量，那么HashMap, HashSet and Hashtable将无法正常工作。

技术细节如何hashcode() and equals(Object)应该表现在指定Object http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html API.

那么，如果你犯了这个错误，为什么基于哈希的数据结构会崩溃呢？基本上是因为哈希表的工作原理是使用哈希函数的值来缩小要与“候选”进行比较的值集的范围。如果候选对象的哈希码与表中某个对象的哈希码不同，则查找算法很可能不会与表中的对象进行比较……即使对象相等。