guava-libraries: Objects.hashCode(Object[])是否具有碰撞安全性？

Question

在查看不同覆盖hashCode()的选项时，我被引导到Google的guava-libraries中的Objects.hashCode(Object[])（javadoc）。Javadoc指出它委托给Arrays.hashCode(Object[])。在许多不同类型的对象中使用此方法是否安全？这不容易发生哈希冲突，还是因为容器通常只包含一种类型的对象，所以这不太可能发生？

作为一个简单的例子，请考虑以下类：

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class HashCodeDriver {
    public static void main(String[] args) {
        final String name = "moe";
        Student s = new Student(name);
        Teacher t = new Teacher(name);

        long studentHash = s.hashCode();
        long teacherHash = t.hashCode();
        System.out.println("studentHash=" + studentHash + " teacherHash=" + teacherHash);
        if(studentHash == teacherHash) {
            System.out.println("hash codes match");
        }
        else {
            System.out.println("hash codes don't match");
        }
    }
}

输出：

studentHash=108322 teacherHash=108322
hash codes match

对象是两种不同类型，但生成的哈希码相同。这是一个问题吗？我应该将类作为第一个参数传递以防止冲突吗？例如，

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Student.class, name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Teacher.class, name);
    }
}

这是否是 javadoc 警告仅向此方法提供单个对象的原因？从 javadoc 中可以看到：

警告：当只提供单个对象时，返回的哈希码并不等于该对象的哈希码。

- John McCarthy

Answer 1

当两个不同类型的对象具有相同的哈希码时，这并不是问题。

希望在构建HashMap时，您不会将学生和老师混为该映射的键。即使在您想要使用HashMap<Object，Object>的情况下，也没有问题，因为

assertFalse( new Teacher( "John Smith" ).equals( new Student( "John Smith" ) );

这就是为什么重写 hashCode 和 equals 方法非常重要的原因。

将委托给 Arrays.hashCode(Object[]) 的唯一缺点可能是从性能角度来看有时可能太昂贵了。

例如，在您的情况下，这将是 Teacher 或 Student 的更好的哈希方法。

@Override
public int hashCode() {
    return name.hashCode();
}

- Alexander Pogrebnyak

---

这段对话有点反了。通常情况下，开发人员会重写equals方法，但却忘记了hashcode。我不明白在这种情况下为什么HashMap<Object, Object>会是可行的选择。你的assertFalse是从哪里来的？我在HashMap中找不到它。据我所知，HashMap只使用hashCode而不是equals。因此，两个不同类型的对象可能会发生碰撞，这就是我对Objects.hashCode(Object[])持谨慎态度的原因。我同意，重写hashCode和equals作为一对总是很重要的，但据我所知，如果两个对象具有相同的哈希码，则它们应该是相等的，反之亦然。 - John McCarthy

@nondescript1 - 我想你误解了equals和hashcode的契约 - 当你重写equals时，必须重写hashcode，并且两个相等的对象应该产生相同的hashcode，但反之则不然。Object＃hashcode的一般契约是 - 并不要求如果两个对象根据equals（java.lang.Object）方法是不相等的，则调用每个对象上的hashCode方法必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。 - Premraj

根据我的理解，HashSet会使用hashCode值将对象存储在哈希桶中，但会调用equals方法比较对象的相等性。如果您想从Map中获取Teacher对象，它会检查equals方法，然后返回有效的Teacher或null，因此不会发生任何冲突。至于你的观点“根据我所见，HashMap仅使用hashCode而不是equals”，你是如何得出这个结论的？能否给我提供文档/规范的链接？ - Premraj

@nondescript1，@Alexander Pogrebnyak - 是的，使用Objects.hashCode(Object[])来生成哈希码是完全可以的，至于性能方面，也许@Alexander可以提供更多信息。 - Premraj

@Falcon，@nondescript1。我不是在谈论Arrays.hashCode的哈希分发性能，它很不错。这仅仅是关于在这里简单情况下做太多的讨论。如果您将代理到Arrays.hashCode(Object[])，那么您至少要构建一个数组来获得性能。我的观点是，如果您的对象只有一个字段，在大多数情况下，将代理到该字段的hashCode是可以的。 - Alexander Pogrebnyak

Answer 2

警告只是说x.hashCode() != Objects.hashCode(x)是正确的。(好的，这在大多数情况下是正确的。但对于某些值仍可能发生碰撞。实际上，对于大多数对象来说，它们并不相等。)

一个有效的hashCode/equals实现应该是：

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override public equals(Object obj){
        if(obj == this) return true;
        if(!(obj instanceof Teacher)) return false;
        return Objects.equal(name, ((Teacher) obj).getName());
    }

    @Override public hashCode(){
        return 0;
    }
}

这是一个有效的实现，尽管所有哈希值都会发生碰撞。根据hashCode() javadoc文档：

如果两个对象在equals(java.lang.Object)方法中不相等，则调用这两个对象的hashCode方法不一定产生不同的整数结果。

与“正常”实现的区别在于，此代码的性能将大大降低。例如，HashMap查找的性能将退化为类似列表的性能。

即使使用此实现：

@Override
public int hashCode() {
    return Objects.hashCode(Teacher.class, name);
}

不太可能，但有可能，不同类的哈希值会发生碰撞。如果两个类的类名哈希值相同，则会发生这种情况。

只有在集合中存在许多来自不同类型且名称相同的实例，并且该集合在内部使用hashCode()时，才应考虑此类优化。总体效果将受到限制：如果您有n种类型，则由于此场景最多可能发生n次碰撞。其他因素可能会支配性能特征。

- Thomas Jung

---

在您的equals实现中，该行 - if(!(obj instanceof Teacher)) return true; 应该返回false而不是true。 - Premraj

Answer 3

如果您在同一地图的键集中混合使用多种不同的混凝土类型，则仍可以使用Objects.hashCode()并通过每个混凝土类型的不同值对输出执行异或运算来最小化碰撞。

class Class1 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0x12b7eff8;
  }
}

class Class2 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0xe800792b;
  }
}

通过与一个随机选择但稳定的值进行异或运算，您可以消除仅因Object.hashCode的参数等效而可能发生的冲突的机会。

警告：当提供单个对象时，返回的哈希码不等于该对象的哈希码。

这就是为什么javadoc警告只向该方法提供单个对象的原因吗？从javadoc来看，

不是。这个警告不是关于具有相同成员的不同具体类的实例之间发生碰撞的机会。相反，它警告由于假设单个值的哈希值与singleValue.hashCode（）的哈希值相同，导致哈希码匹配的虚假负面影响。

例如，看看以下在尝试使用缓存的哈希码避免平等检查的快速跟踪代码中所做的假设：

class Name {
  int cachedHashCode;

  ...
}

class Person {
  int cachedHashCode;  // 0 if not computed

  private final Name name;

  public boolean hasName(Name n) {
    return ((cachedHashCode != 0 && n.cachedHashCode != 0) 
            && cachedHashCode == n.cachedHashCode)
        || n.equals(name);
  }

  public int hashCode() {
    if (cachedHashCode == 0) { cachedHashCode = Object.hashCode(name); }
    return cachedHashCode;
  }
}

- Mike Samuel

---

我认为Object.hashCode(...) ^ 0x12b7eff8破坏了一种类型的值的分布。Object.hashCode(0x12b7eff8, ...)应该没问题。Object.hashCode(..., getClass().getName())可能更易读一些。 - Thomas Jung

@Thomas，"destroys the distribution"是什么意思？ - Mike Samuel

我曾认为所有的位运算都会改变分布（最简单的例子是hashCode | Integer.MAX_VALUE）。但是，异或运算不会改变值的分布。它们仍然是等分布的。 - Thomas Jung

@Thomas Jung，是的。异或和同或都不会减少熵位数。 - Mike Samuel