散列的价值在于速度。我们使用数组来保存键的信息，这个信息并不是键本身，而是通过键对象生成一个数字(散列码)，作为数组下标。由于数组的容量是固定的，而散列容器的大小是可变的，所以不同的键可以产生相同的数组下标(散列码)。也就是说，可能会有冲突(当然也有特例，比如EnumMap和EnumSet)。所以，数组的值存放着一个保存所有相同散列码的值的list(引用)。然后对list中的值使用equals进行线性查询。如果散列函数设计的比较好的话，数组的每个位置只有较少的值，并且浪费空间也小。于是，查询过程就是首先计算键的散列码得到数组下标，然后内存寻址(时间复杂度为O(1)，赋值)找到数组的值，再遍历list(时间复杂度为O(n)，线性查询)即可。即hashCode和equals共同确定了对象的唯一性。
所有类都继承于Object。Object的hashCode方法生成的散列码，实际上是默认使用对象的地址计算散列码；而Object的equals方法实际上就是地址比较(==)。显然，当我们在使用散列容器(如HashMap的Key，HashSet等)时，我们自定义的类中还继承Object的hashCode和equals是不行的。必须重写hashCode和equals方法。好的hashCode()应该产生分布均匀的散列码。可以用IDE自动生成。下面是一个例子：
import java.util.List;
public class Test9 {
boolean a;
byte b;
short c;
int d;
char e;
long f;
float g;
double h;
String i;
List<String> j;
int[] k;
@Override
public int hashCode() {
// [STEP1] hashCode()里的魔法数字，之所以选择31，是因为它是个奇素数，如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。
// 使用素数的好处并不是很明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性，就是用移位和减法来代替乘法，可以得到更好的性能：31*i==(i<<5)-i。现在的VM可以自动完成这种优化。(from 《Effective Java》)
final int prime = 31;
// [STEP2] 为对象中每个有意义的域用下面公式计算散列码 result = prime * result + c
int result = 1;
// boolean
result = prime * result + (a ? 1231 : 1237);
// byte/short/int/char
result = prime * result + b;
result = prime * result + c;
result = prime * result + d;
result = prime * result + e;
// long
result = prime * result + (int) (f ^ (f >>> 32));
// float
result = prime * result + Float.floatToIntBits(g);
// double
long temp;
temp = Double.doubleToLongBits(h);
result = prime * result + (int) (temp ^ (temp >>> 32));
// 对象
result = prime * result + ((i == null) ? 0 : i.hashCode());
// List(要求每个元素实现hashCode)
result = prime * result + ((j == null) ? 0 : j.hashCode());
// 数组(要求每个元素实现hashCode)
result = prime * result + Arrays.hashCode(k);
// [STEP3] 返回
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Test9 other = (Test9) obj;
if (a != other.a)
return false;
if (b != other.b)
return false;
if (c != other.c)
return false;
if (d != other.d)
return false;
if (e != other.e)
return false;
if (f != other.f)
return false;
if (Float.floatToIntBits(g) != Float.floatToIntBits(other.g))
return false;
if (Double.doubleToLongBits(h) != Double.doubleToLongBits(other.h))
return false;
if (i == null) {
if (other.i != null)
return false;
} else if (!i.equals(other.i))
return false;
if (j == null) {
if (other.j != null)
return false;
} else if (!j.equals(other.j))
return false;
if (!Arrays.equals(k, other.k))
return false;
return true;
}
}