Java必備知識之位運算及常見進制解讀

Posted on by

您好，我是賈斯汀，歡迎又進來學習啦！

在這裡插入圖片描述

【學習背景】

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

進入正文~

常見幾種進制？

在這裡插入圖片描述

  • 二進制（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
進制在線轉換：http://tools.jb51.net/transcoding/hexconvert

在這裡插入圖片描述

即計算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次方)

**

到此這篇關於Java必備知識之位運算及常見進制解讀的文章就介紹到這瞭,更多相關Java 位運算內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：