У меня следующая ситуация: у меня много 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");
}
}
}