浙江龙网

  1. 首页 > 生活百科 > >

HashMap底层原理及jdk1.8源码解读( 二 )

生活百科

五、源码分析之常用方法解读1、tableSizeFor方法解读/** * 返回给定目标容量的 2 次方 。*/static final int tableSizeFor(int cap) { // cap = 10int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;// 小于0就是1，如果大于0在判断是不是超过最大容量就是n=15+1 = 16，超过就按最大容量return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}以cap为10为例：（右移规则为：无符号位右移）
10的二进制为：0000 0000 0000 0000 0000 0000 0000 1010
执行int n = cap - 1;
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1001
执行n |= n >>> 1;（先进行右移，结果和原来的数进行或运算[==有1则1==]）
0000 0000 0000 0000 0000 0000 0000 10010000 0000 0000 0000 0000 0000 0000 0100n>>1结果————————————————————0000 0000 0000 0000 0000 0000 0000 1101n |= n >> 1 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1101
执行n |= n >>> 2;
0000 0000 0000 0000 0000 0000 0000 1101
0000 0000 0000 0000 0000 0000 0000 0011n>>2结果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 2 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行n |= n >>> 4;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>4结果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 4 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行n |= n >>> 8;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>8结果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 8 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行n |= n >>> 16;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>16结果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 16 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
我们会发现，当数小的的时候进行到4时就不会变了我们得到的值为15 ， 即输入10 ， 经过此方法后得到15 。遇到大的数才会明显，大家可以找个大的数字进行试试就是先右移在进行或运算 。最后进行三门运算进行+1操作，最后结果为16=2^4
2、hash方法解读static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}先判断key是否为空 ， 若为空则返回0 。上面说了HashMap仅支持一个key为null的 。若非空 ， 则先计算key的hashCode值 ， 赋值给h ， 然后把h右移16位，并与原来的h进行异或处理（相同为1，不同为0） 。注释进行谷歌翻译：计算 key.hashCode() 并传播（XOR）更高位的哈希降低 。由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突 。（已知的例子是在小表中保存连续整数的 Float 键集 。）因此，我们应用了一种变换，将高位的影响向下传播 。在位扩展的速度、实用性和质量之间存在折衷 。因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最简单的方式对一些移位的位进行异或，以减少系统损失， 以及合并最高位的影响 ， 否则由于表边界，这些最高位将永远不会用于索引计算 。
总结：使用最简易的方式，及减少系统损失又减少了hash碰撞 。
3、put方法解读

HashMap底层原理及jdk1.8源码解读

文章插图
/*** 将指定的值与此映射中的指定键相关联 。即当前key应该存放在数组的哪个下标位置* 如果映射先前包含键的映射，则替换旧的值 。*/public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** 这才是真正的保存方法* @param hash经过hash运算后的key* @param key你要添加的key* @param value你要添加的value* @param onlyIfAbsent如果为真，则不要更改现有值，本次为FALSE，可以替换更改* @param evict如果为 false，则表处于创建模式 。我们为true*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 判断table是否为空if ((tab = table) == null || (n = tab.length) == 0)// 如果空的话 ， 会先调用resize扩容,resize我们后面展开讲解n = (tab = resize()).length;// 把通过hash得到的值与数组大小-1进行与运算，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快 。// 得到key所对应的数组的节点，然后把该数组节点赋值给p,然后判断这个位置是不是有元素if ((p = tab[i = (n - 1) & hash]) == null)// key、value包装成newNode节点，直接添加到此位置 。tab[i] = newNode(hash, key, value, null);// 如果当前数组下标位置已经有元素了，又分为三种情况 。else {Node<K,V> e; K k;// 当前位置元素的hash值等于传过来的hash，并且他们的key值也相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 则把p赋值给e，后续需要新值把旧值替换e = p;// 来到这里说明该节点的key与原来的key不同，则看该节点是红黑树 ， 还是链表else if (p instanceof TreeNode)// 如果是红黑树 ， 则通过红黑树的方式，把key-value存到红黑树中 。后面再讲解这个方法e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 来到这里说明结构为链表，把key-value使用尾插法插到链表尾 。// jdk1.7 链表是头插入法，在并发扩容时会造成死循环// jdk1.8 就把头插入法换成了尾插入法，虽然效率上有点稍微降低一些，但是不会出现死循环for (int binCount = 0; ; ++binCount) {// 遍历该链表，知道知道下一个节点为null 。if ((e = p.next) == null) {// 说明到链表尾部，然后把尾部的next指向新生成的对象p.next = newNode(hash, key, value, null);// 如果链表的长度大于等于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 则链表转化成为红黑树 后面再补充treeifyBin(tab, hash);break;}// 如果在链表中找到了相同key的话，直接退出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 说明发生了碰撞，e代表的是旧值，需要替换为新值if (e != null) { // existing mapping for keyV oldValue = https://www.huyubaike.com/biancheng/e.value;// 判断是不是允许覆盖旧值 ， 和旧值是否为空if (!onlyIfAbsent || oldValue == null)// 把旧值替换e.value = value;// hashmap没有任何实现 ， 我们先不考虑afterNodeAccess(e);// 返回新值return oldValue;}}// fail-fast机制每次对结构改变进行+1++modCount;// 判断HashMap中的存的数据大?。?如果大于数组长度*0.75 ， 就要进行扩容if (++size > threshold)resize();// 也是一个空的实现afterNodeInsertion(evict);return null;}

推荐阅读


上一篇：基于 Apache Hudi 极致查询优化的探索实践

下一篇：详解JS中 call 方法的实现