之前看HashMap源碼時棉钧，總說HashMap數(shù)組大小要用2的n次冪吉执，取模時用到的位運算，這樣HashMap取模才會很快牲尺，也就知道了這個特性卵酪，沒有去專門了解過，為什么用2的n次冪谤碳，可以用位運算來取模溃卡；由于最近看一些框架底層代碼，位運算遇到的多了蜒简，有點好奇塑煎，就研究了下；發(fā)現(xiàn)這個取模確實很有趣臭蚁；
一最铁、(n -1) & hash 取模算法
(n -1) & hash? 就是計算，該key是在數(shù)組中的哪個位置垮兑，下面我們研究下這個(n -1) & hash冷尉；
首先是hash這個值，轉(zhuǎn)成二進制系枪，就是0和1雀哨，我們先用個例子來說明下，n=4私爷，hash=11
11的二進制是1011
4的二進制是100
從上圖可以看出雾棺，因為如果用2的n次冪，當轉(zhuǎn)換成二進制后衬浑，高位肯定能整除低位（舉個例子：上面的是8捌浩，肯定能整除4，8的下一位是16工秩，肯定也能整除4尸饺，以此類推）进统，所以高位可以直接舍棄掉，只用看同樣位置后面的數(shù)浪听；后面的數(shù)就為3螟碎，但是這個3要怎么得到呢；這就是 (n - 1) 和 &的精髓了迹栓；
大家都知道绣檬，&1得到的是原來的值藕夫，高位沒有則不染庀帷猬膨；2進制數(shù)字， n-1則剛好得到的是2的n次冪小一位全是1的二進制數(shù)字答毫，所以上面的列子中，最后是計算
就剛好可以直接把余數(shù)取出來季春；
看到這里了之后洗搂，突然想起來，我們創(chuàng)建HashMap時载弄，可以指定HashMap的初始大小耘拇，那我們傳進去一個不是2的n次冪的數(shù)字，那上面的就計算不了了宇攻，然后就接著研究了下惫叛，這個初始化的算法，也是相當精髓逞刷；
二嘉涌、初始化數(shù)組大小
我們來看看JDK1.7的數(shù)組初始化，這個邏輯清晰一些夸浅；首先我們得明白這一部分邏輯肯定是為了把我們傳進來的數(shù)字仑最，給變成2的n次冪才能進行上面的取模算法；我們先看看?Integer.highestOneBit((number -1) <<1)? 這一部分帆喇；找到了highestOneBit這個方法的解釋警医，意思就是取傳進來的最高位，大概就是當傳進來為7的話坯钦，2進制為111预皇，最高位就是100，也就是4婉刀；得到的就是2的n次冪吟温；
我們先看看括號里面的是什么意思，(number -1) <<1 突颊，就是我們傳進來的數(shù)字減一溯街，然后向左移一位诱桂；開始我的理解是向左移一位就是乘以2，之后才發(fā)現(xiàn)呈昔，我們得放棄我們得數(shù)學思維挥等，不然就會想復雜了；這個向左移一位是為了取到一個大于我們傳進來的數(shù)字且剛好能滿足2的n次冪的數(shù)字堤尾，比如肝劲，我們傳進來是7，二進制就是111郭宝，那剛好大于111的2的n次冪辞槐，肯定是1000，也就是8粘室，所以榄檬，這個向左移一位，然后取最高位衔统，就剛好滿足條件鹿榜，那我們就看出這段邏輯的大概意思了；HashMap數(shù)組的長度锦爵，就是給到一個最適合的數(shù)字舱殿，并且盡量能滿足大部分的key能剛好落到數(shù)組上，不用進行鏈表的遍歷险掀，這樣取值是最快的沪袭；
看到這里，開始我一直沒明白這個?number -1 是什么意思樟氢，本來?number? << 1就可以滿足條件了冈绊，為啥還得減一，最開始的時候也懷疑過是埠啃，我們傳入的數(shù)組剛好是2的n次冪時焚碌，會有問題；其實只要一想到這個霸妹，就能明白這個意思十电，因為我們傳入8的時候，如果向左移一位的話叹螟，就是16了鹃骂，然后取最高位也是16，那就數(shù)組會比原來大一倍罢绽；但是我開始覺得畏线，如果我們能在移位之前判斷這個數(shù)字是不是2的n次冪后再進行移位，這樣是不是就不用減一了良价；然后比較下這兩種處理方式的性能寝殴，才明白蒿叠，直接減一肯定比判斷這個數(shù)字是不是2的n次冪要簡單的多，并且也快得多蚣常；并且當數(shù)字為2的n次冪時市咽，減一肯定不會使二進制數(shù)字的最高位移位，因為只有當數(shù)字為2的n次冪時抵蚊，二進制數(shù)字才是最高位是1施绎，后面全是0；其他任何情況贞绳，減一谷醉，都是修改非最高位數(shù)字，所以根本沒影響冈闭；然后到這里俱尼，就完全明白了這段代碼的邏輯，為啥HashMap性能高萎攒，因為全部是位運算遇八；
三、highestOneBit運算
那到這里就完了嗎躺酒；不押蚤，都研究到這里了蔑歌，不把highestOneBit搞明白羹应，我估計是睡不著覺了；開始看見這段邏輯我是拒絕的次屠，這矩陣都是啥啥啥啊园匹。。劫灶。算了裸违，用最原始的方式來吧；看到這個方法本昏，就發(fā)現(xiàn)供汛，都是向右移，開始移一位進行或運算涌穆，然后移兩位進行或運算怔昨，再移四位進行或運算......手動操作了下，就看明白了矮烹，我舉個極端例子吧越庇，當進入到這個方法剛好是2的n次冪，比如16搬味，運算流程如下：
因為最高位肯定是1问芬，我們不用管后面的位數(shù)是什么數(shù)字强戴，這個算法就是剛好能把所有位上全變成1墨微，因為第一次移一位最域，進行一次或運算，這樣，前兩位肯定都是1了翘魄，然后再把前兩位往右移兩位，然后進行或運算绩鸣，這樣前四位就都是1了，再移4位，8位垒手，16位鳖悠。。胞皱。這樣就得到了所有位上全是1的二進制數(shù)字了允蚣，然后把這個二進制數(shù)字向右移一位做入，然后減掉，就得到了只有最高位是1埠况，后面全是0的狈谊，2的n次冪數(shù)字了喜命；
四、JDK8中HashMap鏈表擴容
分析了上面一塊位運算，然后看到了JDK8赎瞎，如果遇到鏈表結(jié)構缓呛，遷移時攀涵，居然沒有用到取模算法去獲取該節(jié)點的位置，直接分成兩類裆操，一類直接遷入新數(shù)組的同樣索引位置怒详，一類直接遷入同樣索引加上原來數(shù)組長度的索引位置；網(wǎng)上有人說缎岗，這個是2的n次冪特性静尼，其實，這個是擴容選擇雙倍的特性；應為鼠渺，舉個例子：14%3=2? 當3擴大兩倍后 14%6=2蜗元，這是第一種情況；第二種情況系冗，就是? 17%3=2? 擴大兩倍后? 17%6=5=2+3奕扣；其實這個想的話，很容易就能想的明白掌敬；這個是數(shù)學原理惯豆，然后我們再看看代碼，這個是用位運算來代替這個原理奔害；我們回到上面(n -1) & hash這個算法的原理上楷兽，看一下就能明白為什么這個直接&就能知道，要不要加原來數(shù)組長度了华临；比如當前有兩個hash值芯杀，一個為17，一個為21雅潭，擴容前數(shù)組長度為4揭厚，擴容后為8；擴容前扶供，都落在索引為1的位置筛圆；擴容后，一個在1椿浓，一個在5太援；下面我們看下二進制計算過程；
首先1.8的算法直接用hash和原來數(shù)組的大小直接進行&運算扳碍，運算后提岔，要么是0要么是原來數(shù)組的長度（可以用上面的例子來進行驗證下，因為是2的n次冪笋敞，所以只有一位上是1碱蒙，其他位上全是0）；然后這一&運算液样，運算后振亮，就能知道擴容時巧还，原來差的那一位到底是1鞭莽，還是0；如果是1的話麸祷，得到的值肯定是大于0的澎怒，是0的話，得到的值肯定是0；然后我們再看下喷面，如果用原來的(n -1) & hash算法時星瘾，如果原來位置上是0，擴容后進行這個運算惧辈，得到的值是原值琳状；如果原來位置上是1，擴容后進行這個運算盒齿，得到的值就是念逞，數(shù)組原值最高位上，少了個1边翁，這樣轉(zhuǎn)成10進制翎承，就是剛好加上原值就行；所以這個就是為什么不用重新進行(n -1) & hash符匾，只需要 (hash&oldcap) 的原理;
