深入解析hashcode,hashMap源码

时间:2022-12-17 16:18:09

 

hashCode 的常规协定是: 

 1.在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。 
2. 如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 
3、以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。 
4、实际上,由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM 编程语言不需要这种实现技巧。) 
5、当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。

以上这段官方文档的定义,我们可以抽出成以下几个关键点:

1、hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的;

2、如果两个对象相同,就是适用于equals(java.lang.Object) 方法,那么这两个对象的hashCode一定要相同;

3、如果对象的equals方法被重写,那么对象的hashCode也尽量重写,并且产生hashCode使用的对象,一定要和equals方法中使用的一致,否则就会违反上面提到的第2点;

4、两个对象的hashCode相同,并不一定表示两个对象就相同,也就是不一定适用于equals(java.lang.Object) 方法,只能够说明这两个对象在散列存储结构中,如Hashtable,他们“存放在同一个篮子里”


再归纳一下就是hashCode是用于查找使用的,而equals是用于比较两个对象的是否相等的。以下这段话是从别人帖子回复拷贝过来的:

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()有什么用啊

一、java对象的比较

等号(==):

对比对象实例的内存地址(也即对象实例的ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等; 

equals():

对比两个对象实例是否相等。

当对象所属的类没有重写根类Object的equals()方法时,equals()判断的是对象实例的ID(内存地址),是否是同一对象实例;该方法就是使用的等号(==)的判断结果,如Object类的源代码所示:

Java代码  深入解析hashcode,hashMap源码

  1. public boolean equals(Object obj) {  
  2.       return (this == obj);  
  3. }  

 
当对象所属的类重写equals()方法(可能因为需要自己特有的“逻辑相等”概念)时,equals()判断的根据就因具体实现而异,有些类是需要比较对象的某些指或内容,如String类重写equals()来判断字符串的值是否相等。判断逻辑相等。

hashCode():

计算出对象实例的哈希码,并返回哈希码,又称为散列函数。根类Object的hashCode()方法的计算依赖于对象实例的D(内存地址),故每个Object对象的hashCode都是唯一的;当然,当对象所对应的类重写了hashCode()方法时,结果就截然不同了。


二、Java的类为什么需要hashCode?---hashCode的作用,从Java中的集合的角度看。

  总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是 Object.equals方法了。但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。   

    于是,Java采用了哈希表的原理。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。关于哈希算法,这里就不详细介绍。可以这样简单理解,hashCode方法实际上返回的就是对象存储位置的映像。   

     这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就能定位到它应该放置的存储位置。如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就表示发生冲突了,散列表对于冲突有具体的解决办法,但最终还会将新元素保存在适当的位置。这样一来,实际调用equals方法的次数就大大降低了,几乎只需要一两次。   

所以,Java对于eqauls方法和hashCode方法是这样规定的:
1、相等的对象必须具有相等的哈希码(或者散列码)。
2、如果两个对象的hashCode相同,它们并不一定相同。
   
 上述的对象相同指的是通过eqauls方法判断,结果为true。

 你当然可以不按要求去做了,但你会发现,相同的对象可以出现在Set集合中。同时,增加新元素的效率会大大下降。 

三、深入解析HashMap类的底层数据结构

Map接口
  Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个 value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。 

Hashtable类
  Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。   

    Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。
使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是”one”,”two”,”three”:
    Hashtable numbers = new Hashtable();
    numbers.put(“one”, new Integer(1));
    numbers.put(“two”, new Integer(2));
    numbers.put(“three”, new Integer(3));
  要取出一个数,比如2,用相应的key:
    Integer n = (Integer)numbers.get(“two”);
    System.out.println(“two = ” + n);

 
1.    HashMap概述:
   HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
 
2.    HashMap的数据结构:
    HashMap实际上是一个“链表散列”的数据结构,
即数组和链表的结合体。首先,HashMap类的属性中定义了Entry类型的数组。Entry类实现java.ultil.Map.Entry接口,同时每一对key和value是作为Entry类的属性被包装在Entry的类中。 

如图所示,HashMap的数据结构:

深入解析hashcode,hashMap源码
 

 

 

   HashMap的部分源码如下:

Java代码  深入解析hashcode,hashMap源码
  1. /** 
  2.  * The table, resized as necessary. Length MUST Always be a power of two. 
  3.  */  
  4.   
  5. transient Entry[] table;  
  6.    
  7. static class Entry<K,V> implements Map.Entry<K,V> {  
  8.     final K key;  
  9.     V value;  
  10.     Entry<K,V> next;  
  11.     final int hash;  
  12.     ……  
  13. }  

 
    可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。table数组的元素是Entry类型的。每个 Entry元素其实就是一个key-value对,并且它持有一个指向下一个 Entry元素的引用,这就说明table数组的每个Entry元素同时也作为某个Entry链表的首节点,指向了该链表的下一个Entry元素,这就是所谓的“链表散列”数据结构,即数组和链表的结合体。 

3.    HashMap的存取实现:

   1) 添加元素:

当我们往HashMap中put元素的时候,先根据key的重新计算元素的hashCode,根据hashCode得到这个元素在table数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

HashMap的部分源码如下:

Java代码  深入解析hashcode,hashMap源码
  1. public V put(K key, V value) {  
  2.    // HashMap允许存放null键和null值。  
  3.    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
  4.    if (key == null)  
  5.        return putForNullKey(value);  
  6.    // 根据key的keyCode重新计算hash值。  
  7.    int hash = hash(key.hashCode());  
  8.    // 搜索指定hash值在对应table中的索引。  
  9.    int i = indexFor(hash, table.length);  
  10.    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
  11.    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  12.        Object k;  
  13.       // 如果发现 i 索引处的链表的某个Entry的hash和新Entry的hash相等且两者的key相同,则新Entry覆盖旧Entry,返回。  
  14.        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  15.            V oldValue = e.value;  
  16.            e.value = value;  
  17.            e.recordAccess(this);  
  18.            return oldValue;  
  19.        }  
  20.    }  
  21.    // 如果i索引处的Entry为null,表明此处还没有Entry。  
  22.    modCount++;  
  23.    // 将key、value添加到i索引处。  
  24.    addEntry(hash, key, value, i);  
  25.    return null;  

 

 2) 读取元素:

有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

HashMap的部分源码如下:

Java代码  深入解析hashcode,hashMap源码
  1. public V get(Object key) {  
  2.     if (key == null)  
  3.         return getForNullKey();  
  4.     int hash = hash(key.hashCode());  
  5.     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
  6.         e != null;  
  7.         e = e.next) {  
  8.         Object k;  
  9.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
  10.             return e.value;  
  11.     }  
  12.     return null;  
  13. }   

  
   3) 归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。   

四、关于“相等的对象必须具有相等的哈希码”

  由于作为key的对象将通过计算其散列函数hashCode()来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
  如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。

同时复写equals方法和hashCode方法,必须保证“相等的对象必须具有相等的哈希码”,也就是当两个对象通过equals()比较的结果为true时,这两个对象调用hashCode()方法生成的哈希码必须相等。 

如何保证相等,可以参考下面的方法:

    复写equals方法和hashCode方法时,equals方法的判断根据和计算hashCode的依据相同。如String的equals方法是比较字符串每个字符,String的hashCode也是通过对该字符串每个字符的ASC码简单的算术运算所得,这样就可以保证相同的字符串的hashCode相同且equals()为真。 

String类的equals方法的源代码:

Java代码  深入解析hashcode,hashMap源码
  1.    /** 
  2.     * Compares this string to the specified object.  The result is {@code 
  3.     * true} if and only if the argument is not {@code null} and is a {@code 
  4.     * String} object that represents the same sequence of characters as this 
  5.     * object. 
  6.     * 
  7.     * @param  anObject 
  8.     *         The object to compare this {@code String} against 
  9.     * 
  10.     * @return  {@code true} if the given object represents a {@code String} 
  11.     *          equivalent to this string, {@code false} otherwise 
  12.     * 
  13.     * @see  #compareTo(String) 
  14.     * @see  #equalsIgnoreCase(String) 
  15.     */  
  16.    public boolean equals(Object anObject) {  
  17. if (this == anObject) {  
  18.     return true;  
  19. }  
  20. if (anObject instanceof String) {  
  21.     String anotherString = (String)anObject;  
  22.     int n = count;  
  23.     if (n == anotherString.count) {  
  24.     char v1[] = value;  
  25.     char v2[] = anotherString.value;  
  26.     int i = offset;  
  27.     int j = anotherString.offset;  
  28.     while (n-- != 0) {  
  29.         if (v1[i++] != v2[j++])  
  30.         return false;  
  31.     }  
  32.     return true;  
  33.     }  
  34. }  
  35. return false;  
  36.    }  

 

String类的hashCode方法计算hashCode的源代码:

Java代码  深入解析hashcode,hashMap源码
  1.    /** 
  2.     * Returns a hash code for this string. The hash code for a 
  3.     * <code>String</code> object is computed as 
  4.     * <blockquote><pre> 
  5.     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
  6.     * </pre></blockquote> 
  7.     * using <code>int</code> arithmetic, where <code>s[i]</code> is the 
  8.     * <i>i</i>th character of the string, <code>n</code> is the length of 
  9.     * the string, and <code>^</code> indicates exponentiation. 
  10.     * (The hash value of the empty string is zero.) 
  11.     * 
  12.     * @return  a hash code value for this object. 
  13.     */  
  14.    public int hashCode() {  
  15. int h = hash;  
  16.        int len = count;  
  17. if (h == 0 && len > 0) {  
  18.     int off = offset;  
  19.     char val[] = value;  
  20.   
  21.            for (int i = 0; i < len; i++) {  
  22.                h = 31*h + val[off++];  
  23.            }  
  24.            hash = h;  
  25.        }  
  26.        return h;  
  27.    }