- 浏览: 545636 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wa114d:
楼主工作几年了,好厉害
一个面试官对面试问题的分析 -
wobuxiaole:
Good,非常好
30岁前男人需要完成的事 -
小逗逗:
Good,非常好
30岁前男人需要完成的事 -
invincibleLiu:
好帖,要顶!(别投我隐藏啊,这是对BBS最原始一种支持)
Java:synchronized修饰符在静态方法与非静态方法上的区别 -
fayedShih:
第三题,不知道对不对
import java.util.con ...
企业牛逼面试题目 高手进来讨论答题
1.hashcode是用来查找的,如果你学过数据结构就应该知道,在查找和排序这一章有
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我 们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的余 数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除8 求余数直接找到存放的位置了。
2.但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals(),为什么还要重写hashCode()呢?
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊
3。你要对A类排序,有两种方法,一种就是让A类实现comparabole结构并实现compareTo()方法,那么可以通过Collections.sort(List <A> list)对其进行排序
另一种方法:自己定义一个类B实现Comparator类并实现compare方法,
然后通过Collections.sort(List <A> list,B b)进行排序
hashCode() 是用来产生哈希玛的,而哈希玛是用来在散列存储结构中确定对象的存储地址的,(这一段在 Java编程思想 中讲的很清楚的)象util包中的 带 hash 的集合类都是用这种存储结构 :HashMap,HashSet, 他们在将对象存储时(严格说是对象引用),需要确定他们的地址吧, 而HashCode()就是这个用途的,一般都需要重新定义它的,因为默认情况下,由 Object 类定义的 hashCode 方法会针对不同的对象返回不同的整数,这一般是通过将该对象的内部地址转换成一个整数来实现的,现在举个例子来说, 就拿HashSet来说 ,在将对象存入其中时,通过被存入对象的 hashCode() 来确定对象在 HashSet 中的存储地址,通过equals()来确定存入的对象是否重复,hashCode() ,equals()都需要自己重新定义,因为hashCode()默认前面已经说啦,而equals() 默认是比较的对象引用,你现在想一下,如果你不定义equals()的话,那么同一个类产生的两个内容完全相同的对象都可以存入Set,因为他们是通过 equals()来确定的,这样就使得HashSet 失去了他的意义,看一下下面这个:
你分别注释掉hashCode()和 equals()来比较一下他们作用就可以拉,关键要自己动手看看比较的结果你就可以记得很清楚啦
如果还不是很明确可以再看另一个例子:
还是那句话:你注释掉hashCode()比较一下他们作用就可以拉,关键要自己动手看看比较的结果你就可以记得很清楚啦
总结
hashCode() 方法使用来提高Map里面的搜索效率的,Map会根据不同的hashCode()来放在不同的桶里面,Map在搜索一个对象的时候先通过 hashCode()找到相应的桶,然后再根据equals()方法找到相应的对象.要正确的实现Map里面查找元素必须满足一下两个条件:
(1)当obj1.equals(obj2)为true时obj1.hashCode() == obj2.hashCode()必须为true
(2)当obj1.hashCode() == obj2.hashCode()为false时obj.equals(obj2)必须为false
Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。
那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是Object.equals方法了。
但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。
也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。
哈 希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。我们可以认为hashCode方法返回的就是对象存储的物理地址(实际可能并不是,例 如:通过获取对象的物理地址然后除以8再求余,余数几是计算得到的散列值,我们就认为返回一个不是物理地址的数值,而是一个可以映射到物理地址的值)。
这 样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素,它就可以直 接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列 其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次。
改写equals时总是要改写hashCode
============================================================
java.lnag.Object中对hashCode的约定:
1. 在一个应用程序执行期间,如果一个对象的equals方法做比较所用到的信息没有被修改的话,则对该对象调用hashCode方法多次,它必须始终如一地返回同一个整数。
2. 如果两个对象根据equals(Object o)方法是相等的,则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
3. 如果两个对象根据equals(Object o)方法是不相等的,则调用这两个对象中任一个对象的hashCode方法,不要求产生不同的整数结果。但如果能不同,则可能提高散列表的性能。
有一个概念要牢记,两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象。
所以hashcode相等只能保证两个对象在一个HASH表里的同一条HASH链上,继而通过equals方法才能确定是不是同一对象,如果结果为true, 则认为是同一对象不在插入,否则认为是不同对象继续插入。
从上面我们可以看到是否很可能Object.hashCode就是代表内存地址。下面我们来证明hashcode是不是真的就是Object的内存地址呢?实际上,hashcode根本不能代表object的内存地址。
-----------------------------------------
Object.hashCode不可以代表内存地址
----------------------------------------
==============================
看HashTable的源代码非常有用:
==============================
============================================================
有效和正确定义hashCode()和equals():
============================================================
级别:入门级
每个Java对象都有hashCode()和 equals()方法。许多类忽略(Override)这些方法的缺省实施,以在对象实例之间提供更深层次的语义可比性。在Java理念和实践这一部分, Java开发人员Brian Goetz向您介绍在创建Java类以有效和准确定义hashCode()和equals()时应遵循的规则和指南。您可以在讨论论坛与作者和其它读者一 同探讨您对本文的看法。(您还可以点击本文顶部或底部的讨论进入论坛。)
虽然Java语言不直接支持关联数组 -- 可以使用任何对象作为一个索引的数组 -- 但在根Object类中使用hashCode()方法明确表示期望广泛使用HashMap(及其前辈Hashtable)。理想情况下基于散列的容器提供 有效插入和有效检索;直接在对象模式中支持散列可以促进基于散列的容器的开发和使用。
定义对象的相等性
Object类有两种方法来推断对象的标识:equals()和hashCode()。一般来说,如果您忽略了其中一种,您必须同时忽略这两种,因为两者 之间有必须维持的至关重要的关系。特殊情况是根据equals() 方法,如果两个对象是相等的,它们必须有相同的hashCode()值(尽管这通常不是真的)。
特定类的equals()的语义在Implementer的左侧定义;定义对特定类来说equals()意味着什么是其设计工作的一部分。Object提供的缺省实施简单引用下面等式:
public boolean equals(Object obj) { return (this == obj); }
在这种缺省实施情况下,只有它们引用真正同一个对象时这两个引用才是相等的。同样,Object提供的 hashCode()的缺省实施通过将对象的内存地址对映于一个整数值来生成。由于在某些架构上,地址空间大于int值的范围,两个不同的对象有相同的 hashCode()是可能的。如果您忽略了hashCode(),您仍旧可以使用System.identityHashCode()方法来接入这类缺 省值。
忽略 equals() -- 简单实例
缺省情况下,equals()和hashCode()基于标识的实施是合理的,但对于某些类来说,它们希望放宽等式的定义。例如,Integer类定义equals() 与下面类似:
在这个定义中,只有在包含相同的整数值的情况下这两个Integer对象是相等的。结合将不可修改的 Integer,这使得使用Integer作为HashMap中的关键字是切实可行的。这种基于值的Equal方法可以由Java类库中的所有原始封装类 使用,如Integer、Float、Character和Boolean以及String(如果两个String对象包含相同顺序的字符,那它们是相等 的)。由于这些类都是不可修改的并且可以实施hashCode()和equals(),它们都可以做为很好的散列关键字。
为什么忽略 equals()和hashCode()?
如果Integer不忽略equals() 和 hashCode()情况又将如何?如果我们从未在HashMap或其它基于散列的集合中使用Integer作为关键字的话,什么也不会发生。但是,如果 我们在HashMap中使用这类Integer对象作为关键字,我们将不能够可靠地检索相关的值,除非我们在get()调用中使用与put()调用中极其 类似的Integer实例。这要求确保在我们的整个程序中,只能使用对应于特定整数值的Integer对象的一个实例。不用说,这种方法极不方便而且错误 频频。
Object的interface contract要求如果根据 equals()两个对象是相等的,那么它们必须有相同的hashCode()值。当其识别能力整个包含在equals()中时,为什么我们的根对象类需 要hashCode()?hashCode()方法纯粹用于提高效率。Java平台设计人员预计到了典型Java应用程序中基于散列的集合类 (Collection Class)的重要性--如Hashtable、HashMap和HashSet,并且使用equals()与许多对象进行比较在计算方面非常昂贵。使所 有Java对象都能够支持 hashCode()并结合使用基于散列的集合,可以实现有效的存储和检索。
==============================
Go deep into HashCode:
==============================
为什么HashCode对于对象是如此的重要?
一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的
Hash算法相比还不能叫真正的算法,但如何实现它,不仅仅是程序员的编程水平问题,
而是关系到你的对象在存取时性能的非常重要的问题.有可能,不同的HashCode可能
会使你的对象存取产生,成百上千倍的性能差别.
我们先来看一下,在JAVA中两个重要的数据结构:HashMap和Hashtable,虽然它们有很
大的区别,如继承关系不同,对value的约束条件(是否允许null)不同,以及线程安全性
等有着特定的区别,但从实现原理上来说,它们是一致的.所以,我们只以Hashtable来
说明:
在java中,存取数据的性能,一般来说当然是首推数组,但是在数据量稍大的容器选择中,
Hashtable将有比数据性能更高的查询速度.具体原因看下面的内容.
Hashtable在存储数据时,一般先将该对象的HashCode和0x7FFFFFFF做与操作,因为一个
对象的HashCode可以为负数,这样操作后可以保证它为一个正整数.然后以Hashtable的
长度取模,得到该对象在Hashtable中的索引.
index = (o.hashCode() & 0x7FFFFFFF)%hs.length;
这个对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象
放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接从第index
取得这个对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的查询比数据
具有更高的性能.
既然可以根据HashCode直接定位对象在Hashtable中的位置,那么为什么Hashtable
要用key来做映射呢(为了一些思维有障碍的人能看到懂我加了一句话:而不是直接放value呢)?这就是关系Hashtable性能问题的最重要的问题:Hash冲突.
常见的Hash冲突是不同对象最终产生了相同的索引,而一种非常甚至绝对少见的Hash冲突
是,如果一组对象的个数大过了int范围,而HashCode的长度只能在int范围中,所以肯定要
有同一组的元素有相同的HashCode,这样无论如何他们都会有相同的索引.当然这种极端
的情况是极少见的,可以暂不考虑,但对于相同的HashCode经过取模,则会产中相同的索引,
或者不同的对象却具有相同的HashCode,当然具有相同的索引.
所以对于索引相同的对象,在该index位置存放了多个对象,这些值要想能正确区分,就要依
靠key本身和hashCode来识别.
事实上一个设计各好的HashTable,一般来说会比较平均地分布每个元素,因为Hashtable
的长度总是比实际元素的个数按一定比例进行自增(装填因子一般为0.75)左右,这样大多
数的索引位置只有一个对象,而很少的位置会有几个对象.所以Hashtable中的每个位置存
放的是一个链表,对于只有一个对象的位置,链表只有一个首节点(Entry),Entry的next为
null.然后有hashCode,key,value属性保存了该位置的对象的HashCode,key和value(对象
本身),如果有相同索引的对象进来则会进入链表的下一个节点.如果同一个位置中有多个
对象,根据HashCode和key可以在该链表中找到一个和查询的key相匹配的对象.
从上面我看可以看到,对于HashMap和Hashtable的存取性能有重大影响的首先是应该使该
数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode
产生不同的index,但相同的HashCode一定产生相同的index,从而影响产生Hash冲突.
对于一个象,如果具有很多属性,把所有属性都参与散列,显然是一种笨拙的设计.因为对象
的HashCode()方法几乎无所不在地被自动调用,如equals比较,如果太多的对象参与了散列.
那么需要的操作常数时间将会增加很大.所以,挑选哪些属性参与散列绝对是一个编程水平
的问题.
从实现来说,一般的HashCode方法会这样:
return Attribute1.HashCode() + Attribute2.HashCode()...[+super.HashCode()],
我们知道,每次调用这个方法,都要重新对方法内的参与散列的对象重新计算一次它们的
HashCode的运算,如果一个对象的属性没有改变,仍然要每次都进行计算,所以如果设置一
个标记来缓存当前的散列码,只要当参与散列的对象改变时才重新计算,否则调用缓存的
hashCode,这可以从很大程度上提高性能.
默认的实现是将对象内部地址转化为整数作为HashCode,这当然能保证每个对象具有不同
的HasCode,因为不同的对象内部地址肯定不同(废话),但java语言并不能让程序员获取对
象内部地址,所以,让每个对象产生不同的HashCode有着很多可研究的技术.
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我 们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的余 数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除8 求余数直接找到存放的位置了。
2.但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals(),为什么还要重写hashCode()呢?
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊
3。你要对A类排序,有两种方法,一种就是让A类实现comparabole结构并实现compareTo()方法,那么可以通过Collections.sort(List <A> list)对其进行排序
另一种方法:自己定义一个类B实现Comparator类并实现compare方法,
然后通过Collections.sort(List <A> list,B b)进行排序
hashCode() 是用来产生哈希玛的,而哈希玛是用来在散列存储结构中确定对象的存储地址的,(这一段在 Java编程思想 中讲的很清楚的)象util包中的 带 hash 的集合类都是用这种存储结构 :HashMap,HashSet, 他们在将对象存储时(严格说是对象引用),需要确定他们的地址吧, 而HashCode()就是这个用途的,一般都需要重新定义它的,因为默认情况下,由 Object 类定义的 hashCode 方法会针对不同的对象返回不同的整数,这一般是通过将该对象的内部地址转换成一个整数来实现的,现在举个例子来说, 就拿HashSet来说 ,在将对象存入其中时,通过被存入对象的 hashCode() 来确定对象在 HashSet 中的存储地址,通过equals()来确定存入的对象是否重复,hashCode() ,equals()都需要自己重新定义,因为hashCode()默认前面已经说啦,而equals() 默认是比较的对象引用,你现在想一下,如果你不定义equals()的话,那么同一个类产生的两个内容完全相同的对象都可以存入Set,因为他们是通过 equals()来确定的,这样就使得HashSet 失去了他的意义,看一下下面这个:
public class Test { public static void main(String[] args) { HashSet set = new HashSet(); for (int i = 0; i <= 3; i++){ set.add(new Demo1(i,i)); } System.out.println(set); set.add(new Demo1(1,1)); System.out.println(set); System.out.println(set.contains(new Demo1(0,0))); System.out.println(set.add(new Demo1(1,1))); System.out.println(set.add(new Demo1(4,4))); System.out.println(set); } private static class Demo1 { private int value; private int id; public Demo1(int value,int id) { this.value = value; this.id=id; } public String toString() { return " value = " + value; } public boolean equals(Object o) { Demo1 a = (Demo1) o; return (a.value == value) ? true : false; } public int hashCode() { return id; } } }
你分别注释掉hashCode()和 equals()来比较一下他们作用就可以拉,关键要自己动手看看比较的结果你就可以记得很清楚啦
如果还不是很明确可以再看另一个例子:
public final class Test { public static void main(String[] args) { Map m = new HashMap(); m.put(new PhoneNumber(020, 12345678), "shellfeng"); System.out.println(m.get(new PhoneNumber(020, 12345678))); } private static class PhoneNumber { /** * 区号 */ private short areaCode; /** * 扩展号 */ private short extension; public PhoneNumber(int areaCode, int extension) { this.areaCode = (short) areaCode; this.extension = (short) extension; } public boolean equals(Object o) { if (o == this) { return true; } if (!(o instanceof PhoneNumber)) { return false; } PhoneNumber pn = (PhoneNumber) o; return pn.extension == extension && pn.areaCode == areaCode; } /** * @see java.lang.Object#hashCode() * @return result就是我们得到的散列值,其实我们的计算过程可以多种,这里只不过是一个例子,需要你的灵活运用,使其接近你需要的理想结果 */ public int hashCode() { int result = 17; result = 37 * result + areaCode; result = 37 * result + extension; return result; } } }
还是那句话:你注释掉hashCode()比较一下他们作用就可以拉,关键要自己动手看看比较的结果你就可以记得很清楚啦
总结
hashCode() 方法使用来提高Map里面的搜索效率的,Map会根据不同的hashCode()来放在不同的桶里面,Map在搜索一个对象的时候先通过 hashCode()找到相应的桶,然后再根据equals()方法找到相应的对象.要正确的实现Map里面查找元素必须满足一下两个条件:
(1)当obj1.equals(obj2)为true时obj1.hashCode() == obj2.hashCode()必须为true
(2)当obj1.hashCode() == obj2.hashCode()为false时obj.equals(obj2)必须为false
Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。
那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是Object.equals方法了。
但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。
也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。
哈 希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。我们可以认为hashCode方法返回的就是对象存储的物理地址(实际可能并不是,例 如:通过获取对象的物理地址然后除以8再求余,余数几是计算得到的散列值,我们就认为返回一个不是物理地址的数值,而是一个可以映射到物理地址的值)。
这 样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素,它就可以直 接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列 其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次。
改写equals时总是要改写hashCode
============================================================
java.lnag.Object中对hashCode的约定:
1. 在一个应用程序执行期间,如果一个对象的equals方法做比较所用到的信息没有被修改的话,则对该对象调用hashCode方法多次,它必须始终如一地返回同一个整数。
2. 如果两个对象根据equals(Object o)方法是相等的,则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
3. 如果两个对象根据equals(Object o)方法是不相等的,则调用这两个对象中任一个对象的hashCode方法,不要求产生不同的整数结果。但如果能不同,则可能提高散列表的性能。
有一个概念要牢记,两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象。
所以hashcode相等只能保证两个对象在一个HASH表里的同一条HASH链上,继而通过equals方法才能确定是不是同一对象,如果结果为true, 则认为是同一对象不在插入,否则认为是不同对象继续插入。
public String toString () { return this.getClass().getName() + "@" + Integer.toHexString(this.hashCode()); } public boolean equals (Object o) { return this == o; /** * Answers an integer hash code for the receiver. Any two * objects which answer <code>true</code> when passed to * <code>.equals</code> must answer the same value for this * method. * * @author OTI * @version initial * * @return int * the receiver's hash. * * @see #equals */ public native int hashCode();}
从上面我们可以看到是否很可能Object.hashCode就是代表内存地址。下面我们来证明hashcode是不是真的就是Object的内存地址呢?实际上,hashcode根本不能代表object的内存地址。
-----------------------------------------
Object.hashCode不可以代表内存地址
----------------------------------------
package com.tools; import java.util.ArrayList; /** * 此方法的作用是证明 java.lang.Object的hashcode 不是代表 对象所在内存地址。 * 我产生了10000个对象,这10000个对象在内存中是不同的地址,但是实际上这10000个对象 * 的hashcode的是完全可能相同的 */ public class HashCodeMeaning { public static void main(String[] args) { ArrayList list = new ArrayList(); int numberExist=0; //证明hashcode的值不是内存地址 for (int i = 0; i < 10000; i++) { Object obj=new Object(); if (list.contains(obj.toString())) { System.out.println(obj.toString() +" exists in the list. "+ i); numberExist++; } else { list.add(obj.toString()); } } System.out.println("repetition number:"+numberExist); System.out.println("list size:"+list.size()); //证明内存地址是不同的。 numberExist=0; list.clear(); for (int i = 0; i < 10000; i++) { Object obj=new Object(); if (list.contains(obj)) { System.out.println(obj +" exists in the list. "+ i); numberExist++; } else { list.add(obj); } } System.out.println("repetition number:"+numberExist); System.out.println("list size:"+list.size()); } }
==============================
看HashTable的源代码非常有用:
==============================
============================================================
有效和正确定义hashCode()和equals():
============================================================
级别:入门级
每个Java对象都有hashCode()和 equals()方法。许多类忽略(Override)这些方法的缺省实施,以在对象实例之间提供更深层次的语义可比性。在Java理念和实践这一部分, Java开发人员Brian Goetz向您介绍在创建Java类以有效和准确定义hashCode()和equals()时应遵循的规则和指南。您可以在讨论论坛与作者和其它读者一 同探讨您对本文的看法。(您还可以点击本文顶部或底部的讨论进入论坛。)
虽然Java语言不直接支持关联数组 -- 可以使用任何对象作为一个索引的数组 -- 但在根Object类中使用hashCode()方法明确表示期望广泛使用HashMap(及其前辈Hashtable)。理想情况下基于散列的容器提供 有效插入和有效检索;直接在对象模式中支持散列可以促进基于散列的容器的开发和使用。
定义对象的相等性
Object类有两种方法来推断对象的标识:equals()和hashCode()。一般来说,如果您忽略了其中一种,您必须同时忽略这两种,因为两者 之间有必须维持的至关重要的关系。特殊情况是根据equals() 方法,如果两个对象是相等的,它们必须有相同的hashCode()值(尽管这通常不是真的)。
特定类的equals()的语义在Implementer的左侧定义;定义对特定类来说equals()意味着什么是其设计工作的一部分。Object提供的缺省实施简单引用下面等式:
public boolean equals(Object obj) { return (this == obj); }
在这种缺省实施情况下,只有它们引用真正同一个对象时这两个引用才是相等的。同样,Object提供的 hashCode()的缺省实施通过将对象的内存地址对映于一个整数值来生成。由于在某些架构上,地址空间大于int值的范围,两个不同的对象有相同的 hashCode()是可能的。如果您忽略了hashCode(),您仍旧可以使用System.identityHashCode()方法来接入这类缺 省值。
忽略 equals() -- 简单实例
缺省情况下,equals()和hashCode()基于标识的实施是合理的,但对于某些类来说,它们希望放宽等式的定义。例如,Integer类定义equals() 与下面类似:
public boolean equals(Object obj) { return (obj instanceof Integer && intValue() == ((Integer) obj).intValue()); }
在这个定义中,只有在包含相同的整数值的情况下这两个Integer对象是相等的。结合将不可修改的 Integer,这使得使用Integer作为HashMap中的关键字是切实可行的。这种基于值的Equal方法可以由Java类库中的所有原始封装类 使用,如Integer、Float、Character和Boolean以及String(如果两个String对象包含相同顺序的字符,那它们是相等 的)。由于这些类都是不可修改的并且可以实施hashCode()和equals(),它们都可以做为很好的散列关键字。
为什么忽略 equals()和hashCode()?
如果Integer不忽略equals() 和 hashCode()情况又将如何?如果我们从未在HashMap或其它基于散列的集合中使用Integer作为关键字的话,什么也不会发生。但是,如果 我们在HashMap中使用这类Integer对象作为关键字,我们将不能够可靠地检索相关的值,除非我们在get()调用中使用与put()调用中极其 类似的Integer实例。这要求确保在我们的整个程序中,只能使用对应于特定整数值的Integer对象的一个实例。不用说,这种方法极不方便而且错误 频频。
Object的interface contract要求如果根据 equals()两个对象是相等的,那么它们必须有相同的hashCode()值。当其识别能力整个包含在equals()中时,为什么我们的根对象类需 要hashCode()?hashCode()方法纯粹用于提高效率。Java平台设计人员预计到了典型Java应用程序中基于散列的集合类 (Collection Class)的重要性--如Hashtable、HashMap和HashSet,并且使用equals()与许多对象进行比较在计算方面非常昂贵。使所 有Java对象都能够支持 hashCode()并结合使用基于散列的集合,可以实现有效的存储和检索。
==============================
Go deep into HashCode:
==============================
为什么HashCode对于对象是如此的重要?
一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的
Hash算法相比还不能叫真正的算法,但如何实现它,不仅仅是程序员的编程水平问题,
而是关系到你的对象在存取时性能的非常重要的问题.有可能,不同的HashCode可能
会使你的对象存取产生,成百上千倍的性能差别.
我们先来看一下,在JAVA中两个重要的数据结构:HashMap和Hashtable,虽然它们有很
大的区别,如继承关系不同,对value的约束条件(是否允许null)不同,以及线程安全性
等有着特定的区别,但从实现原理上来说,它们是一致的.所以,我们只以Hashtable来
说明:
在java中,存取数据的性能,一般来说当然是首推数组,但是在数据量稍大的容器选择中,
Hashtable将有比数据性能更高的查询速度.具体原因看下面的内容.
Hashtable在存储数据时,一般先将该对象的HashCode和0x7FFFFFFF做与操作,因为一个
对象的HashCode可以为负数,这样操作后可以保证它为一个正整数.然后以Hashtable的
长度取模,得到该对象在Hashtable中的索引.
index = (o.hashCode() & 0x7FFFFFFF)%hs.length;
这个对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象
放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接从第index
取得这个对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的查询比数据
具有更高的性能.
既然可以根据HashCode直接定位对象在Hashtable中的位置,那么为什么Hashtable
要用key来做映射呢(为了一些思维有障碍的人能看到懂我加了一句话:而不是直接放value呢)?这就是关系Hashtable性能问题的最重要的问题:Hash冲突.
常见的Hash冲突是不同对象最终产生了相同的索引,而一种非常甚至绝对少见的Hash冲突
是,如果一组对象的个数大过了int范围,而HashCode的长度只能在int范围中,所以肯定要
有同一组的元素有相同的HashCode,这样无论如何他们都会有相同的索引.当然这种极端
的情况是极少见的,可以暂不考虑,但对于相同的HashCode经过取模,则会产中相同的索引,
或者不同的对象却具有相同的HashCode,当然具有相同的索引.
所以对于索引相同的对象,在该index位置存放了多个对象,这些值要想能正确区分,就要依
靠key本身和hashCode来识别.
事实上一个设计各好的HashTable,一般来说会比较平均地分布每个元素,因为Hashtable
的长度总是比实际元素的个数按一定比例进行自增(装填因子一般为0.75)左右,这样大多
数的索引位置只有一个对象,而很少的位置会有几个对象.所以Hashtable中的每个位置存
放的是一个链表,对于只有一个对象的位置,链表只有一个首节点(Entry),Entry的next为
null.然后有hashCode,key,value属性保存了该位置的对象的HashCode,key和value(对象
本身),如果有相同索引的对象进来则会进入链表的下一个节点.如果同一个位置中有多个
对象,根据HashCode和key可以在该链表中找到一个和查询的key相匹配的对象.
从上面我看可以看到,对于HashMap和Hashtable的存取性能有重大影响的首先是应该使该
数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode
产生不同的index,但相同的HashCode一定产生相同的index,从而影响产生Hash冲突.
对于一个象,如果具有很多属性,把所有属性都参与散列,显然是一种笨拙的设计.因为对象
的HashCode()方法几乎无所不在地被自动调用,如equals比较,如果太多的对象参与了散列.
那么需要的操作常数时间将会增加很大.所以,挑选哪些属性参与散列绝对是一个编程水平
的问题.
从实现来说,一般的HashCode方法会这样:
return Attribute1.HashCode() + Attribute2.HashCode()...[+super.HashCode()],
我们知道,每次调用这个方法,都要重新对方法内的参与散列的对象重新计算一次它们的
HashCode的运算,如果一个对象的属性没有改变,仍然要每次都进行计算,所以如果设置一
个标记来缓存当前的散列码,只要当参与散列的对象改变时才重新计算,否则调用缓存的
hashCode,这可以从很大程度上提高性能.
默认的实现是将对象内部地址转化为整数作为HashCode,这当然能保证每个对象具有不同
的HasCode,因为不同的对象内部地址肯定不同(废话),但java语言并不能让程序员获取对
象内部地址,所以,让每个对象产生不同的HashCode有着很多可研究的技术.
发表评论
-
ConcurrentHashMap在jdk1.7和jdk1.8中的不同
2021-12-02 17:30 0https://blog.csdn.net/qq_418849 ... -
CallableAndFuture
2012-07-24 11:31 1174import java.util.concurrent.Cal ... -
CountDownLatch
2012-07-24 11:00 1174concurrent包里面的CountDownLatch其实可 ... -
认识理解Java中native方法
2011-11-02 16:35 2357Java不是完美的,Java的不足除了体现在运行速度 ... -
java 数组复制:System.arrayCopy 深入解析
2011-11-02 10:02 4165转载:http://happyjin2010.it ... -
java proxy
2011-07-12 16:31 936代理?就是别人帮你管理叫代理. 举个例子 你是家里的主人, ... -
关于 JVM 命令行标志您不知道的 5 件事(来自IBM)
2010-11-29 17:10 963JVM 是多数开发人员视为理所当然的 Java 功能和性能背后 ... -
关于 Java Collections API 您不知道的 5 件事,第 1 部分(转自IBM)
2010-11-29 16:58 981对于很多 Java 开发人员 ... -
java线程安全总结(转载jameswxx)
2010-11-29 12:50 1364最近想将java基础的一些 ... -
说说new Integer和Integer.valueOf(转载jameswxx)
2010-11-29 12:23 1639看看这两个语句 Integer a=new Integer ... -
优化JVM参数提高eclipse运行速度
2010-11-26 16:13 881性能优化从身边做起。 首先建立评估体系,将workspac ... -
主题:一次Java垃圾收集调优实战
2010-11-26 15:29 11251 资料 •JDK5.0垃圾收集优化之--Don't Paus ... -
通过GC输出分析内存泄露问题
2010-11-26 15:13 1023SIP5.0以后服务的请求量爆发性增长,因此也暴露了原来没有暴 ... -
15种提高系统伸缩性和性能的最佳实践
2010-11-25 16:00 9931, 提高系统性能, 需要尽早做性能剖析, 而且要经常做.当项 ... -
JVM调优总结(一)-- 一些概念
2010-11-25 15:00 890数据类型 Java虚拟机中,数据类型可以分为两类:基本 ... -
DCL,双重检查(来自annegu)
2010-09-05 16:25 924对于多线程编程来说, ... -
JVM原理学习笔记一
2010-06-11 16:22 901最近在阅读 《Inside the J ... -
ImportDataFromMySQLToOracle
2009-12-10 10:42 1340import java.sql.Connection; im ... -
Merge two Hashtable<String, Integer>
2009-12-03 14:50 1357private static Hashtable< ... -
TreeMap 排序重写
2009-12-03 14:40 4417import java.util.Comparator; i ...
相关推荐
- **性能考虑**: 为了提高性能,只有当两个对象的`hashCode`相同的情况下,才会调用`equals`方法进行深度比较。 - **一致性要求**: `equals`方法需要满足对称性、反射性、传递性和一致性等性质,以确保集合操作的...
【面试】中提到的几个关键知识点集中在对象比较、equals()和hashCode()方法的使用以及它们之间的关系上。这些概念在Java编程中至关重要,特别是在处理集合类和比较对象时。 1、**hashCode与equals两者之间的关系**...
在面试中,面试官可能会问到如何正确实现equals()和hashCode(),或者关于“==”和equals()在不同情况下的行为的问题。熟悉这些知识点不仅可以帮助你通过面试,还能提升你的编程素养,确保在实际开发中写出更健壮的...
桶的深度是一个什么概念呢,桶的深度是指具有相同hashcode值的元素的个数,也就是发生哈希碰撞的元素的个数。 一个好的哈希算法应该尽量减少哈希碰撞的次数。在String类中,哈希算法的实现主要体现在hashCode()方法...
本讲将深度剖析Java中的"==运算符"和"equals()方法",这两个是判断对象之间相等性的主要手段。 一、"=="运算符 "=="运算符在Java中用于比较基本类型的值是否相等,例如int、char、boolean等。对于引用类型的变量,...
面试题可能涉及它们的重写规则,以及为何要在重写`equals()`时同时重写`hashCode()`。 ### 方法重写(Override) 方法重写是子类继承父类时对父类方法的一种定制。面试中可能会问及方法重写的条件、注意事项,以及`@...
JavaSE是Java编程的基础部分,面试中经常涉及的Java基础知识包括变量存储位置、equals和hashcode的重写、Map的分类及其特点、Object的hashCode方法、以及==运算符的使用等。以下是对这些知识点的详细解释: 1. **...
Java 7引入了`java.util.Objects`类,其中的`equals()`方法可以方便地比较基本类型和对象,而`deepEquals()`方法用于比较两个对象数组或复杂嵌套的对象结构,它会进行深度比较。 **5. 实现Comparable接口** 除了`...
5. **hashCode()和equals()方法的重要性**:在HashMap中,hashCode()方法用于确定键值对的索引,而equals()方法用于比较两个键是否相等。如果两个不同的对象通过hashCode()方法得到的哈希值相同,且equals()方法返回...
3. **hashCode()与equals()的关系** `hashCode()`方法返回对象的哈希码,用于在哈希表(如HashMap)中快速定位对象。两个对象的`hashCode()`相同,并不意味着它们`equals()`一定为true。根据Java的约定,如果两个...
同时,如果重写了`equals()`,也应该重写`hashCode()`,因为`equals()`相等的两个对象其`hashCode()`也应相等,这对于使用哈希表(如HashMap)的场景尤为重要。`hashCode()`返回的是对象的散列值,用于快速定位对象...
equals() 方法和 hashCode() 方法是 Java 中两个非常重要的方法,它们的作用是分别比较两个对象的值和哈希值。图 2 展示了这两个方法的区别: * 如果两个对象相等(equal),那么他们一定有相同的哈希值。 * 如果两...
它基于词法分析和语法分析的原理,将SQL语句转换为抽象语法树(AST),从而方便对SQL进行深度处理。通过这个模块,开发者可以轻松获取SQL的结构信息,例如表名、字段名、数据类型等,这对于自动化代码生成非常有帮助...
- **equals()与hashCode()**:在"相等性(==及equals方法)详解.swf"中,会深入讨论这两个方法的区别和何时重写它们。 3. **异常处理** - **try-catch-finally**:理解如何捕获和处理异常,以及finally块的作用。...
3. **hashCode()和equals()方法**: - **关键作用**:在HashMap中,这两个方法用于确定键的唯一性。正确的`hashCode()`实现确保不同键有不同哈希值,`equals()`确保键的比较逻辑。不正确的实现可能导致键值对的错误...
《SpringBoot与Lombok插件的深度解析及应用实践》 在Java开发中,SpringBoot以其简洁、快速的特性受到了广大开发者的喜爱。与此同时,Lombok这个轻量级库也因其自动化代码生成的能力,极大地提高了开发效率,成为了...
Java面试的深度和广度随着技术的发展而不断提升,面试题目的范围从基本概念扩展到了更为高级和复杂的领域。本文将围绕Java面试中的关键知识点进行详细阐述。 首先,多线程和并发是Java开发者必备的技能之一。面试中...
由于`equals()`不相等,根据Java的约定,`hashCode()`也应返回不同的值,因此`a.hashCode() == b.hashCode()`返回`false`。 2. 程序输出分析: ```java public static void certkiller(String str) { int check = ...