Java--几种位运算及常见进制说明(解读HashMap源码必备知识)

吾日三省贾斯汀 发表于 2021/09/27 18:49:55 2021/09/27
【摘要】 您好,我是贾斯汀,欢迎又进来学习啦!【学习背景】学习Java的小伙伴,都知道想要提升个人技术水平,阅读JDK源码少不了,但是说实话还是有些难度的,底层源码实现的原理离不开各种常用的数据结构和算法,很多时候还会用到各种位运算,比如面试必问和工作写烂透了的HashMap,就一个put(key,value)添加元素的底层实现,就用到了各种位运算知识,不对位运算略知一二,你还真读不懂它的源码,所以本...
您好,我是贾斯汀,欢迎又进来学习啦!

在这里插入图片描述

【学习背景】

学习Java的小伙伴,都知道想要提升个人技术水平,阅读JDK源码少不了,但是说实话还是有些难度的,底层源码实现的原理离不开各种常用的数据结构和算法,很多时候还会用到各种位运算,比如面试必问和工作写烂透了的HashMap,就一个put(key,value)添加元素的底层实现,就用到了各种位运算知识,不对位运算略知一二,你还真读不懂它的源码,所以本文主要对Java中的几种位运算以及常见进制的说明,还会以HashMap底层实现添加元素四部曲展开说明,希望能提高提升自己对源码的理解,也希望能帮助到有需要的小伙伴~

进入正文~


@TOC

常见几种进制?

在这里插入图片描述

  • 二进制(Binary)
    数值范围0,1,满2进1
    以0b或0B开头
    bit比特是计算机最小存储单元,1个bit占用1个二进制位即0或1
    1个byte字节有8个bit即占用8个二进制位
    int整型4字节占用32个二进制位
    二进制左半部分表示高位,右半部分为低位
    二进制最高位为0表示正数,最高位为1表示负数
    二进制原码取反得到反码,反码补1得到补码,负数使用补码表示
  • 八进制(Octal)
    数值范围0-7,满8进1
    以数字0开头表示
  • 十进制(Decimal)
    数值范围0-9 ,满10进1
    日常阿拉伯数字即十进制
  • 十六进制(Hexadecimal)
    数值范围0-9及A-F,满16进1
    以0x或0X开头表示。 此处的A-F不区分大小写

Java八种按位运算?

在这里插入图片描述

  • 按位与(&)
    都为1则得1
  • 按位或(|)
    有一个为1即得1
  • 按位异或(^)
    不同得1,相同得0
  • 按位取反(~)
    取反即1变0、0变1
  • 按位左移(<<)
    按位左移几位,高位会被截掉几位,正负数,低位都会被补几个0
  • 按位右移(>>)
    按位右移几位,低位就会被截掉几位,正数高位会被补几个0,负数高位会被补几个1
  • 按位无符号右移(>>>)
    按位右移几位,低位就会被截掉几位,正负数数高位会被补几个0
  • 按位无符号左移(<<<)
    按位左移几位,高位就会被截掉几位,正负数数低位都会被补几个0

HashMap添加元素四步曲用到的位运算?

前奏:HashMap如何添加一个元素?

HashMap底层数据结构是数组+链表,通过put(K key, V value)方法添加元素,底层四步曲如下:

  • 第一步曲:根据key得到hashCode值
  • 第二步曲:根据hashCode值计算出hash值
  • 第三步曲:根据hash值计算出元素(key/value)最终要放在哪个数组index下标
  • 第二步曲:最后根据元素(key/value)新建节点并保存到指定数组index下标位置

Java HashMap添加元素的示例代码:

        HashMap<Object, Object> map = new HashMap<>();
        map.put("name","Justin");

HashMap底层put(key,value)方法源码:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

接下来将解读底层源码用到哪些位运算,有什么奥妙之处

第一步曲

根据key得到hashCode值
可以看到hash值计算的过程就用到了^(异或)和>>>(无符号右移)两种位运算

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这里key是字符串"name",String重写了计算字符串hashCode值的hashCode()方法,源码如下:
在这里插入图片描述
计算得到hashCode值为3373707

第二步曲

根据hashCode值计算出hash值
(h = key.hashCode()) ^ (h >>> 16)(3373707) ^ (3373707 >>> 16)
3373707二进制表达
0000000001100110111101010001011
h >>> 16二进制表达
00000000000000000000000000110011
根据^异或运算原理即不同得1,相同得0得到3373707 ^ (3373707 >>>16)二进制结果为:
0000000001100110111101010111000
进制在线转换:https://c.runoob.com/front-end/58/
在这里插入图片描述
即计算key的hash值得到3373752,断点往后查看hash值刚好也是这个值

第三步曲

根据hash值计算出元素(key/value)最终要放在哪个数组index下标
公式:i = (n - 1) & hash
这里就用到了&按位与运算(都为1则得1)
在这里插入图片描述
公式(n - 1) & hash 的奥妙之处在于,n表示HashMap中的数组容量大小,并且刚好是16,32,64…2的次方,这种情况其实是等效于 hash % n 取模,计算出的数组index下标值一样,还能够保证不会数组下标越界

但是HashMap这里没有使用%取模,因为hash值是int整型即十进制数值,使用%取模会先将内存数据转成十进制再进行运算,多了这部分的性能开销,因此效率比较低

HashTable底层倒是用的%取模,hash值与十六进制0x7FFFFFFF做按位与运算目的是为了保证hash值始终是正数
在这里插入图片描述
有的小伙伴可能会问了,使用%取模计算,那这里为啥HashTable还在用,我想说的是其实也可以优化,只不过HashTable本身就是主打synchronized线程安全,也就不考虑优化%取模为位运算了
在这里插入图片描述

第四步曲

最后根据元素(key/value)新建节点并保存到指定数组index下标位置

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

终曲:为什么HashMap底层源码用这么多位运算?

关于位运算的使用,文中在介绍第三步曲时,也提到了HashMap计算数组下标使用%取模和位运算的问题,使用于位运算的奥妙之处在直接从内存读取数据进行计算,不需要转成十进制,如果使用%取模需要先转成十进制,有性能开销,效率比较低

HashMap底层除了文中提到的^按位异或、>>>无符号右移、&按位与位运算,其实在HashMap的扩容机制resize()中,还用到了<<左移运算
oldCap << 1
在这里插入图片描述
这里oldCap << 1刚好是两倍,可以总结的说一个数与n进行左移运算,结果为这个数乘以2的n次方
oldCap << 1 等值 oldCap = oldCap * (2的n次方)
同理,一个数与n进行右移运算结果为这个数除以2的n次方
oldCap >> 1 等值 oldCap = oldCap / (2的n次方)

**

❤️‍我是贾斯汀,今天的学习暂时到这里,有疑问的小伙伴可以留言或私信我!❤️‍
❤️‍原创不易,觉得有用的小伙伴(点赞+收藏)支持一下哇!❤️‍

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。