哈希算法与哈希数

鼯鼠

用标准类库的Integer 来充当HashMap 的键，由于它具备了键所应必备的一切功能，因此程序能很正常地运行。但是当用自己写的类来充当键的时候，就必须把hashCode( )和equals( )都给覆写了，就像下面这个程序：
public class Groundhog {
protected int number;
public Groundhog(int n) { number = n; }
public String toString( ) {
return "Groundhog #" + number;
}
} ///:~
public class Prediction {
private boolean shadow = Math.random( ) > 0.5;
public String toString( ) {
if(shadow)
return "Six more weeks of Winter!";
else
return "Early Spring!";
}
} ///:~
//: c11:SpringDetector.java
// What will the weather be?
import com.bruceeckel.simpletest.*;
import java.util.*;
import java.lang.reflect.*;
public class SpringDetector {
private static Test monitor = new Test( );
// Uses a Groundhog or class derived from
Groundhog:
public static void
detectSpring(Class groundHogClass) throws
Exception {
Constructor ghog =
groundHogClass.getConstructor(
new Class[] {int.class});
Map map = new HashMap( );
for(int i = 0; i < 10; i++)
map.put(ghog.newInstance(
new Object[]{ new Integer(i) }), new
Prediction( ));
System.out.println("map = " + map + "\n");
Groundhog gh = (Groundhog)
ghog.newInstance(new Object[]{ new
Integer(3) });
System.out.println("Looking up prediction for "
+ gh);
if(map.containsKey(gh))
System.out.println((Prediction)map.get(gh));
else
System.out.println("Key not found: " + gh);
}
public static void main(String[] args) throws
Exception {
detectSpring(Groundhog.class);
monitor.expect(new String[] {
"%% map = \\{(Groundhog #\\d=" +
"(Early Spring!|Six more weeks of Winter!)" +
"(, )?){10}\\}",
"",
"Looking up prediction for Groundhog #3",
"Key not found: Groundhog #3"
});
}
} ///:~
//: c11:Groundhog2.java
// A class that's used as a key in a HashMap
// must override hashCode( ) and equals( ).
public class Groundhog2 extends Groundhog {
public Groundhog2(int n) { super(n); }
public int hashCode( ) { return number; }
public boolean equals(Object o) {
return (o instanceof Groundhog2)
&& (number == ((Groundhog2)o).number);
}
} ///:~
//: c11:SpringDetector2.java
// A working key.
import com.bruceeckel.simpletest.*;
import java.util.*;
public class SpringDetector2 {
private static Test monitor = new Test( );
public static void main(String[] args) throws
Exception {
SpringDetector.detectSpring(Groundhog2.class);
monitor.expect(new String[] {
"%% map = \\{(Groundhog #\\d=" +
"(Early Spring!|Six more weeks of Winter!)" +
"(, )?){10}\\}",
"",
"Looking up prediction for Groundhog #3",
"%% Early Spring!|Six more weeks of Winter!"
});
}
} ///:~
Groundhog2.hashCode( ) 会以groundhog的序号为hash 数，并且返回这个数字。程序员要保证两个groundhog不能拥有相同的序号。HashCode( )并不要求返回一个唯一的标识符，可是equals( )方法就必须能准确地判断两个对象是否相等。这个equals( )是根据groundhog 的序号来作判断的，所以如果HashMap 的键里有两个序号相同的Groundhog2 的话，程序就会出错。虽然equals( )好像只检查了参数是不是Groundhog2 类型的，但实际上它还悄悄地作了一个健全性检查，也就是检查一下这个对象是不是null 的，因为如果等号的左边是null 的话，instanceof 会返回false。如果类型正确且不为空， equals( )就要根据ghNumber 进行比较。
一个合适的equals( )必须做到以下五点：
1. 反身性：对任何x，x.equals(x)必须是true 的。
2. 对称性：对任何x 和y，如果y.equals(x)是 true 的，那么x.equals(y)也必须是true 的。
3. 传递性：对任何x，y 和z，如果x.equals(y)是true 的，且y.equals(z)也是true 的，那么x.equals(z)也必须是true 的。
4. 一致性：对任何x 和y，如果对象里面用来判断相等性的信息没有修
改过，那么无论调用多少次x.equals(y)，它都必须一致地返回true 或false。
5. 对于任何非空的x，x.equals(null)必须返回false。