讨论 - 散列混合 (CustomClass1, CustomClass2, Collection<CustomClass3>) 的最佳方式

Question

我正在阅读 Java 中 equals() 和 hashCode() 的实现，得出的结论是存在冲突的可能性（在我的案例中我从未遇到过冲突）但我正在考虑找到一种更好的方法来获取一些唯一标识符，例如我拥有的对象的 GUID -

我有 [CustomClass1 cc1、CustomClass2 cc2 和 Set scc3] 来自一个方法，我将它们包装在 object1 中并执行 object1.hashCode() 并且 hashCode() 工作正常（处理SET 中对象的顺序也是如此，所以即使集合中对象的顺序不同，比如 1、2、3 或 2、3、1，只要它们是“1”，我就会得到唯一的哈希码，“ 2" 和 "3" 但不考虑顺序）

但我想找到更好的方法 - 将 object1 转换为 GUID 而不是 object1.hashCode()。

有没有更好的方法？如果是，请分享您的想法。

Answer 1

没有更好的实用方法。

鉴于哈希算法设计不佳，冲突很常见，哈希值是否为 32 位并不重要（如 java 的 hashCode()）或 128 位 (UUIds)。

Java 的内置类型，例如 String 或 List 或 HashSet 或诸如此类的东西，在合理的范围内都能很好地完成工作，因此您不必担心它们的设计很糟糕。 String 的 hashCode 可能会更好，但更改它会向后不兼容。不过，这并不是说 java.lang.String 中的当前算法特别糟糕。没关系。

一旦我们继续前进，32 位 space 中的冲突极不可能。它发生一次，好吧，40 亿个条目。冲突 没问题 - java 不会完全做错事。试试吧！

class StupidHashCodeImpl {
  private final String name;

  public StupidHashCodeImpl(String name) {
    if (name == null) throw new NullPointerException("name");
    this.name = name;
  }

  @Override public String toString() {
    return this.name;
  }

  @Override public int hashCode() {
    return 1; // all StupidHashCodeImpl hashes collide!
  }

  @Override public boolean equals(Object other) {
    if (other == null || other.getClass() != StupidHashCodeImpl.class) return false;
    return this.name.equals(((StupidHashCodeImpl) other).name);
  }
}

and then:

Set<StupidHashCodeImpl> set = new HashSet<>();
set.add(new StupidHashCodeImpl("foo"));
set.add(new StupidHashCodeImpl("bar"));
System.out.println(set.size()); // prints 2 as expected.
set.contains(new StupidHashCodeImpl("foo")); //true
set.contains(new StupidHashCodeImpl("bar")); //true
set.contains(new StupidHashCodeImpl("baz")); //false

看到了吗？效果很好。这里完全没有问题。规则明确：

如果 a.equals(b)，那么它必须认为 a.hashCode() == b.hashCode() - 不遵守此规则意味着 hashset 开始给出错误的答案。
反之不正确。如果 a.hashCode() == b.hashCode()，那么如果 !a.equals(b) 就完全没问题。 HashSet 处理得很好。
hashCodes 必须稳定。这确实意味着改变哈希集中的对象或用作哈希图中的键的对象会破坏事物。

上述 'bad hashing' 算法的唯一缺点是 map/set 变得低效。通常，如果您将一百万个键放入一个哈希集中，然后执行一些 set.contains() 操作，那么这些操作要比将一百万个条目放入列表中并运行 .contains() 要快得多。然而，如果你在一个集合中加入一百万个条目并且它们都有冲突的哈希，那么 HashSet 在性能上并不比列表好（事实上，有点差），原因很明显。

但是，UUID 并不能解决这个问题。全部：

如果您的散列算法不好，UUID 不会降低发生冲突的几率。如果要修复它，请修复错误的算法。
如果您的哈希算法很好，冲突的发生率大约为十亿分之一，因此冲突造成的任何性能下降总是除以十亿左右，将其减少到微不足道。
对比一下，比较 128 位值比比较 32 位值要昂贵得多。那么，您为十亿分之一的冲突付出的代价是什么？好的，您可以使用 UUID 摆脱它，但是您需要为每次查找支付少量费用。

您必须编写它并使用 JMH 进行一些性能测试才能确定，但我敢打赌 UUID-based HashSet impl 显着比 java 自己的 HashSet 慢

自己写'good'散列算法，很简单：

使用 Project Lombok 的 @Value 或 @Data 或 @EqualsAndHashCode 并收工。如果您不想这样做，或者您只是想知道它是如何工作的，请单击 link 并检查示例代码，它准确地显示了正在发生的事情。或者，询问您的 IDE - 他们中的大多数（包括 2 个最流行的 IDEs，IntelliJ 和 eclipse）在他们的菜单结构中的某处有 'generate equals and hashCode'。他们做了类似于 lombok 的事情。

总的要点是：

选择一些常量。最好是素数。
从 1 开始。
通过首先将我们当前的哈希值乘以质数，然后添加这个新组件的哈希，“整合”每个组件的每个哈希（通常所有字段都是组件——所有需要影响哈希值的东西）。
特别注意具有 known-broken 哈希码隐含的数据类型。例如，不要调用 someArray.hashCode()，它不会按照您的想法执行，而是调用 Arrays.deepHashCode(someArray)。通过将高 32 位和低 32 位异或在一起来散列 long。通过选择 2 个任意数字来哈希布尔值（一个用于 true，一个用于 false）。
将 null 散列为某物。只需选择一个值。可能不是 0.

仅此而已。

例如，这将确保 1,2,3 和 2,3,1 具有不同的哈希码。

讨论 - 散列混合 (CustomClass1, CustomClass2, Collection<CustomClass3>) 的最佳方式

Discussion - Best way to hash a mix of (CustomClass1, CustomClass2, Collection<CustomClass3>)

java

equals

hashcode