Java中hashcode的理解

本文隶属于分类

编程语言

广告推荐

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

标签:instance   论坛   区分   instant   hset   col   又一   guid   ray   

Java中hashcode的理解

原文链接http://blog.csdn.net/chinayuan/article/details/3345559

怎样理解hashCode的作用:

以 java.lang.Object来理解,JVM每new一个Object,它都会将这个Object丢到一个Hash哈希表中去,这样的话,下次做 Object的比較或者取这个对象的时候,它会依据对象的hashcode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。详细过程是这 样:
1.new Object(),JVM依据这个对象的Hashcode值,放入到相应的Hash表相应的Key上,假设不同的对象确产生了同样的hash值,也就是发 生了Hash key同样导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将全部产生同样hashcode的对象放到这个单链表上去,串在一起。
2.比較两个对象的时候,首先依据他们的 hashcode去hash表中找他的对象,当两个对象的hashcode同样,那么就是说他们这两个对象放在Hash表中的同一个key上,那么他们一 定在这个key上的链表上。

那么此时就仅仅能依据Object的equal方法来比較这个对象是否equal。当两个对象的hashcode不同的话,肯定 他们不能equal.

============================================================

改写equals时总是要改写hashCode

java.lang.Object中对hashCode的约定:

  1. 在一个应用程序运行期间,假设一个对象的equals方法做比較所用到的信息没有被改动的话。则对该对象调用hashCode方法多次,它必须始终如一地返回同一个整数。
  2. 假设两个对象依据equals(Object o)方法是相等的,则调用这两个对象中任一对象的hashCode方法必须产生同样的整数结果。
  3. 假设两个对象依据equals(Object o)方法是不相等的。则调用这两个对象中任一个对象的hashCode方法。不要求产生不同的整数结果。但假设能不同,则可能提高散列表的性能。

有一个概念要牢记。两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象。

所以hashcode相等仅仅能保证两个对象在一个HASH表里的同一条HASH链上,继而通过equals方法才干确定是不是同一对象,假设结果为true, 则觉得是同一对象在插入。否则觉得是不同对象继续插入。

Object的代码:
public String toString () {
return this.getClass().getName() + “@” + Integer.toHexString(this.hashCode());
}

public boolean equals (Object o) {
return this == o;
}

public native int hashCode();

从上面我们能够看到是否非常可能Object.hashCode就是代表内存地址。以下我们来证明hashcode是不是真的就是Object的内存地址呢?实际上,hashcode根本不能代表object的内存地址。

Object.hashCode不能够代表内存地址

package com.tools;

import java.util.ArrayList;

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方法使用简单介绍

Hash表数据结构常识:
一、哈希表基于数组。
二、缺点:基于数组的。数组创建后难以扩展。

某些哈希表被基本填满时。性能下降得非常严重。
三、没有一种简便得方法能够以不论什么一种顺序遍历表中数据项。
四、假设不须要有序遍历数据,并且能够提前预測数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

一、为什么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来做映射呢?这就是关系Hashtable性能问题的最重要的问题:Hash冲突.
常 见的Hash冲突是不同对象终于产生了同样的索引。而一种非常甚至绝对少见的Hash冲突是,假设一组对象的个数大过了int范围。而HashCode的 长度仅仅能在int范围中,所以肯定要有同一组的元素有同样的HashCode,这样不管怎样他们都会有同样的索引.当然这样的极端的情况是极少见的。能够暂 不考虑,可是对于同的HashCode经过取模,则会产中同样的索引,或者不同的对象却具有同样的HashCode,当然具有同样的索引.
所以对于索引同样的对象,在该index位置存放了多个值,这些值要想能正确区分。就要依靠key来识别.
事 实上一个设计各好的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() Attribute1.HashCode()..[ super.HashCode()],我们知道,每次调用这种方法,都要又一次对方法内的參与散列的对象又一次计算一次它们的HashCode的运算。假设一 个对象的属性没有改变。仍然要每次都进行计算。所以假设设置一个标记来缓存当前的散列码。仅仅要当參与散列的对象改变时才又一次计算。否则调用缓存的 hashCode,这能够从非常大程度上提高性能.
默认的实现是将对象内部地址转化为整数作为HashCode。这当然能保证每一个对象具有不同的HasCode。由于不同的对象内部地址肯定不同(废话)。但java语言并不能让程序猿获取对象内部地址。所以,让每一个对象产生不同的HashCode有着非常多可研究的技术.
如 果从多个属性中採样出能具有平均分布的hashCode的属性,这是一个性能和多样性相矛盾的地方。假设全部属性都參与散列,当然hashCode的多样 性将大大提高。但牺牲了性能,而假设仅仅能少量的属性採样散列,极端情况会产生大量的散列冲突,如对”人”的属性中,假设用性别而不是姓名或出生日期。那将 仅仅有两个或几个可选的hashcode值,将产生一半以上的散列冲突.所以假设可能的条件下。专门产生一个序列用来生成HashCode将是一个好的选择 (当然产生序列的性能要比全部属性參与散列的性能高的情况下才行,否则还不如直接用全部属性散列).
怎样对HashCode的性能和多样性求得一个平衡,能够參考相关算法设计的书,事实上并不一定要求非常的优秀,仅仅要能尽最大可能减少散列值的聚集.重要的是我们应该记得HashCode对于我们的程序性能有着重要的影响。在程序设计时应该时时加以注意.
请记住:假设你想有效的使用HashMap。你就必须重写在其的HashCode()。


还有两条重写HashCode()的原则:
不 必对每一个不同的对象都产生一个唯一的hashcode,仅仅要你的HashCode方法使get()能够得到put()放进去的内容就能够了。

即“不为一原 则”。生成hashcode的算法尽量使hashcode的值分散一些, 不要非常多hashcode都集中在一个范围内。这样有利于提高HashMap的性能。

即“分散原则”。

至于第二条原则的详细原因,有兴趣者能够參考 Bruce Eckel的《Thinking in Java》,
在那里有对HashMap内部实现原理的介绍,这里就不赘述了。
掌握 了这两条原则。你就能够用好HashMap编写自己的程序了。

不知道大家注意没有。 java.lang.Object中提供的三个方法:clone(),equals()和hashCode()尽管非常典型,但在非常多情况下都不能够适用。 它们仅仅是简单的由对象的地址得出结果。

这就须要我们在自己的程序中重写它们,事实上java类库中也重写了千千万万个这样的方法。利用面向对象的多态性—— 覆盖,Java的设计者非常优雅的构建了Java的结构,也更加体现了Java是一门纯OOP语言的特性。
Java提供的Collection和Map的功能是十分强大的。它们能够使你的程序实现方式更为灵活,运行效率更高。希望本文能够对大家更好的使用HashMap有所帮助。

hashcode理论与实践:
有效和正确定义hashCode()和equals()
每一个Java对象都有hashCode()和 equals()方法。

很多类忽略(Override)这些方法的缺省实施,以在对象实例之间提供更深层次的语义可比性。


虽 然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中的keyword是切实可行的。这样的基于值的Equal方法能够由Java类库中的全部原始封装类使用。如Integer、Float、 Character和Boolean以及String(假设两个String对象包括同样顺序的字符,那它们是相等的)。由于这些类都是不可改动的并且可 以实施hashCode()和equals()。它们都能够做为非常好的散列keyword。
为什么忽略 equals()和hashCode()?
如 果Integer不忽略equals() 和 hashCode()情况又将怎样?假设我们从未在HashMap或其他基于散列的集合中使用Integer作为keyword的话。什么也不会发生。可是,假设 我们在HashMap中使用这类Integer对象作为keyword,我们将不能够可靠地检索相关的值,除非我们在get()调用中使用与put()调用中极其 相似的Integer实例。

这要求确保在我们的整个程序中,仅仅能使用相应于特定整数值的Integer对象的一个实例。不用说,这样的方法极不方便并且错误 频频。
Object的interface contract要求假设依据 equals()两个对象是相等的,那么它们必须有同样的hashCode()值。

当其识别能力整个包括在equals()中时,为什么我们的根对象类需 要hashCode()?hashCode()方法纯粹用于提高效率。Java平台设计人员估计到了典型Java应用程序中基于散列的集合类 (Collection Class)的重要性–如Hashtable、HashMap和HashSet,并且使用equals()与很多对象进行比較在计算方面非常昂贵。使所 有Java对象都能够支持 hashCode()并结合使用基于散列的集合。能够实现有效的存储和检索。

实施equals()和hashCode()的需求
实施equals()和 hashCode()有一些限制,Object文件里列举出了这些限制。

特别是equals()方法必须显示以下属性:
Symmetry:两个引用,a和 b,a.equals(b) if and only if b.equals(a)
Reflexivity:全部非空引用, a.equals(a)
Transitivity:If a.equals(b) and b.equals(c), then a.equals(c)
Consistency with hashCode():两个相等的对象必须有同样的hashCode()值
Object 的规范中并没有明白要求equals()和 hashCode() 必须一致 – 它们的结果在随后的调用中将是同样的。假设“不改变对象相等性比較中使用的不论什么信息。”这听起来象“计算的结果将不改变,除非实际情况如此。”这一模糊声 明通常解释为相等性和散列值计算应是对象的可确定性功能,而不是其他。
对象相等性意味着什么?
人们非常easy满足Object类规范对 equals() 和 hashCode() 的要求。决定是否和怎样忽略equals()除了判断以外。还要求其他。

在简单的不可修值类中,如Integer(事实上是差点儿全部不可改动的类),选择 相当明显 – 相等性应基于基本对象状态的相等性。在Integer情况下,对象的唯一状态是主要的整数值。
对于可改动对象来说,答案并不总 是如此清楚。

equals() 和hashCode() 是否应基于对象的标识(象缺省实施)或对象的状态(象Integer和String)?没有简单的答案 – 它取决于类的计划使用。

对于象List和Map这样的容器来说。人们对此争论不已。Java类库中的大多数类,包括容器类,错误出如今依据对象状态来提供 equals()和hashCode()实施。
假设对象的hashCode()值能够基于其状态进行更改,那么当使用这类对象作为基于散列的集 合中的keyword时我们必须注意。确保当它们用于作为散列keyword时,我们并不同意更改它们的状态。全部基于散列的集合假设,当对象的散列值用于作为集合中的关 键字时它不会改变。

假设当keyword在集合中时它的散列代码被更改,那么将产生一些不可预測和easy混淆的结果。

实践过程中这通常不是问题 – 我们并不常常使用象List这样的可改动对象做为HashMap中的keyword。
一个简单的可改动类的样例是Point,它依据状态来定义equals()和hashCode()。假设两个Point 对象引用同样的(x, y)座标。Point的散列值来源于x和y座标值的IEEE 754-bit表示,那么它们是相等的。


对 于比較复杂的类来说,equals()和hashCode()的行为可能甚至受到superclass或interface的影响。比如,List接口要 求假设并且仅仅有还有一个对象是List,并且它们有同样顺序的同样的Elements(由Element上的Object.equals() 定义),List对象等于还有一个对象。

hashCode()的需求更特殊–list的hashCode()值必须符合以下计算:
hashCode = 1;
Iterator i = list.iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ?

0 : obj.hashCode());
}
不仅仅散列值取决于list的内容,并且还规定了结合各个Element的散列值的特殊算法。

(String类规定相似的算法用于计算String的散列值。

)
编写自己的equals()和hashCode()方法
忽 略缺省的equals()方法比較简单,但假设不违反对称(Symmetry)或传递性(Transitivity)需求,忽略已经忽略的 equals() 方法极其棘手。当忽略equals()时。您应该总是在equals()中包括一些Javadoc凝视。以帮助那些希望能够正确扩展您的类的用户。
作为一个简单的样例,考虑以下类:
class A {
final B someNonNullField;
C someOtherField;
int someNonStateField;
}
我们应怎样编写该类的equals()的方法?这样的方法适用于很多情况:
public boolean equals(Object other) {
// Not strictly necessary, but often a good optimization
if (this == other)
return true;
if (!(other instanceof A))
return false;

A otherA = (A) other;
return
(someNonNullField.equals(otherA.someNonNullField))
&& ((someOtherField == null)
? otherA.someOtherField == null
someOtherField.equals(otherA.someOtherField)));
}
如今我们定义了equals(),我们必须以统一的方法来定义hashCode()。一种统一但并不总是有效的定义hashCode()的方法例如以下:
public int hashCode() { return 0; }
这样的方法将生成大量的条目并显著减少HashMaps的性能。但它符合规范。一个更合理的hashCode()实施应该是这样:
public int hashCode() {
int hash = 1;
hash = hash * 31 + someNonNullField.hashCode();
hash = hash * 31
+ (someOtherField == null ? 0 : someOtherField.hashCode());
return hash;
}
注 意:这两种实施都减少了类状态字段的equals()或hashCode()方法一定比例的计算能力。

依据您使用的类。您可能希望减少 superclass的equals()或hashCode()功能一部分计算能力。

对于原始字段来说,在相关的封装类中有helper功能,能够帮助创 建散列值。如Float.floatToIntBits。


编写一个完美的equals()方法是不现实的。通常。当扩展一个自身忽略了 equals()的instantiable类时,忽略equals()是不切实际的,并且编写将被忽略的equals()方法(如在抽象类中)不同于为 详细类编写equals()方法。关于实例以及说明的更详细信息请參阅Effective Java Programming Language Guide, Item 7 (參考资料) 。
有待改进?


将散列法构建到Java类库的根对象类中是一种非常明智的设计折衷方法 – 它使使用基于散列的容器变得如此简单和高效。可是,人们对Java类库中的散列算法和对象相等性的方法和实施提出了很多批评。java.util中基于散 列的容器非常方便和简便易用。但可能不适用于须要非常高性能的应用程序。尽管当中大部分将不会改变,但当您设计严重依赖于基于散列的容器效率的应用程序时 必须考虑这些因素,它们包括:
太小的散列范围。

使用int而不是long作为hashCode()的返回类型添加了散列冲突的几率。


糟糕的散列值分配。短strings和小型integers的散列值是它们自己的小整数,接近于其他“邻近”对象的散列值。一个循规导矩(Well-behaved)的散列函数将在该散列范围内更均匀地分配散列值。
无 定义的散列操作。

尽管某些类,如String和List。定义了将其Element的散列值结合到一个散列值中使用的散列算法。但语言规范不定义将多个对 象的散列值结合到新散列值中的不论什么批准的方法。我们在前面编写自己的equals()和hashCode()方法中讨论的List、String或实例类 A使用的诀窍都非常easy,但算术上还远远不够完美。类库不提供不论什么散列算法的方便实施,它能够简化更先进的hashCode()实施的创建。
当扩 展已经忽略了equals()的 instantiable类时非常难编写equals()。

当扩展已经忽略了equals()的 instantiable类时,定义equals()的“显而易见的”方式都不能满足equals()方法的对称或传递性需求。这意味着当忽略 equals()时。您必须了解您正在扩展的类的结构和实施详细信息,甚至须要暴露基本类中的机密字段,它违反了面向对象的设计的原则。
结束语
通 过统一定义equals()和hashCode()。您能够提升类作为基于散列的集合中的keyword的使用性。有两种方法来定义对象的相等性和散列值:基于标 识,它是Object提供的缺省方法;基于状态,它要求忽略equals()和hashCode()。

当对象的状态更改时假设对象的散列值发生变化,确信 当状态作为散列keyword使用时您不同意更更改其状态。

解析Java对象的equals()和hashCode()的使用:

在 Java语言中。equals()和hashCode()两个函数的使用是紧密配合的,你要是自己设计当中一个,就要设计另外一个。

在多数情况 下,这两个函数是不用考虑的。直接使用它们的默认设计就能够了。

可是在一些情况下,这两个函数最好是自己设计,才干确保整个程序的正常运行。最常见的是当 一个对象被添加收集对象(collection object)时。这两个函数必须自己设计。更细化的定义是:假设你想将一个对象A放入还有一个收集对象B里,或者使用这个对象A为查找一个元对象在收集对 象B里位置的钥匙,并支持是否容纳。删除收集对象B里的元对象这样的操作,那么,equals()和hashCode()函数必须开发人员自定义。其他情 况下,这两个函数是不须要定义的。

equals():
它是用于进行两个对象的比較的,是对象内容的比較,当然也能用于进行对 象參阅值的比較。

什么是对象參阅值的比較?就是两个參阅变量的值得比較,我们 都知道參阅变量的值事实上就是一个数字,这个数字能够看成是鉴别不同对象的代号。两个对象參阅值的比較。就是两个数字的比較。两个代号的比較。这样的比較是默 认的对象比較方式,在Object这个对象中,这样的方式就已经设计好了。

所以你也不用自己来重写,浪费不必要的时间。

对象内容的比較才是设计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”。
hashCode():
这 个函数返回的就是一个用来进行哈希操作的整型代号,请不要把这个代号和前面所说的參阅变量所代表的代号弄混了。后者不仅仅是个代号还具有在内存中才查找对 象的位置的功能。hashCode()所返回的值是用来分类对象在一些特定的收集对象中的位置。这些对象是HashMap, Hashtable, HashSet,等等。这个函数和上面的equals()函数必须自己设计。用来协助HashMap, Hashtable, HashSet,等等对自己所收集的大量对象进行搜寻和定位。

这些收集对象到底怎样工作的,想象每一个元对象hashCode是一个箱子的 编码,依照编码,每一个元对象就是依据hashCode()提供的代号归入相应的箱子里。全部的箱子加起来就是一个HashSet,HashMap,或 Hashtable对象,我们须要寻找一个元对象时,先看它的代码,就是hashCode()返回的整型值,这样我们找到它所在的箱子,然后在箱子里,每 个元对象都拿出来一个个和我们要找的对象进行对照。假设两个对象的内容相等。我们的搜寻也就结束。

这样的操作须要两个重要的信息。一是对象的 hashCode()。还有一个是对象内容对照的结果。

hashCode()的返回值和equals()的关系例如以下:

假设x.equals(y)返回“true”,那么x和y的hashCode()必须相等。


假设x.equals(y)返回“false”,那么x和y的hashCode()有可能相等,也有可能不等。

为 什么这两个规则是这样的。原因事实上非常easy,拿HashSet来说吧,HashSet能够拥有一个或很多其他的箱子,在同一个箱子中能够有一个 或很多其他的独特元对象(HashSet所容纳的必须是独特的元对象)。这个样例说明一个元对象能够和其他不同的元对象拥有同样的hashCode。可是一个 元对象仅仅能和拥有同样内容的元对象相等。

所以这两个规则必须成立。

设计这两个函数所要注意到的:
假设你设计的对象类型并不使用于收集性对象。那么没有必要自己再设计这两个函数的处理方式。这是正确的面向对象设计方法,不论什么用户一时用不到的功能,就先不要设计,以免给日后功能扩展带来麻烦。

假设你在设计时想别出心裁。不遵守以上的两套规则。那么劝你还是不要做这样想入非非的事。我还没有遇到过哪一个开发人员和我说设计这两个函数要违背前面说的两个规则,我碰到这些违反规定的情况时。都是作为设计错误处理。

当 一个对象类型作为收集型对象的元对象时。这个对象应该拥有自己处理equals(),和/或处理hashCode()的设计,并且要遵守前面所说 的两种原则。equals()先要查null和是否是同一类型。

查同一类型是为了避免出现ClassCastException这样的异常给丢出来。查 null是为了避免出现NullPointerException这样的异常给丢出来。

假设你的对象里面容纳的数据过多。那么这两个函数 equals()和hashCode()将会变得效率低。假设对象中拥有无法serialized的数据。equals()有可能在操作中出现错误。想象 一个对象x。它的一个整型数据是transient型(不能被serialize成二进制数据流)。然而equals()和hashCode()都有依靠 这个整型数据,那么,这个对象在serialization之前和之后。是否一样?答案是不一样。由于serialization之前的整型数据是有效的 数据,在serialization之后,这个整型数据的值并没有存储下来。再又一次由二进制数据流转换成对象后,两者(对象在serialization 之前和之后)的状态已经不同了。

这也是要注意的。

============================================================

有效和正确定义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中的keyword是切实可行的。这样的基于值的Equal方法能够由Java类库中的全部原始封装类 使用。如Integer、Float、Character和Boolean以及String(假设两个String对象包括同样顺序的字符。那它们是相等 的)。

由于这些类都是不可改动的并且能够实施hashCode()和equals()。它们都能够做为非常好的散列keyword。

  为什么忽略 equals()和hashCode()?

   假设Integer不忽略equals() 和 hashCode()情况又将怎样?假设我们从未在HashMap或其他基于散列的集合中使用Integer作为keyword的话。什么也不会发生。可是,假设 我们在HashMap中使用这类Integer对象作为keyword,我们将不能够可靠地检索相关的值。除非我们在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有着非常多可研究的技术.

怎样从多个属性中採样出能具有多样性的hashCode的属性,这是一个性能和多样性相矛
盾的地方,假设全部属性都參与散列,当然hashCode的多样性将大大提高,但牺牲了性能,
而假设仅仅有少量的属性採样散列,极端情况会产生大量的散列冲突,如对”人”的属性中,如
果用性别而不是姓名或出生日期,那将仅仅有两个或几个可选的hashcode值,将产生一半以上
的散列冲突.所以假设可能的条件下,专门产生一个序列用来生成HashCode将是一个好的选
择(当然产生序列的性能要比全部属性參与散列的性能高的情况下才行,否则还不如直接用
全部属性散列).

怎样对HashCode的性能和多样性求得一个平衡,能够參考相关算法设计的书,事实上并不一定
要求非常的优秀,仅仅要能尽最大可能减少散列值的聚集.重要的是我们应该记得HashCode对
于我们的程序性能有着生要的影响,在程序设计时应该时时加以注意.

Java中hashcode的理解

标签:instance   论坛   区分   instant   hset   col   又一   guid   ray   

原文:https://www.cnblogs.com/zhchoutai/p/8676351.html

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

广告推荐

讨论区