第一次有人把HashMap的hash快速生成方法这么详细~

我就是我 2021-07-24 20:56 749阅读 0赞

> 第一次有人把HashMap的hash快速生成方法这么详细~

明人不说暗话~直接开干  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70][]

解析hash的源码

static final int hash(Object key) { 
        int h;
        return key==null? 0: (h=key.hashCode())^h>>>16;
        // key.hashCode()是对象的hashcode，任何对象类都有自定义的hashcode
        // ^h 异或操作：两个位相同为0，相异为1；>>> 无符号右移：忽略符号位，空位都以0补齐
        // 注意>>> 优先级高于^，所以写成(h=key.hashCode())^(h>>>16)更容易理解
    }

以下图为例，展示对一个32位的int整型做hash计算过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1][]  
源码中对hashcode的再处理称之为“扰动函数”。

无符号右移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大随机性。

## 为什么使用扰动函数 ##

[【参考】][Link 1]：写在前面：我没在源码里找到indexFor。

理论上散列值是一个int型，如果直接拿散列值作为下标访问hashmap主数组的话，考虑2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但是一个40亿长度的数组，内存是放不下的。所以源码中用indexFor函数将哈希码对数组的长度取模运算，得到的余数才能用来访问数组下标。

bucketIndex = indexFor(hash, table.length);
    static int indexFor(int h, int length) { 
        return h&(length-1);
    }

indexFor以下为例说明：

bucketIndex = indexFor(hash, table.length);

到这里问题就是，就算散列值分步再松散，要是只取最后几位，碰撞也很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，会恰好使最后几个低位呈现规律性重复。[【参考文献】][Link 1]

所以就引入了“扰动函数”来加大哈希码的随机性。

## Java运算符优先级 ##

<table> 
 <thead> 
  <tr> 
   <th><strong>优先级</strong></th> 
   <th><strong>运算符</strong></th> 
   <th><strong>结合性</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>() [] .</td> 
   <td>从左到右</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>! +(正) -(负) ~ ++ –</td> 
   <td><a href="https://jq.qq.com/?_wv=1027&amp;k=0IsBuUb0" rel="nofollow">从右向左</a></td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>* / %</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>+(加) -(减)</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>&lt;&lt; &gt;&gt; &gt;&gt;&gt;</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>&lt; &lt;= &gt; &gt;= instanceof</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>== !=</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>&amp;(按位与)</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>^</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td><code>|</code></td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>&amp;&amp;</td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td><code>||</code></td> 
   <td>从左向右</td> 
  </tr> 
  <tr> 
   <td>13</td> 
   <td>?:</td> 
   <td><a href="https://jq.qq.com/?_wv=1027&amp;k=0IsBuUb0" rel="nofollow">从右向左</a></td> 
  </tr> 
  <tr> 
   <td>14</td> 
   <td><code>= += -= *= /= %= &amp;= |= ^= ~= &lt;&lt;= &gt;&gt;= &gt;&gt;&gt;=</code></td> 
   <td><a href="https://jq.qq.com/?_wv=1027&amp;k=0IsBuUb0" rel="nofollow">从右向左</a></td> 
  </tr> 
 </tbody> 
</table>

[**最新2021整理收集的一些高频面试题（都整理成文档），有很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，也有详细的学习规划图，面试题整理等，需要获取这些内容的朋友请加Q君样：756584822**][Link 1]  
[  
![20210528220121448.gif_pic_center][]][Link 1]

[![在这里插入图片描述][11b455b97e85493a7dcb5eda11c96681.gif_pic_center]][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]: /images/20210724/9df75e96c41f418497893610e54b7a15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1]: /images/20210724/263de63afdb64555a7a882dfed2a98aa.png
[Link 1]: /images/20210724/38c137dbfefa48aa80ad3beeb85323a2.png
[20210528220121448.gif_pic_center]: /images/20210724/a29e6780a67441f08083f056bf8fa552.png
[11b455b97e85493a7dcb5eda11c96681.gif_pic_center]: https://img-blog.csdnimg.cn/img_convert/11b455b97e85493a7dcb5eda11c96681.gif#pic_center