一、取模运算和取余运算
- 取余运算，这个很好理解，我们经过多年的数学学习也知道，就是求余数，一个整数和另一个整数相除，得到它们的余数，就是我们说的取余
- 取模运算，通俗的来讲大多运算在计算机领域，取模运算其实就是两个二进制数字之间做与运算，它们最后得到的数字就是取模
- 我们举个简单的例子，有一个二进制数字0000 0001 1001 1101，1111 0101 1010 0011，这个两个数字做与运算，它们相同位置的数字，如果有一个数字出现1，那么计算后的数字的那个位置就是1，这两个数字与运算后的值为1111 0101 1011 1111这就是取模运算
二、hash函数在HashMap的源码
    <span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hash</span><span class="hljs-params">(Object key)</span> </span>{<br>        <span class="hljs-keyword">int</span> h;<br>        <span class="hljs-keyword">return</span> (key == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : (h = key.hashCode()) ^ (h >>> <span class="hljs-number">16</span>);<br>    }
- 我们乍一看这个东西很懵，到底有什么用，讲这个源码之前，我们得先知道hashCode()函数是干嘛的？我们先看源码
    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">native</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hashCode</span><span class="hljs-params">()</span></span>;
- 这个就是hashCode函数的实现，从native关键字可以看出这是一个由底层C代码实现的函数，因此我们不必知道它是怎么实现，我们只需要知道，它就是返回一个int类型的数字，这个数字就相当于对象的身份证，指纹，因此可以利用这个”身份证”来进行归类，我们知道int值域在-2147483648 到 2147483648，这个范围有40多亿，因此想要相同也不容易，但是我们的HashMap底层数据结构是一个数组啊，用于存储这些节点，初始大小为16，因此按照我们常规做法就是，用这个”身份证”和数组大小（也就是16）做取余运算，这样我们就是把一个很大的数字映射成一个16以内的整数。然后我们就可以把这个节点存储到这个数组的某一个位置了。
三、hashMap中映射的解决方案
- 这个解决方案其实很好，但是我们还没有其他的解决方案呢？
- 其实是有的，在hashmap中的做映射，使用是取模运算而不是取余运算，这是为啥？
- 因为取余运算的效率远高于取余运算，我们知道任何数据存储在计算机内部都是以二进制形式存储的，因为两个int整数进行取模运算的时候，做几次比较立即就得出了，但是取余就要运算很长
- hashMap内部使用取模，比如我们一个对象的”身份证”是
- 1010 0111 0100 1010 1111 1001 0010 1010
- 我们数组大小是16，16的二进制是0000 0000 0000 0000 0000 0000 0001 0000
- 我们减一，那就是 0000 0000 0000 0000 0000 0000 0000 1111，用这个数字和上面那个”身份证”取模得到0000 * 7个，最后四位就是1010，多好啊!把一个数字映射成了一个16以内的数字，我们看看源码是不是这个方法
    <span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent,<br>                   <span class="hljs-keyword">boolean</span> evict)</span> </span>{<br>        Node<k,v>[] tab; Node<k,v> p; <span class="hljs-keyword">int</span> n, i;<br>        <span class="hljs-keyword">if</span> ((tab = table) == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)<br>            n = (tab = resize()).length;<br>        <span class="hljs-keyword">if</span> ((p = tab[i = (n - <span class="hljs-number">1</span>) & hash]) == <span class="hljs-keyword">null</span>)<br>            tab[i] = newNode(hash, key, value, <span class="hljs-keyword">null</span>);<br><br></k,v></k,v>
- 可以看见正好n-1就是16-1=15这样2进制最后4位都是1，就是模取出来了
- 这也正好解释了为什么扩容都是*2了，因为-1之后就是后面几位数字都是1了，便于好取模，求出映射
- 回到我们刚才说的hash函数有什么用
- 我们看这里h&(h>>16),其实就是身份证和身份证往右移动16位之后取模，我们知道一个int值类型就是一个32位的二进制，这样其实就是把前16和后16位进行取模，这样就把一个增大了随机性，因为你看原来的方法只取了后面4位，前面的28位都没啥用，用这个方法之后，再取后4位就是把前面的16位也拿来了
- 总结 ：hash函数就是为了是对象的hash值增加随机性，它集合前16位和后16的特征进行计算，这样再被取模之后，会让对象在HashMap中分布更均匀。
四、源码：
- github路径：https://github.com/ruigege66/Java/blob/master/newJava/src/com/newJava/D151_HashMapAnalysis.java
- CSDN：https://blog.csdn.net/weixin_44630050
- 博客园：https://www.cnblogs.com/ruigege0000/
Original: https://www.cnblogs.com/ruigege0000/p/15700598.html
Author: 心悦君兮君不知-睿
Title: Java连载152-HashMap中的hash函数有什么用
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/607928/
转载文章受原作者版权保护。转载请注明原作者出处！