java - 取消覆盖 hashCode

Question

我有以下情况:我有很多 BST s，我想合并同构子树以节省空间。

我正在将二叉搜索树节点散列到一个“唯一表”中——基本上是 BST 节点的散列。

具有相同左右子节点和相同键的节点具有相同的哈希码，并且我已经适本地覆盖了节点类的 equals。

一切正常，除了计算哈希值很昂贵 - 它涉及计算子节点的哈希值。

我想缓存节点的散列值。我遇到的问题是执行此操作的自然方式，从节点到整数的 HashMap 本身将调用节点上的哈希函数。

我通过在节点中声明一个新字段来解决这个问题，我用它来存储哈希码。但是，我觉得这不是正确的解决方案。

我真正想要的是使用使用节点地址的散列将节点映射到它们的散列码。我想我可以通过创建 HashMap 并将节点转换为对象来实现这一点，然后对象将调用对象的 hashCode 方法，但这没有用(插入到哈希中仍然调用节点哈希和相等函数。

我希望深入了解实现节点到哈希代码缓存的最佳方式。我在下面附上了代码，说明了下面发生的事情。

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;

class Bst {

  int key;
  String name;
  Bst left;
  Bst right;

  public Bst( int k, String name, Bst l, Bst r ) {
    this.key = k;
    this.name = name;
    this.left = l;
    this.right = r;
  }

  public String toString() {
    String l = "";
    String r = "";
    if ( left != null ) {
      l = left.toString();
    }
    if ( right != null ) {
      r = right.toString();
    }
    return key + ":" + name + ":" + l + ":" + r;
  }

 @Override
  public boolean equals( Object o ) {
    System.out.println("calling Bst's equals");
    if ( o == null ) {
      return false;
    }
    if ( !(o instanceof Bst) ) {
      return false;
    }
    Bst n = (Bst) o;

    if ( n == null || n.key != key ) {
      return false;
    } else if ( n.left != null && left == null || n.right != null && right == null ||
                n.left == null & left != null || n.right == null && right != null ) {
      return false;
    } else if ( n.left != null && n.right == null ) {
      return n.left.equals( left );
    } else if ( n.left != null && n.right != null ) {
      return n.left.equals( left ) && n.right.equals( right );
    } else if ( n.left == null && n.right != null ) {
      return n.right.equals( right );
    } else {
      return true;
    }
  }

  @Override
  public int hashCode() {
    // the real hash function is more complex, entails
    // calling hashCode on children if they are not null
    System.out.println("calling Bst's hashCode");
    return key;
  }
}

public class Hashing {

  static void p(String s) { System.out.println(s); }

  public static void main( String [] args ) {
    Set<Bst> aSet = new HashSet<Bst>();
    Bst a = new Bst(1, "a", null, null );
    Bst b = new Bst(2, "b", null, null );
    Bst c = new Bst(3, "c", null, null );
    Bst d = new Bst(1, "d", null, null );

    a.left = b;
    a.right = c;
    d.left = b;
    d.right = c;

    aSet.add( a );
    if ( aSet.contains( d ) ) {
      p("d is a member of aSet");
    } else {
      p("d is a not member of aSet");
    }

    if ( a.equals( d ) ) {
      p("a and d are equal");
    } else {
      p("a and d are not equal");
    }

    // now try casts to objects to avoid calling Bst's HashCode and equals
    Set<Object> bSet = new HashSet<Object>();
    Object foo = new Bst( a.key, a.name, a.left, a.right );
    Object bar = new Bst( a.key, a.name, a.left, a.right );
    bSet.add( foo );
    p("added foo");
   if ( bSet.contains( bar ) ) {
      p("bar is a member of bSet");
    } else {
      p("bar is a not member of bSet");
    }
  }
}

Answer 1

将散列存储在节点的一个字段中对我来说是正确的解决方案。这也是 java.lang.String 用于其自己的哈希码的内容。撇开其他不谈，这意味着您不可能以其他方式可以收集的对象的缓存条目结束，等等。

如果您真的想要 Object 中的实现返回的 hashCode 的值，您可以使用 System.identityHashCode尽管。不过，您不应该依赖这个 - 或任何其他哈希码 - 是唯一的。

还有一点:由于字段是包访问，您的树目前是可变的。如果您在第一次调用它时缓存哈希码，您将不会“注意到”它是否会因字段更改而发生更改。基本上，您不应在使用哈希码后更改节点。