0.4、HashMap——从hashCode() 到哈希表

墨蓝 2021-12-21 14:51 190阅读 0赞

### 文章目录 ###

*   *   *   *  前言
             *  本文代码基于 JDK1.8
             *  JDK 中的 hashCode()
             *   *  hashCode() 基本约定
                 *  hashCode() 的覆盖重写
             *  hashCode() 不可用于比较两个对象是否相等
             *  HashMap 对哈希表的实现基于链表法
             *   *  哈希表
                 *  HashMap 链表法实现 哈希表
                 *   *  hashCode() 用于数组中的定位
                     *  HashMap 对 hashCode()进行了封装
             *  重写 equals() 方法时一定要重写 hashCode()
             *   *  Object.hashCode()
                 *  Object.equals(Object obj)
                 *  == 和 equals 的关系和区别
                 *  equals 重写一定要同时重写 hashCode()方法
             *  HashMap添加新元素:hashCode()只是一个开始
             *  小饼干:一个 不同对象 相同hashCode 的例子
             *  参考链接

#### 前言 ####

> 体能状态先于精神状态，习惯先于决心，聚焦先于喜好.

#### 本文代码基于 JDK1.8 ####

> 没有特殊声明,本文所展示的源码基于 JDK1.8

#### JDK 中的 hashCode() ####

> 在 java.lang.Object.hashCode(); 方法的注释中我们可以了解到 hashCode()方法是Object 类中到一个基本方法,而且其是一个 native 方法.  
> 返回一个 int 类型到值.

public native int hashCode();

##### hashCode() 基本约定 #####

> java.lang.Object.hashCode() 注释的总结如下:

1.  hashCode()方法返回一个int类型
2.  对于同一个应用中的同一个对象,hashCode()多次调用的返回值总是一样的
3.  对于同一个应用中的两个对象,如果 equals()结果相等,hashCode()结果必须相等
4.  对于不同应用中的两个对象,hashCode()结果可以相同也可以不相等,但是出于性能考虑,hashCode()应该尽可能不同,但是注意不能违背第3点

##### hashCode() 的覆盖重写 #####

> 基于对 hashCode() 基本约定的遵守,由于是为了更好的满足第4点,JDK 中很多的基础类都对 hashCode() 方法进行了从写  
> 比如下面列举 java.lang.String 中对 hashCode() 方法的重写

/** * 可以看到 String 类型的 hashCode 是基于String 内容 //hash默认的 "字符串".toCharArray(); */
    public int hashCode() { 
    	  //hash默认为0
          int h = hash;
          if (h == 0 && value.length > 0) { 
          //value="字符串".toCharArray();
              char val[] = value;
    
              for (int i = 0; i < value.length; i++) { 
                  h = 31 * h + val[i];
              }
              hash = h;
          }
          return h;
      }

#### hashCode() 不可用于比较两个对象是否相等 ####

> 上面已经说了,对于两个不同的对象,其hashCode()可能相等,也可能不相等,所以不可以通过 hashCode()来判断两个对象是否相等,不要从语义上这样用

#### HashMap 对哈希表的实现基于链表法 ####

##### 哈希表 #####

> 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。  
> HashMap 是对哈希表对一种实现  
> hashCode() 是hashMap 中的初步的散列函数-HashMap对这个函数进行了进一步的封装，用于确定元素在哈希表中的定位。

##### HashMap 链表法实现 哈希表 #####

> HashMap 对哈希表的实现基于链表法,在JDK1.8后,链表在满足一定条件后会被转化为 红黑树  
> HashMap 对象是由**数组**加**链表**组成的,那么一个键值对放到这个 HashMap 对象的数组中,还是链表中呢?  
> 这里就体现 hashCode() 的作用了,HashMap 使用与运算定位到了这个键值对在数组中的位置

###### hashCode() 用于数组中的定位 ######

> final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
> boolean evict) \{ 方法中的代码片段

//n为数组长度
    //hash 为 hash 值
    tab[i = (n - 1) & hash]

###### HashMap 对 hashCode()进行了封装 ######

/** * 本方法为向 HashMap 对象新增键值对 * hash(key)用于计算 key对应对hash值 */
    public V put(K key, V value) { 
          return putVal(hash(key), key, value, false, true);
       }
    
    /** * key.hashCode() 调用的是对象自己的 hashCode()方法 * 本方法进行二次封装 */
    static final int hash(Object key) { 
          int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }

#### 重写 equals() 方法时一定要重写 hashCode() ####

> 根据上面提到的 hashCode()的基本规定,如果对 equals()方法进行了从写,而没有对 hashCode()方法进行重新,可能会造成 equals()方法判断两个对象相等,而两个对象得到对hashCode()值不相等,hashCode()用于哈希表的初次定位  
> 一般来说,我们自己写的类都默认继承了 Object ,下面展示一下 Object 类中 hashCode() 的代码逻辑和equals()方法的代码逻辑

##### Object.hashCode() #####

public native int hashCode();

##### Object.equals(Object obj) #####

> 可以看到,内部使用的是 == 判断,即只有两个对象内存地址相同时,才会判断相等

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

##### == 和 equals 的关系和区别 #####

> 在Object.equals(Object obj) 的方法中已经可以看到,Object的equals方法内部使用了 == 来判断两个对象是否相等  
> 这种情况下,只有两个对象在内存中的地址一样时,才会返回true  
> 如果你自己覆盖从写 equals 方法,可能会按照内容,而不是对象地址,所以相当于 equals 方法给了我们自主判断两个对象是否相等的能力  
> 比如我们看下 String 类 equals 的代码:地址相同或者两个字符串对象的每一位相同,都可以认为 equals 相同

public boolean equals(Object anObject) { 
     	//如果内存地址相同,返回true
         if (this == anObject) { 
             return true;
         }
         //必须是 String 类型
         if (anObject instanceof String) { 
             String anotherString = (String)anObject;
             int n = value.length;
             if (n == anotherString.value.length) { 
                 char v1[] = value;
                 char v2[] = anotherString.value;
                 int i = 0;
                 //如果字符串的每一位都相同,则为true
                 while (n-- != 0) { 
                     if (v1[i] != v2[i])
                         return false;
                     i++;
                 }
                 return true;
             }
         }
         return false;
     }

##### equals 重写一定要同时重写 hashCode()方法 #####

> 重写 equals 方法是为了按照程序员自己的逻辑判断两个对象是否相等,而不是别的目的  
> 两个相等的对象就是一个对象,在向HashMap中添加的时候,这两个对象作为key相当于同一个key,或者说,它们只应被添加一次  
> 如果没有重写 hashCode() ,就有可能,两个对象 hashCode() 结果不同,从而导致被分配到HashMap 的数组的不同位置中-一个一摸一样的key被添加到HashMap 两次,这就是写出bug了

#### HashMap添加新元素:hashCode()只是一个开始 ####

> HashMap 实现的哈希表是数组加链表  
> 但是两个不同对象得到相同的 hashCode()值,所以当两个对象定位到数组的同一个位置时,第一个会被保存到数组,第二个会被保存到数组该位置的链表上,即数组中节点的next指向一个新节点,用以保存第二个对象

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70]

#### 小饼干:一个 不同对象 相同hashCode 的例子 ####

> “Aa”.hashCode() 和 “BB”.hashCode() 的值都是 2112

/** * 一个 不同对象 相同hashCode 的例子 * 可以用于 debug 跟踪代码时使用 * */
    @Test
    public void testHashCode() { 
    	System.out.println("Aa".hashCode());//2112
    	System.out.println("BB".hashCode());//2112
    }

#### 参考链接 ####

> \[1\]、[https://blog.csdn.net/zj15527620802/article/details/88547914][https_blog.csdn.net_zj15527620802_article_details_88547914]  
> \[2\]、[https://blog.csdn.net/wangxing233/article/details/79452946][https_blog.csdn.net_wangxing233_article_details_79452946]  
> \[3\]、[https://www.cnblogs.com/xinzhao/p/5644175.html][https_www.cnblogs.com_xinzhao_p_5644175.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70]: /images/20211220/448020546a454151a16450f5174700fb.png
[https_blog.csdn.net_zj15527620802_article_details_88547914]: https://blog.csdn.net/zj15527620802/article/details/88547914
[https_blog.csdn.net_wangxing233_article_details_79452946]: https://blog.csdn.net/wangxing233/article/details/79452946
[https_www.cnblogs.com_xinzhao_p_5644175.html]: https://www.cnblogs.com/xinzhao/p/5644175.html