继承自 Object 类
hashcode() 和 equals() 均是 Object 类中定义的方法,这意味着所有的 Java 实例对象均继承了这两个方法。其中 hashcode() 方法是一个 native 的方法,用来产生该对象的哈希值;而 equals() 方法是用来比较两个对象是否相同,在 Object 中的实现是直接进行了内存地址比较。equals() 方法在实际使用中是使用频率非常高的方法之一,而 hashcode() 方法却不是常用的方法。hashcode() 方法的主要使用用途是在 Java 的 集合(Collection)体系中,在集合中采用了 Hash 命令的集合类都使用了这个方法。用来快速定位两个对象是否不相等,可以说 hashcode() 方法就是为了 Java 集合体系而准备的。
下面是 hashcode() 和 equals() 在 Java 中的源代码:
public native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}
重写 equals() 方法
当使用 String、Math、Integer 或 Double 等这些类的时候,这些类已经覆盖了默认的 equals() 方法以便能正确反应两个对象是否相等。如下是 String 中对 equals() 的覆盖:
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
很明显,这是在进行内容比较,已经不再是简单的内存地址的比较了。依次类推Double、Integer、Math 等等这些类都是重写了 equals() 方法的。
我们还应该注意,Java 语言对 equals() 的要求如下:
- 对称性:如果
x.equals(y)
返回的是true
,那么y.equals(x)
也应该返回true
。 - 反射性:
x.equals(x)
必须返回true
。 - 类推性:如果
x.equals(y)
返回的是true
,而且y.equals(z)
返回的也是true
,那么z.equals(x)
也应该返回true
。 - 一致性:如果
x.equals(y)
返回的是true
,只要 x 和 y 内容一直不便,不管重复多少次x.equals(y)
,返回值都应该是true
。 - 任何情况下:
x.equals(null)
,返回值永远都为false
;x.equals(和x不同类型的对象)
,返回值永远都为false
。
以上这五点是重写 equals() 方法时必须要遵守的准则,如果违反会出现意想不到的错误。
重写 hashcode() 方法
下面是 String 类中重写的 hashcode() 方法:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
上面的代码实际在执行如下算式:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
s 代表字符串,s[i] 代表字符串的第 i 个字符,n 代表字符串长度。^ 代表求幂(空字符串的哈希码为 0)。
hashcode() 与 equals() 方法的区别
equals() 相等的两个对象,hashcode() 一定相等;equals() 不相等的两个对象,却并不能证明它们的 hashcode() 不相等。换句话说,equals() 方法不相等的两个对象,hashcode() 有可能相等。反过来,hashcode() 不相等,equals() 也一定不相等;hashcode() 相等,equals() 不一定相等。
在 Object 类中,hashcode() 是默认的是根据内存地址来计算的,而 equals() 方法是直接比较两个对象的内存地址,但因为 hashcode() 在计算哈希码时候又可能会产生冲突,造成两个不同地址的哈希码一致,因此仅仅通过 hashcode() 相等,是无法判断出两个对象是相等的;但反过来,如果 两个对象 equals() 是相等的,那么其对应的 hashcode() 也是相等的。而其子类,例如 String、Integer、Double 等在重写这两个方法时候也都遵守了这些原则。
在集合体系中的应用
在 HashSet 中不允许出现重复对象,而在 HashMap 中则不允许出现重复的 key 值,在 HashSet 中和 HashMap 中是如何确定对象是否重复的呢?
我们可以直接通过 equals() 方法来判断两个对象是否相等,因为所有重写的子类应该遵循了 equals() 方法的原则,从而来判断是否对象是否重复。但是如果每两个对象都通过 equals() 来判断是否重复,那么效率会大大降低,例如在 String 重写的 equals() 方法中,会循环判断每个字符是否相等。为了提高程序的运行的效率,Java 在两个判断两个对象是否相等的时候,先通过 hashcode() 方法来判断两个对象是否相等,如果 hashcode() 不相等,就没有进行 equals() 方法的必要,因为两个对象肯定不相等;而如果 hashcode() 相等,那么再进行 equals() 判断,就能确定两个对象是否相等了,因为 hashcode() 方法相等,其 equals() 方法返回值不一定相等。所以需要完全确定两个对象是否相等,需要 hashcode() 与 equals() 方法结合来使用。
下面是 HashMap 中 put(K key, V value)
方法中确定 key 是否重复的局部代码片段:
Node<K,V> e; K k;
//判断需要添加的Node是否和原来的Node一致,并且key不会null
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
扰动函数
在 JDK1.7 中,HashMap 的 hash(int h)
方法的源代码如下:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
而在 JDK1.8 中,HashMap 的 hash(Object key)
方法的源代码如下:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们知道,在 Object 类中默认提供的 hashcode() 方法,返回的是一个 int 类型的哈希码。int 类型带符号对象可以储存范围在 -2147483648
到 2147483648
,这总共有四十亿个数字。如果在 HashMap 中直接用这个数组来作为数组的下标,可能最多的时候需要四十亿的映射内存空间,这显然不是内存中可以存放下的。所以这个哈希码并不能直接用在 HashMap 中数据数组的中,而需要进一步运算才能在高效合理的情况下使用哈希码。
在使用之前先要对数组的长度做取模运算,得到的余数,就是 HashMap 中数据数组的下标。
在 JDK1.7 中与这一步骤有关的是 indexFor()
方法,其源代码如下:
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
}
而在 JDK1.8 中去掉了这个方法,因为该方法比较简单,所以直接放在具体要访问数组的方法内部中了,下面是 HashMap 的 put(K key, V value)
中调用的 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
的局部代码片段:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//...
//省略部分代码
}
可以看到在使用中,也仅仅是把哈希码和数组长度-1 做了一个与运算。
我们知道,在 HashMap 中,如果创建对象时没有指定其初始容量,HashMap 默认的数据数组的大小是 16;如果创建对象时指定了初始容量,如果初始容量会被指定成大于等于这个初始容量的最小 2 的整次幂。之所以需要这么设定,是因为 (length-1)
和哈希码进行与运算之后,其结果的高位全部归零,只保留了低位值,而保留的低位值数值较小,可以用来作为 HashMap 的数据数组下标。而 (leng-1)
就相对于是一个“低位掩码”。
下面以 HashMap 的初始数据数组的默认长度 16 为例:
public class HashTest {
//定义一个将int类型转换为二进制并打印出来的方法
private static String printNum(int n){
String num = Integer.toBinaryString(n);
if(num.length() == 32){
return num;
}else{
StringBuilder sb = new StringBuilder("");
for(int i =0;i < 32 - num.length(); i ++){
sb.append("0");
}
return sb.toString() + num;
}
}
public static void main(String[] args) {
//定义HashMap中key
String key = new String("哈希测试分析");
//打印该key值的哈希码的二进制
System.out.println(" " + printNum(key.hashCode()));
//打印HashMap中默认的数据数组长度-1的二进制
System.out.println("& " + printNum(16-1));
System.out.println("-----------------------------------");
//打印其求与运算结果
System.out.println(" " + printNum(key.hashCode() & (16-1)));
}
}
运行上面的程序,其结果为:
00001101011011011010101111111000
& 00000000000000000000000000001111
-----------------------------------
00000000000000000000000000001000
根据上面的结果可以看出,其结果的高位全部为 0,只留下低位的值,其转换为十进制结果为 8,此时作为 HashMap 的数据数组下标是可以的。但是这样也出现了一个问题,就算在计算哈希码时散列值再松散,在运行行与运算之后,只剩下低位的数据,这样碰撞出现的频率就会增高。另外一个问题是,如果在做散列的时候出现了类似低位呈现规律性重复出现,那么碰撞出现的频率就更高了。
为了解决上面的问题,就需要“扰动函数”,来扰动原来的哈希码,以增大随机性,减小碰撞出现的频率。
下面以 JDK1.8 中的 hash(Object key)
来进行举例:
public static void main(String[] args) {
//定义HashMap中key
String key = new String("哈希测试分析");
int hash = key.hashCode();
//打印该key值的哈希码的二进制
System.out.println(" " + printNum(hash));
//下面进行hash(Object key)方法中的运算
//将key值的哈希码右移16位
System.out.println("^ " + printNum(hash >>> 16));
System.out.println("-----------------------------------");
hash = hash ^ (hash >>> 16);
//打印hash与hash右移16位数值的或运算结果
System.out.println(" " + printNum(hash));
System.out.println();
System.out.println(" " + printNum(hash));
//打印HashMap中默认的数据数组长度-1的二进制
System.out.println("& " + printNum(16-1));
System.out.println("-----------------------------------");
//打印其求与运算结果
System.out.println(" " + printNum(hash & (16-1)));
System.out.println(hash & (16-1));
}
上面的程序运算结果是:
00001101011011011010101111111000
^ 00000000000000000000110101101101
-----------------------------------
00001101011011011010011010010101
00001101011011011010011010010101
& 00000000000000000000000000001111
-----------------------------------
00000000000000000000000000000101
上面的程序可以用如下的简化形式表示:
h=hashCode():00001101011011011010101111111000 //调用"哈希测试分析"字符串的hashCode()方法
h:00001101011011011010101111111000
h>>>16:00000000000000000000110101101101 //将哈希码右移16位
------------------------------------------------
hash=h^(h>>>16):00001101011011011010011010010101 //计算后的哈希码
hash:00001101011011011010011010010101
(16-1):00000000000000000000000000001111 //HashMap默认的数据数组长度-1
------------------------------------------------
00000000000000000000000000000101 //计算后的结果,转换为十进制等于5
将原来的哈希码右移16位,正好是32位的一半,刚好将原来哈希码的高位移动到了低位,再用原来哈希码的高位和低位做异或,这样就扰动了原来哈希码的高位和低位,以及来增大随机性。混合后的哈希码掺杂了部分高位码的特征,换句话说,混淆后的哈希码也保留也原来哈希码部分高位码。
而在 JDK1.7 中,进行了 4 次扰动,其原理和 JDK1.8 中的一致,都是为了增大随机性。但经过测试,扰动四次的碰撞次数并没有比扰动一次减少太多,反而运算四次增加了程序的运算量,所以在 JDK1.8 中改为了一次,这也是在性能和算法策略中寻求的一种平衡。
本文部分内容来自: