4

你如何想出一个通用对象的散列函数？如果用户定义的两个对象“相等”，则存在两个对象需要具有相同哈希值的约束。Java 是如何做到这一点的？

4

6 回答 6

2

首先，基本上你通过重写hashCode() 方法来定义一个类的散列函数。Javadoc 指出：

hashCode 的一般合约是：

  • 每当在 Java 应用程序执行期间对同一个对象多次调用它时，hashCode 方法必须始终返回相同的整数，前提是没有修改对象上的 equals 比较中使用的信息。该整数不需要从应用程序的一次执行到同一应用程序的另一次执行保持一致。
  • 如果两个对象根据 equals(Object) 方法相等，则对两个对象中的每一个调用 hashCode 方法必须产生相同的整数结果。
  • 如果根据 equals(java.lang.Object) 方法，如果两个对象不相等，则不需要对两个对象中的每一个调用 hashCode 方法都必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

所以更重要的问题是：是什么让你的两个对象相等？反之亦然：哪些属性使您的对象独一无二？如果您对此有答案，请创建一个equals()方法来比较所有属性，true如果它们都相同则返回，false否则返回。

该hashCode()方法涉及更多，我建议您不要自己创建它，而是让您的 IDE 来做。在 Eclipse 中，您可以选择Source，然后从菜单中选择Generate hashCode() 和 equals() 。这也保证了上述要求。

这是一个小（简化的）示例，其中使用 Eclipse 生成了这两种方法。请注意，我选择不包括该city属性，因为它zipCode已经唯一标识了一个国家/地区内的城市。

public class Address {

    private String streetAndNumber;
    private String zipCode;
    private String city;
    private String country;

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((country == null) ? 0 : country.hashCode());
        result = prime * result
                + ((streetAndNumber == null) ? 0 : streetAndNumber.hashCode());
        result = prime * result + ((zipCode == null) ? 0 : zipCode.hashCode());
        return result;
    }

    @Override
    public boolean equals(final Object obj) {
        if(this == obj)
            return true;
        if(obj == null)
            return false;
        if(!(obj instanceof Address))
            return false;
        final Address other = (Address) obj;
        if(country == null) {
            if(other.country != null)
                return false;
        }
        else if(!country.equals(other.country))
            return false;
        if(streetAndNumber == null) {
            if(other.streetAndNumber != null)
                return false;
        }
        else if(!streetAndNumber.equals(other.streetAndNumber))
            return false;
        if(zipCode == null) {
            if(other.zipCode != null)
                return false;
        }
        else if(!zipCode.equals(other.zipCode))
            return false;
        return true;
    }
}
于 2012-09-26T08:32:28.633 回答
2

我刚刚找到了我自己问题的答案。Java 这样做的方式是它为每个对象定义一个 hashCode，默认情况下，如果两个对象在内存中相同，则两个对象的 hashCode 相同。因此，当哈希表的客户端覆盖对象的 equals() 方法时，他还应该覆盖计算哈希码的方法，这样如果 a.equals(b) 为真，则 a.hashCode() 也必须等于 b.hashCode ()。这样，可以确保相等的对象具有相同的哈希码。

于 2012-09-26T08:36:01.790 回答
1

Java 不这样做。如果 hashCode() 和 equals() 没有显式实现，JVM 将为有意义相等的实例生成不同的 hashCode。您可以查看 Joshua Bloch 的 Effective Java。这真的很有帮助。

于 2012-09-26T08:38:42.187 回答
0

几个选项：

  • 阅读 Joshua Bloch 的《Effective Java》。它包含一个很好的哈希码算法
  • 让您的 IDE 生成 hashCode 方法
  • Java SE 7 及更高版本：使用Objects.hash
于 2012-09-26T08:35:27.353 回答
0

班级java.lang.Object作弊。它将相等性（由 确定equals）定义为对象身份（由 确定==）。所以，除非你在你的子类中重写，否则你equals的类的两个实例是“相等的”，如果它们碰巧是同一个对象。

与此相关的哈希码由系统函数实现System.identityHashCode（它不再真正基于对象地址——曾经是这样吗？——但可以认为是以这种方式实现的）。

如果你 override equals，那么这个实现hashCode就不再有意义了。

考虑以下示例：

class Identifier {

    private final int lower;
    private final int upper;

    public boolean equals(Object any) {
        if (any == this) return true;
        else if (!(any instanceof Identifier)) return false;
        else {
            final Identifier id = (Identifier)any;
            return lower == id.lower && upper == id.upper;
        }
    }
}

这个类的两个实例被认为是相等的，如果它们的“lower”和“upper”成员具有相同的值。由于相等性现在由对象成员确定，我们需要以hashCode兼容的方式定义。

public int hashCode() {
    return lower * 31 + upper;  // possible implementation, maybe not too sophisticated though
}

如您所见，我们使用的字段与hashCode我们在确定相等性时也使用的字段相同。将哈希码基于所有成员通常是一个好主意，在比较相等性时也会考虑这些成员。

请考虑以下示例：

class EmailAddress {

    private final String mailbox;
    private final String displayName;

    public boolean equals(Object any) {
        if (any == this) return true;
        else if (!(any instanceof EmailAddress)) return false;
        else {
            final EmailAddress id = (EmailAddress)any;
            return mailbox.equals(id.mailbox);
        }
    }
}

由于在这里，相等性仅由mailbox成员确定，因此哈希码也应仅基于该成员：

public int hashCode() {
    return mailbox.hashCode();
}
于 2012-09-26T08:39:09.113 回答
-3

对象的散列是通过覆盖hashCode()方法建立的，开发人员可以覆盖该方法。

Java 在默认哈希码计算中使用素数。

如果equals()andhashCode()方法没有实现，JVM 会为对象隐式生成 hashcode（对于 Serializable 类，serialVersionUID会生成 a）。

于 2012-09-26T08:33:52.737 回答