效率编程 之「对于所有对象都通用的方法」

第 1 条：覆盖equals方法时请遵守通用约定

覆盖equals方法看似很简单，但是有许多覆盖方式会导致错误，并且后果非常严重。最容易避免这类问题的办法就是不覆盖equals方法，在这种情况下，类的每个实例都只与它自身相等。如果类满足了以下任何一个条件，就不需要我们覆盖equals方法：

• 类的每个实例本质上都是唯一的；
• 不关心类是否提供了“逻辑相等”的测试功能；
• 超类已经覆盖了equals方法，从超类继承过来的行为对于子类也是合适的；
• 类是私有的或是包级私有的，可以确定它的equals方法永远不会被调用。

有一种“值类”不需要覆盖equals方法，即用实例受控确保“每个值至多只存在一个对象”的类，如枚举类型。否则的话，如果要覆盖equals方法，则需要满足以下等价关系：

• 自反性，对于任何非null的引用值x，x.equals(x)必须返回true；
• 对称性，对于任何非null的引用值x和y，当且仅当x.equals(y)返回true时，y.equals(x)必须返回true；
• 传递性，对于任何非null的引用值x、y和z，如果x.equals(y)返回true，并且y.equals(z)也返回true，那么x.equals(z)也必须返回true；
• 一致性，对于任何非null的引用值x和y，只要equals()的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false；
• 对于任何非null的引用值x，x.equals(null)必须返回fales.

如果违反了上述等价关系，就会导致类在比较的时候出现不可预测的行为。例如，Timestamp的equals就违反了对称性，因此如果Timestamp和Date对象被用于同一个集合中，或者以其他方式被混合在一起，就会引起不正确的行为。无论类是否是不可变的，都不用使equals方法依赖于不可靠的资源。基于上述原则及要求，我们得出了以下实现高质量equals方法的诀窍：

1. 使用==操作符检查“参数是否为这个对象的引用”。如果是，则返回ture。这只不过是一种性能优化，如果比较操作有可能很昂贵，就值得这么做。
2. 使用instanceof操作符检查“参数是否为正确的类型”。如果不是，则返回false。一般来说，所谓“正确的类型”是指equals方法所在那个类。有些情况下，则是指该类所实现的某个接口。如果类实现的接口改进了equals约定，允许在实现了该接口的类之前进行比较，那么就使用接口。
3. 把参数转换成正确的类型。因为转换之前进行过instanceof测试，所以确保会成功。
4. 对于该类中的每个“关键”域，检查参数中的域是否与该对象中对应的域相匹配。如果这些测试全部成功，则返回true；否则返回false。如果第 2 步中的类型是个接口，就必须通过接口方法访问参数中的域；如果该类型是个类，也许就能直接访问参数中的域，这药取决于它们的可访问性。
5. 当我们编写完equals方法之后，应该问自己是三个问题：它是否是对称的、传递的、一致的？

对于既不是float也不是double类型的基本类型域，可以使用==操作符进行比较；对于对象引用域，可以递归地调用equals方法；对于float域，可以使用Float.compare方法；对于double域，则使用Double.compare方法。对float和double域进行特殊的处理是有必要的，因此存在着Float.NaN、-0.0f以及类似的double常量。

域的比较顺序可能会影响到equals方法的性能。为了获得最佳的性能，应该最先比较最有可能不一致的域，或者是开销最低的域，最理想的情况是两个条件同时满足的域。

public final class PhoneNumber {
    private final short areaCode;
    private final short prefix;
    private final short lineNubmer;

    /**
     * 构造函数
     *
     * @param areaCode
     * @param prefix
     * @param lineNumber
     */
    public PhoneNumber(int areaCode, int prefix, int lineNumber) {
        rangeCheck(areaCode, 999, "area code");
        rangeCheck(prefix, 999, "prefix");
        rangeCheck(lineNumber, 9999, "line number");
        this.areaCode = (short) areaCode;
        this.prefix = (short) prefix;
        this.lineNubmer = (short) lineNumber;
    }

    /**
     * 参数校验方法
     *
     * @param arg
     * @param max
     * @param name
     */
    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || arg > max) {
            throw new IllegalArgumentException(name + " : " + arg);
        }
    }

    /**
     * 覆盖 equals 方法
     *
     * @param o
     * @return true or false
     */
    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof PhoneNumber)) {
            return false;
        }
        PhoneNumber pn = (PhoneNumber) o;
        return pn.lineNubmer == lineNubmer
                && pn.prefix == prefix
                && pn.areaCode == areaCode;
    }
}

如上述代码所示，该类的equals方法就是根据上面的诀窍构造出来的，符合equals方法的各项等价关系以及通用约定。下面，给出有关equals方法的最后告诫：

• 覆盖equals方法时总要覆盖hashCode方法；
• 不用切图让equals方法过于智能；
• 不用将equals方法声明的Object对象替换为其他的类型。

第 2 条：覆盖equals方法时总要覆盖hashCode方法

一个很常见的错误根源在于没有覆盖hashCode方法。在每个覆盖了equals方法的类中，也必须覆盖hashCode方法。如果不这样做的话，就会违反Object.hashCode的通用约定，从而导致该类无法结合所有基于散列的集合一起正常工作，这样的集合包括HashMap、HashSet和Hashtable等。以上 第 1 条 中的PhoneNumber类为例，如果我们企图将其与HashMap一起使用：

Map<PhoneNumber, String> amap = new HashMap<PhoneNumber, String>();
amap.put(new PhoneNumber(010, 521, 1314), "Gavin");

这时候，我们可能期望amap.get(new PhoneNumber(010, 521, 1314))会返回Gavin，但实际上返回的是null。出现这样现象的原因就是，我们没有覆盖hashCode方法，以至于两个相等的实例具有不相等的散列码。修正这个问题非常简单，只需为PhoneNumber类提供一个合适的hashCode方法即可。那么，hashCode方法应该是什么样的呢？编写一个合法但并不好用的hashCode方法没有任何价值。例如，下面这个方法总是合法，但是永远都不应该被正式使用：

@Override
public int hashCode() {
    return 20151120;
}

上面这个hashCode方法是合法的，因为它确保了相等的对象总是具有同样的散列码。但是它也是极为恶劣的，因为它使得每个对象都具有同样的散列码。因此，每个对象都被映射到同一个散列通中，使散列表退化为链表。它使得本该线性时间运行的程序变成了以平方级时间在运行。对于规模很大的散列表而言，这会关系到散列表能否正常工作。一个好的散列函数通常倾向于“为不相等的对象产生不相等的散列码”。理想情况下，散列函数应该把集合中不相等的实例均匀地分布到所有可能的散列值上。想要完全达到这种理想的情形是非常困难的，幸运的是，相对接近这种理想情形并不太困难。下面给出一种简单的解决办法：

• 1、把某个非零的常数值，比如说 1120，保存在一个名为result的int类型的变量中。
• 2、对于对象中每个关键域f（指equals方法中涉及的每个域），完成以下步骤：
  • a. 为该域计算int类型的散列码c：
    • i. 如果该域是boolean类型，则计算(f?1:0)。
    • ii. 如果该域是byte、char、short或者int类型，则计算(int)f。
    • iii. 如果该域是long类型，则计算(int)(f^(f>>>32))。
    • iv. 如果该域是float类型，则计算Float.floatToIntBits(f)。
    • v. 如果该域是double类型，则计算Double.doubleToLongBits(f)，然后按照步骤2.a.iii，为得到的long类型值计算散列值。
    • vi. 如果该域是一个对象引用，并且该类的equals方法通过递归地调用equals的方式来比较这个域，则同样为这个域递归地调用hashCode方法。如果需要更复杂的比较，则为这个域计算一个“范式”，然后针对这个范式调用hashCode方法。如果这个域的值为null，则返回0（或者其他某个常数，但通常是0）。
    • vii. 如果该域是一个数组，则要把每个元素当做单独的域来处理。也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤2.b中的做法把这些散列值组合起来。如果数组域中的每个元素都很重要，可以利用 JDK 发行版本1.5中增加的Arrays.hashCode方法。
  • b. 按照下面的公式，把步骤2.a中计算得到的散列码c合并到result中：
    • result = 31 * result + c;
• 3、返回result。
• 4、写完了hashCode方法之后，问问自己“相等的实例是否都具有相等的散列码”。要编写单元测试来验证我们的推断。如果相等的实例有着不相等的散列码，则要找出原因，并修正错误。

在散列码的计算过程中，可以把冗余域排除在外。换句话说，如果一个域的值可以根据参与计算的其他域值计算出来，则可以把这样的域排除在外。必须排除equals比较计算中没有用到的任何域。但是，不用试图从散列码计算中排除掉一个对象的关键部分来提高性能。

@Override
public int hashCode() {
    int result = 1120;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNubmer;
    return result;
}

如上述代码所示，这个hashCode方法就是根据上面的方法构造出来的，满足hashCode方法的通用约定。