作者:Resolve | 来源:互联网 | 2023-06-08 12:50
Java集合类中常见的hashSet,hashMap,hashTable(现已很少用,几乎都采用hashMap替代)的实现都离不开散列表,而散列表的优势在于O(1)级别的查找,而has
Java集合类中常见的hashSet,hashMap,hashTable(现已很少用,几乎都采用hashMap替代)的实现都离不开散列表,而散列表的优势在于O(1)级别的查找,而hashCode()是其中的关键支撑。
什么是hashCode()?
hashCode() 是获取哈希码函数,返回一个整数,确定对象在哈希表中的索引位置。hashCode() 定义在Object类中,Java中的任何类都包含有hashCode() 函数,Object类的hashCode()方法返回这个对象存储的内存地址的编号。虽然每个Java类都包含hashCode() 函数。但是在散列表相关的类中才有用(确定对象在散列表中的位置),在其它情况下基本没用。什么是散列表就不介绍了,基础的数据结构
什么是equals()?
很多文章会将equals()和hashCode()放在一起解释,两者的相同点是都在Object类中定义,以及两个对象equals,则两个对象hashCode()相同(推荐的设计原则)等。所以重写equals之后也要重写hashCode()。和equals一起考察的还有==,==常用来和equals比较区别:==判断两个对象是不是同一个对象,即它们的内存地址是否一致;equals比较两个对象是否相等,即是否是同一个类型,对象内容是否一致。所以由==可以推出equals。而equals又可以推出hashCode()相等。
hashCode()遇上hashMap
使用hashMap泛型类时,将其实例化的类,要重写类的equals和hashCode()方法,才能达到我们对hashMap定义的效果。为什么这么说呢?得参考下hashMap的部分源代码。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
注意到,hashMap中存放健值对的位置,是由key的hashCode经过hash()操作后生成的。hash函数如下
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
从put()代码可以看出hashMap的插入流程:先调用hashCode方法得到该元素的hashCode值,hash()重新计算hashCode,然后查看table中是否存在该hashCode值,如果存在则调用equals方法重新确定是否存在该元素,如果存在,则更新value值,否则将新的元素添加到HashMap中。从这里可以看出,hashCode方法的存在是为了减少equals方法的调用次数,从而提高查找效率。
hash()函数是一个单调函数,返回值和h参数之间是一一映射的关系。所以如果满足equals()的两个对象,hashCode()不同,在hashMap中会被当作两个不同的对象分别插入,语义上就会造成偏差。下面的代码具体反映了偏差
class People{
private String name;
private int age;
public People(String name,int age) {
this.name = name;
this.age = age;
}
public void setAge(int age){
this.age = age;
}
@Override
public boolean equals(Object obj) {
return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;
}
}
public class Main {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
People p1 = new People("Jack", 12);
hashMap.put(p1, 1);
System.out.println(hashMap.get(new People("Jack", 12)));
}
}
发现,插入了p1,但是在get()和p1 equals的对象时,返回的却为空。因为new People(“Jack”,12)和p1的hashCode没有在People类中重写,返回的是对象默认的内存地址,而两个对象的内存地址不同,所以hashCode不同,查找hashMap时返回为null。
重写hashCode,equals原则
- 同一个对象调用多次,hashCode方法必须始终如一地返回同一个整数。
- 如果两个对象equals比较是相等的,那么调用两个对象的hashCode方法必须返回相同的整数结果。
- 如果两个对象根据equals比较是不等的,hashCode方法不一定得返回不同的整数。
对于第一点,要防止自定义的hashCode依赖对象自身的字段,比如同一个对象,如果只是修改字段的值,hashCode不应该改变。
遵守以上三点原则,在hashMap(包括hashSet,hashTable)中,就不会出现违背hashMap定义的情况
最后
本文参考了浅谈Java中的hashcode方法,深入Java集合学习系列:HashMap的实现原理。
很惭愧,做了一点微小的贡献!