网站扁平化设计风格,首码项目推广网站,做网站优势,获客软件首先#xff0c;hash方法用来干什么#xff1f;
在搞清楚原理之前#xff0c;我们先站在巨人的肩膀浅浅了解一下hash方法的本质作用。
实质上#xff0c;它的作用很朴素#xff0c;就是用key值通过某种方式计算出一个hash码
而且这个hash码我们后面要用来计算key存在底…首先hash方法用来干什么
在搞清楚原理之前我们先站在巨人的肩膀浅浅了解一下hash方法的本质作用。
实质上它的作用很朴素就是用key值通过某种方式计算出一个hash码
而且这个hash码我们后面要用来计算key存在底层数组的下标所以它必须保持一定的随机性让计算出的数组元素下标更加均衡分布减少碰撞其实就是更大程度上的避免hash冲突。
注保持随机性这一性质只有在hash方法计算hash值这一步会有所体现后面的取模运算只是单独的为了取到余数与保证随机性没有关系 Hash方法是什么
这里先直观的给出它的源码 参数 key 需要计算哈希码的键值。 key null ? 0 : (h key.hashCode()) ^ (h 16) 这是一个三目运算符看似复杂其实很好理解。 逻辑就是如果键值为null则哈希码为 0 依旧是说如果键为 null 则存放在第一个位置否则通过调用 hashCode() 方 法获取键的哈希码并将其与右移16 位的哈希码进行异或运算。 ^ 运算符异或运算符是 Java 中的一种位运算符它用于将两个数的二进制位进行比较如果相同则为 0不同则为 1 。 16 将哈希码向右移动 16 位相当于将原来的哈希码分成了两个 16 位的部分。最终返回的是经过异或运算后得到的哈希码值。 这短短的一行代码汇聚不少计算机巨佬们的聪明才智。 理论上哈希值即hashcode方法返回的值是一个 int 类型大家都知道int型在java中占4个字节即32位范围从 -2147483648 到 2147483648 。前后加起来大概 40 亿的映射空间只要哈希值映射得比较均匀松散一般是不会出现哈希碰撞哈希冲突会降低 HashMap 的效率。 但问题是一个 40 亿长度的数组内存是放不下的。 HashMap 扩容之前的数组初始大小只有 16 所以这个哈希值是不能直接拿来用的用之前要和数组的长度做取模运算前文提到的 (n - 1) hash 用得到的余数来访问数组下标才行。 对h ^ h16如何理解
上面的h其实就是我们调用key的hashcode()方法得到的hashcode值我们将它右移16位因为是int型所以总共是32位前面16位补0然后我们让它与原本的hashcode值进行异或因为异或的逻辑是不同为1相当于就是前16位与后16位进行会进行一次异或占据最终返回的hash的后16位然后前16位与进行补位的16个0进行异或占据最终返回的hash的前16位得到最终return的hash码。
上面的流程可以参考下面的图进行思考 这样大家可能会比较疑惑这么翻来覆去是为了啥呀其实都是为了一个hash码的随机性目的还是为了避免hash冲突毕竟hash冲突会降低HashMap的效率。 综上所述 hash 方法是用来做哈希值优化的 把哈希值右移 16 位也就正好是自己长度的一半之后与原哈希值做异或运算这样就混合了原哈希值中的高位和低位增大了随机性。 计算好了hash值然后我们怎么使用hash值计算下标
我们使用n - 1 hash的方式获取下标其实就是取模运算 大家可能会比较好奇要进行取模运算难道不该用% 吗为什么要用位运算 呢
这是因为%虽然确实可以实现但是实际效率却还是不如
并且我们的能够取代%是要有一个前提条件的
只有当 b 为 2 的 n 次方时才存在这样一个公式a % b a (b-1) 我们可以对其进行一个验证 我们来验证一下假如 a 14 b 8 也就是 2^3 n3 。 14%8 余数为 6 14 的二进制为 1110 8 的二进制 1000 8-1 7 7 的二进制为 0111 111001110110 也就是 0 * 2^01 * 2^11 * 2^20 * 2 ^302406 14%8 刚好也等于 6 。 害计算机就是这么讲道理没办法 也就是说只有数组长度是2的n次方时使用才会取余成功这也是为什么我们对hashmap进行扩容时必须是2倍扩容了 为什么会这么巧刚好二者就相同了呢这与一个低位掩码的概念有关这里我们先不细讲。 顺着上一个问题的图我们再看这个步骤进行理解 知道了hash方法的原理以及并将其计算出来我们还需要知道 hash方法在哪里被用到
1.首先当然是我们最经典的put方法 后面的putval会通过hash值来计算下标 2.其次是我们使用get方法获取元素时会调用getNode方法其中用到hash值 小结 hash 方法的主要作用是将 key 的 hashCode 值进行处理得到最终的哈希值。由于 key 的hashCode 值是 不确定的可能会出现哈希冲突因此需要将哈希值通过一定的算法映射到HashMap 的实际存储位置上。 hash 方法的原理是先获取 key 对象的 hashCode 值然后将其高位与低位进行异或操作得到一个新的哈希值。为什么要进行异或操作呢因为对于 hashCode 的高位和低位它们的分布是比较均匀的如果只是简单地将它们加起来或者进行位运算容易出现哈希冲突而异或操作可以避免这个问题。然后将新的哈希值取模mod得到一个实际的存储位置。这个取模操作的目的是将哈希值映射到桶Bucket的索引上桶是 HashMap 中的一个数组每个桶中会存储着一个链表或者红黑树装载哈希值相同的键值对没有相同哈希值的话就只存储一个键值对。 总的来说HashMap 的 hash 方法就是将 key 对象的 hashCode 值进行处理得到最终的哈希值并通过一定的算法映射到实际的存储位置上。这个过程决定了 HashMap 内部键值对的查找效率。
