快捷導(dǎo)航

Java必備知識之位運(yùn)算及常見進(jìn)制解讀

更新時間：2021年10月09日 17:02:53 作者：吾日三省賈斯汀

從現(xiàn)代計(jì)算機(jī)中所有的數(shù)據(jù)二進(jìn)制的形式存儲在設(shè)備中。即 0、1 兩種狀態(tài)，計(jì)算機(jī)對二進(jìn)制數(shù)據(jù)進(jìn)行的運(yùn)算(+、-、*、/)都是叫位運(yùn)算，即將符號位共同參與運(yùn)算的運(yùn)算

學(xué)習(xí)Java的小伙伴，都知道想要提升個人技術(shù)水平，閱讀JDK源碼少不了，但是說實(shí)話還是有些難度的，底層源碼實(shí)現(xiàn)的原理離不開各種常用的數(shù)據(jù)結(jié)構(gòu)和算法，很多時候還會用到各種位運(yùn)算，比如面試必問和工作寫爛透了的HashMap，就一個put(key,value)添加元素的底層實(shí)現(xiàn)，就用到了各種位運(yùn)算知識，不對位運(yùn)算略知一二，你還真讀不懂它的源碼，所以本文主要對Java中的幾種位運(yùn)算以及常見進(jìn)制的說明，還會以HashMap底層實(shí)現(xiàn)添加元素四部曲展開說明，希望能提高提升自己對源碼的理解，也希望能幫助到有需要的小伙伴~

進(jìn)入正文~

常見幾種進(jìn)制？

在這里插入圖片描述

二進(jìn)制（Binary）

數(shù)值范圍0,1，滿2進(jìn)1
以0b或0B開頭
bit比特是計(jì)算機(jī)最小存儲單元，1個bit占用1個二進(jìn)制位即0或1
1個byte字節(jié)有8個bit即占用8個二進(jìn)制位
int整型4字節(jié)占用32個二進(jìn)制位
二進(jìn)制左半部分表示高位，右半部分為低位
二進(jìn)制最高位為0表示正數(shù)，最高位為1表示負(fù)數(shù)
二進(jìn)制原碼取反得到反碼，反碼補(bǔ)1得到補(bǔ)碼，負(fù)數(shù)使用補(bǔ)碼表示

八進(jìn)制（Octal）

數(shù)值范圍0-7,滿8進(jìn)1
以數(shù)字0開頭表示

十進(jìn)制（Decimal）

數(shù)值范圍0-9 ，滿10進(jìn)1
日常阿拉伯?dāng)?shù)字即十進(jìn)制

十六進(jìn)制（Hexadecimal）

數(shù)值范圍0-9及A-F，滿16進(jìn)1
以0x或0X開頭表示。此處的A-F不區(qū)分大小寫

Java八種按位運(yùn)算？

在這里插入圖片描述

按位與（&）

都為1則得1

按位或（|）

有一個為1即得1

按位異或（^）

不同得1，相同得0

按位取反（~）

取反即1變0、0變1

按位左移（<<）

按位左移幾位，高位會被截掉幾位，正負(fù)數(shù)，低位都會被補(bǔ)幾個0

按位右移（>>）

按位右移幾位，低位就會被截掉幾位，正數(shù)高位會被補(bǔ)幾個0，負(fù)數(shù)高位會被補(bǔ)幾個1

按位無符號右移（>>>）

按位右移幾位，低位就會被截掉幾位，正負(fù)數(shù)數(shù)高位會被補(bǔ)幾個0

按位無符號左移（<<<）

按位左移幾位，高位就會被截掉幾位，正負(fù)數(shù)數(shù)低位都會被補(bǔ)幾個0

HashMap添加元素四步曲用到的位運(yùn)算？

前奏：HashMap如何添加一個元素？

HashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表，通過put(K key, V value)方法添加元素，底層四步曲如下：

第一步曲：根據(jù)key得到hashCode值
第二步曲：根據(jù)hashCode值計(jì)算出hash值
第三步曲：根據(jù)hash值計(jì)算出元素(key/value)最終要放在哪個數(shù)組index下標(biāo)
第四步曲：最后根據(jù)元素(key/value)新建節(jié)點(diǎn)并保存到指定數(shù)組index下標(biāo)位置

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);
    }

接下來將解讀底層源碼用到哪些位運(yùn)算，有什么奧妙之處

第一步曲

根據(jù)key得到hashCode值
可以看到hash值計(jì)算的過程就用到了^（異或）和>>>(無符號右移)兩種位運(yùn)算

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

這里key是字符串"name"，String重寫了計(jì)算字符串hashCode值的hashCode()方法，源碼如下：

在這里插入圖片描述

計(jì)算得到hashCode值為3373707

第二步曲

根據(jù)hashCode值計(jì)算出hash值
(h = key.hashCode()) ^ (h >>> 16) 即 (3373707) ^ (3373707 >>> 16)
3373707二進(jìn)制表達(dá)
0000000001100110111101010001011
h >>> 16二進(jìn)制表達(dá)
00000000000000000000000000110011
根據(jù)^異或運(yùn)算原理即不同得1，相同得0得到3373707 ^ (3373707 >>>16)二進(jìn)制結(jié)果為：
0000000001100110111101010111000
進(jìn)制在線轉(zhuǎn)換：http://tools.jb51.net/transcoding/hexconvert

在這里插入圖片描述

即計(jì)算key的hash值得到3373752，斷點(diǎn)往后查看hash值剛好也是這個值

第三步曲

根據(jù)hash值計(jì)算出元素(key/value)最終要放在哪個數(shù)組index下標(biāo)
公式：i = (n - 1) & hash
這里就用到了&按位與運(yùn)算（都為1則得1）

在這里插入圖片描述

公式(n - 1) & hash 的奧妙之處在于，n表示HashMap中的數(shù)組容量大小，并且剛好是16,32,64…2的次方，這種情況其實(shí)是等效于 hash % n 取模，計(jì)算出的數(shù)組index下標(biāo)值一樣，還能夠保證不會數(shù)組下標(biāo)越界

但是HashMap這里沒有使用%取模，因?yàn)閔ash值是int整型即十進(jìn)制數(shù)值，使用%取模會先將內(nèi)存數(shù)據(jù)轉(zhuǎn)成十進(jìn)制再進(jìn)行運(yùn)算，多了這部分的性能開銷，因此效率比較低

HashTable底層倒是用的%取模，hash值與十六進(jìn)制0x7FFFFFFF做按位與運(yùn)算目的是為了保證hash值始終是正數(shù)

在這里插入圖片描述

有的小伙伴可能會問了，使用%取模計(jì)算，那這里為啥HashTable還在用，我想說的是其實(shí)也可以優(yōu)化，只不過HashTable本身就是主打synchronized線程安全，也就不考慮優(yōu)化%取模為位運(yùn)算了

在這里插入圖片描述

第四步曲

最后根據(jù)元素(key/value)新建節(jié)點(diǎn)并保存到指定數(shù)組index下標(biāo)位置

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

終曲：為什么HashMap底層源碼用這么多位運(yùn)算？

關(guān)于位運(yùn)算的使用，文中在介紹第三步曲時，也提到了HashMap計(jì)算數(shù)組下標(biāo)使用%取模和位運(yùn)算的問題，使用于位運(yùn)算的奧妙之處在直接從內(nèi)存讀取數(shù)據(jù)進(jìn)行計(jì)算，不需要轉(zhuǎn)成十進(jìn)制，如果使用%取模需要先轉(zhuǎn)成十進(jìn)制，有性能開銷，效率比較低

HashMap底層除了文中提到的^按位異或、>>>無符號右移、&按位與位運(yùn)算，其實(shí)在HashMap的擴(kuò)容機(jī)制resize()中，還用到了<<左移運(yùn)算
oldCap << 1

在這里插入圖片描述

這里oldCap << 1剛好是兩倍，可以總結(jié)的說一個數(shù)與n進(jìn)行左移運(yùn)算，結(jié)果為這個數(shù)乘以2的n次方
oldCap << 1 等值 oldCap = oldCap * (2的n次方)
同理，一個數(shù)與n進(jìn)行右移運(yùn)算結(jié)果為這個數(shù)除以2的n次方
oldCap >> 1 等值 oldCap = oldCap / (2的n次方)

**

到此這篇關(guān)于Java必備知識之位運(yùn)算及常見進(jìn)制解讀的文章就介紹到這了,更多相關(guān)Java 位運(yùn)算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: