热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

JavaHashMap实现原理0——从hashCode,equals说起

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) {
// HashMap允许存放null键和null值。
// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的hashCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值所对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
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;
}
}
// 如果i索引处的Entry为null,表明此处还没有Entry。
// modCount记录HashMap中修改结构的次数
modCount++;
// 将key、value添加到i索引处。
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);
//System.out.println(p1.hashCode());
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原则

  1. 同一个对象调用多次,hashCode方法必须始终如一地返回同一个整数。
  2. 如果两个对象equals比较是相等的,那么调用两个对象的hashCode方法必须返回相同的整数结果。
  3. 如果两个对象根据equals比较是不等的,hashCode方法不一定得返回不同的整数。

对于第一点,要防止自定义的hashCode依赖对象自身的字段,比如同一个对象,如果只是修改字段的值,hashCode不应该改变。

遵守以上三点原则,在hashMap(包括hashSet,hashTable)中,就不会出现违背hashMap定义的情况

最后

本文参考了浅谈Java中的hashcode方法,深入Java集合学习系列:HashMap的实现原理。
很惭愧,做了一点微小的贡献!


推荐阅读
author-avatar
Resolve
愿你的生活,既有软肋又有盔甲!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有