HashMap源碼分析——put和get（一）
前言
首先，這是自己的開的不知道多少個坑的筆記了（汗顏）蒲祈，這些筆記都是自己在Java這條道路上的初學(xué)階段所思所想，并沒有多少含金量～
想第一篇記一記HashMap，沒有為什么腔剂，任性。
首先驼仪，HashMap的基本方法應(yīng)該都知道了掸犬，put(key,value)以及get(key)袜漩。
另外值得注意的一個基礎(chǔ)問題是HashMap的key、value都不能是基本數(shù)據(jù)類型（即不能為byte short int long char float double boolean）,但是很特別的一點是key和value可以為null
1. 慢著 開始之前復(fù)習(xí)下異或和右移運算符
1.1 異或的基本運算
異或是二元按位運算符的一種湾碎，最基本的概念是在當(dāng)前位下噪服，兩個二進制相同則為0，不同則為1
public static void main(String []args){
int i = -5;
int j = 5;
System.out.println("i : " + Integer.toBinaryString(i));
System.out.println("j : " + Integer.toBinaryString(j));
System.out.println("i ^ j : " + Integer.toBinaryString(i ^ j));
System.out.println("i ^ j : " + (i ^ j));
/**
* output :
* i : 11111111111111111111111111111011
* j : 101
* i ^ j : 11111111111111111111111111111110
* i ^ j : -2
*/
}
1.2 異或規(guī)律
- 0異或A結(jié)果都為A ： 0 ^ 1 = 1 0 ^ 0 = 0
- 1異或A結(jié)果都為A的相反數(shù) ： 1 ^ 1 = 0 1 ^ 0 = 0
- A異或A結(jié)果都為0
1.3 異或進階
關(guān)于異或進階不再贅述胜茧，大家可以觀看維基百科中的異或講解
值得一提的是面試經(jīng)常會考到：如何不使用第三個參數(shù)來交換a和b的值，這時候就可以使用異或仇味。
int a = 10;
int b = 41;
a = b ^ a;
b = b ^ a; // b = b ^ ( b ^ a) = a
a = a ^ b; // a = ( b ^ a ) ^ a = b
1.4 左移和右移運算符和它們的規(guī)律
左移和右移運算符是奇怪的運算操作符呻顽，我剛開始學(xué)的時候覺得不就是移位嘛，移位就是了丹墨，后來看《Java編程思想》的時候才知道原來左移和右移原來有這樣那樣的限制……
先從最簡單的開始說廊遍，左移就是低位補0，右移就是高位補符號位贩挣，無符號右移運算符就是高位補0（這里不再贅述）
接著 在一般情況下 左移和右移都有下面的規(guī)律 :
- a << b = a * (2 ^ b)
- a >> b = a / (2 ^ b)
例如 :
public static void main(String []args){
int i = 5;
int j = 32;
int m = 40;
System.out.println(3 << i);
System.out.println(3 << j);
System.out.println(3 << m);
/**
* output :
* 96
* 3
* 768
*/
}
大家可能發(fā)現(xiàn)了喉前，有些結(jié)果好像與公式并不符合，這是因為int類型的“限制”
眾所周知王财，在Java中int占四個字節(jié)卵迂，也就是32位，在做移位操作時绒净，無論是左移還是右移见咒，右操作運算符都不能大于或者等于32（當(dāng)然，我說的是左邊的數(shù)值是int類型時）挂疆，因為一旦超過了32改览，左邊的數(shù)值完全變了個樣。就拿1 << 32而言：
我們發(fā)現(xiàn)1 << 32如果按照正常計算的話就會變成0缤言，更別提3 << 32宝当，5 << 91了，如果按照正常流程來的話胆萧，只要右操作數(shù)大于32庆揩，結(jié)果都變成了0，當(dāng)然跌穗，Java不可能這樣子計算盾鳞，它采取了一種聰明的操作方式，至于為什么瞻离，目前不在討論范圍只內(nèi)腾仅。另一種狀況是，如果恰巧將1移到了符號位上套利，即便移位之前是正的數(shù)字推励，也會變成負的鹤耍，就像1 << 31 = - 2147483648 那樣。所以验辞，在上邊說的公式有諸多的限制稿黄。
這種聰明的方式就是，在左操作數(shù)類型為int時跌造，當(dāng)右側(cè)數(shù)值大于等于32杆怕，都可以對右操作數(shù)取余操作（ % 32），然后再做移位運算壳贪，例如：
3 << 40 = 3 << (40 % 32) = 3 << 8 = 3 * (2 ^ 8) = 768
以上都說的是int類型下的移位操作陵珍，如果左邊操作數(shù)為char、byte违施、short類型都會被轉(zhuǎn)換成int類型處理互纯，當(dāng)左操作數(shù)是long的時候，右邊操作數(shù)的最大限制變成了64磕蒲。
2. HashMap
2.1 從HashMap結(jié)構(gòu)說起
HashMap結(jié)構(gòu)如下圖所示:
總的來說留潦，HashMap的結(jié)構(gòu)是：數(shù)組+鏈表+紅黑樹 （PS : 我用的是8版本的）
目前，現(xiàn)將紅黑二叉樹看成是一個不一般的二叉樹吧（我能說現(xiàn)階段不知道什么是紅黑二叉樹嘛XD）辣往。以上三張圖分別就是組成HashMap的三種數(shù)據(jù)結(jié)構(gòu)了兔院。
然后，再來看一下幾個HashMap中幾個重要的字段 :
/**
* 默認的數(shù)組容量(也就是數(shù)組的長度) —— 數(shù)字必須是二次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 數(shù)組的最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 當(dāng)使用無參構(gòu)造函數(shù)時 默認的加載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 當(dāng)某個數(shù)組下的鏈表長度超過8時 鏈表將會轉(zhuǎn)換為紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 當(dāng)節(jié)點的數(shù)量超過threshold時會發(fā)生擴容 此外 當(dāng)尚未初始化數(shù)組的時候站削，這個字段也會存放初始數(shù)組的容量秆乳，如果是0的話表示容量是默認的數(shù)組容量(16)
*/
int threshold;
什么是加載因子？我搜索了百度钻哩，然后一臉懵逼屹堰，它是這樣介紹的：
加載因子是表示Hsah表中元素的填滿的程度。
一臉懵逼街氢，兩臉茫然扯键，然后，在進行相關(guān)搜索珊肃，發(fā)現(xiàn)這個比較靠譜
threshold(閾值) = (int)加載因子 * 數(shù)組容量
還是有點懵逼Ｈ傩獭！伦乔！意思就是說當(dāng) 節(jié)點數(shù)量 > 數(shù)組容量 * 加載因子時厉亏，數(shù)組會擴容.
我們來驗證一下吧！烈和！
2.2 HashMap的構(gòu)造函數(shù)
我們通過idea發(fā)現(xiàn)HashMap有四種構(gòu)造函數(shù)爱只，先看前三種（畢竟最后一種不是重點）：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
-
無參構(gòu)造函數(shù) ： 設(shè)置了加載因子為默認加載因子(0.75f)
PS 再來回顧下加載因子是干嘛的：加載因子是擴容用的 什么時候該擴容呢？就是節(jié)點個數(shù)大于加載因子??數(shù)組長度的時候就該擴容了
一個參數(shù)的構(gòu)造函數(shù) ： 設(shè)置了容量初始容量招刹，然后在源碼里面直接this交給了第三個構(gòu)造參數(shù)處理
兩個參數(shù)的構(gòu)造函數(shù) ： 設(shè)置了初始容量以及加載因子恬试，我發(fā)現(xiàn)在這個構(gòu)造函數(shù)中好像并沒有關(guān)于數(shù)組初始容量的更多限制啊窝趣，剛才源碼中不是說初始容量必須是二次冪嗎？我傳一個13训柴，19哑舒，在這個構(gòu)造參數(shù)中也沒拋出異常啊!!不急，我們看最后一句 :
this.threshold = tableSizeFor(initialCapacity);
我們傳入的初始容量13幻馁，18洗鸵，41……這些“不規(guī)范的”（也就是不是二次冪的）數(shù)字傳給了tableSizeFor這個函數(shù)，最終返回給了threshold這個變量中（別忘了仗嗦，這個變量除了可以記錄“擴張閾值”膘滨，在數(shù)組還沒有初始化的時候還可以存放數(shù)組的自定義容量，這些都是注釋中所標(biāo)注的東西）儒将。來領(lǐng)略一下tableSizeFor的真正魅力，這個函數(shù)可以 ：
把任何一個int類型的对蒲、大于0的數(shù)字轉(zhuǎn)成一個與之相近并大于這個數(shù)字的二次冪整數(shù)
聽上去有點繞口钩蚊，簡單點說15進去了成了16，17進去了出來搖身一變成了32（比17大的最小二次冪整數(shù)就是32了）蹈矮，非常神奇的一個函數(shù)砰逻，第二小篇接著看這個函數(shù)。
下一小節(jié) ： HashMap源碼分析——put和get（二）
