1苛蒲、hashmap 計(jì)算下標(biāo)的位置

1111 1111 1111 1111 1111 0000 1110 1010? -- hashcode值（調(diào)用hashcode得到）

0000 0000 0000 0000 1111 1111 1111 1111? -- 無(wú)符號(hào)右移16位

1111 1111 1111 1111 0000 1111 0001 0101? -- ^異或運(yùn)算 相同取0 不同取1? 得到hash值

假設(shè)length=16? length-1=15

hash&（length-1）

1111 1111 1111 1111 0000 1111 0001 0101? -- hash值

0000 0000 0000 0000 0000 0000 0000 1111? -- length-1

0000 0000 0000 0000 0000 0000 0000 0101? -- 做&運(yùn)算? 下標(biāo)為5

2社证、為什么hashMap的容量是2的n次冪?

hash%length等于hash&(length-1)的前提是length是2的n次冪洒宝。

hash &（length-1）

假如容量length=8? length-1=7? ? ? 假如容量length=7? length-1=6

0000 0001 ? ????????????????????????????????????????0000 0001

0000 0111? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0110

0000 0001 --1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0000? --0

0000 0010 ? ????????????????????????????????????????0000 0010

0000 0111? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0110

0000 0010 --2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0010? --2

0000 0011? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0011

0000 0111? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0110

0000 0011 --3? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0010? --2

0000 0100? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0100

0000 0111? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0111

0000 0100 --4? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000 0100? --4

3、如果在創(chuàng)建HashMap對(duì)象的時(shí)候虚吟，指定的容量不是2的n次冪辜伟，比如10，

HashMap會(huì)通過(guò)一系列位移運(yùn)算和或運(yùn)算得到一個(gè)2的n次冪非凌，這個(gè)數(shù)字是離我們指定容量最近的數(shù)字

cap=10? 為防止cap已經(jīng)是2的n次冪需要 n=cap-1 =9?

做或運(yùn)算 比較的位上只要有一個(gè)為1就都為1

n|=n>>>1

0000 0000 0000 0000 0000 0000 0000 1001? --9

0000 0000 0000 0000 0000 0000 0000 0100? --右移1位

0000 0000 0000 0000 0000 0000 0000 1101? --13

n|=n>>>2

0000 0000 0000 0000 0000 0000 0000 1101? --13

0000 0000 0000 0000 0000 0000 0000 0011? --右移2位

0000 0000 0000 0000 0000 0000 0000 1111? --15

n|=n>>>4

0000 0000 0000 0000 0000 0000 0000 1111? --15

0000 0000 0000 0000 0000 0000 0000 0000? --右移4位

0000 0000 0000 0000 0000 0000 0000 1111? --15

cap =n+1= 16

4、hashmap的擴(kuò)容

n：16? ? n-1=15

0000 0000 0000 0000 0000 0000 0001 0000? --16

0000 0000 0000 0000 0000 0000 0000 1111? --15

1111 1111 1111 1111 1111 0000 0000 0101? --key1

1111 1111 1111 1111 1111 0000 0001 0101? --key2

hash&（length-1）

0000 0000 0000 0000 0000 0000 0000 0101? --key1的下標(biāo)? 5

0000 0000 0000 0000 0000 0000 0000 0101? --key2的下標(biāo)? 5

擴(kuò)容 n:32 n-1=31

0000 0000 0000 0000 0000 0000 0010 0000? --32

0000 0000 0000 0000 0000 0000 0001 1111? --31

1111 1111 1111 1111 1111 0000 0000 0101? --key1

1111 1111 1111 1111 1111 0000 0001 0101? --key2

hash&（length-1）

0000 0000 0000 0000 0000 0000 0000 0101? --key1的新下標(biāo)? 5

0000 0000 0000 0000 0000 0000 0001 0101? --key2的新下標(biāo)? 21