學習java的同學注意了！！！ 學習過程中遇到什么問題或者想獲取學習資源的話，歡迎加入Java學習交流群，群號碼：183993990  我們一起學Java！

一、數組是什么？

忘了在哪本書里曾看到過類似這樣的一句話“所有的數據結構都是數組的演化”，想想其實是有道理的，因為計算機的內存其實就是線性的存儲空間。

Java示例代碼：

int[] array = new int[5]
忽略對象頭信息和數組長度信息，JVM執行時會在堆中分配20個字節的內存空間，看起來就是這樣的：
這樣的數據結構可以很方便地通過數組下標存取數據，但在查找時需要遍歷數組，平均時間復雜度為O(n/2)。
當數據量很大或者查找操作頻繁的時候，這樣的遍歷操作幾乎是不可接受的。那么，如何才能夠在更短的時間內快速找到數據呢？
二、二分查找
假如數組內的元素是已經排序的，那么很自然的方式就是使用二分查找。
譬如有一個整形數組的長度為1000，數組內的整數從小到大排列，如果我想要知道6000是否在此數組中。那么我可以先查看array[500]的數字是否為6000，array[500]的數字比6000小，那么就查看array[750]位置的數字……依次類推，那么最多經過10次，就可以確定結果。
此算法的時間復雜度為O(logN)。
然而，大部分情況下數組元素都是無序的，而排序所需要的時間復雜度O(NlogN)通常都遠遠超過遍歷所需要的時間。
那么，問題又回到了原點。該如何在無序的數據中快速找到數據呢？
三、懵懂的思考
還記得剛學編程不久時看《編程珠璣》，其中有一段描述：20世紀70年代，Mike Lesk為電話公司做了電話號碼查找功能，譬如輸入LESK*M*對應的數字鍵5375*6*，可以返回正確的電話號碼或可選列表，錯誤匹配率僅0.2%。
怎么才能做到？
當時我還完全不了解數據結構和算法，還原下當時天馬行空思考的過程，現在看起來仍然是很有意思的。
1、加法
所有數字相加(*鍵為11)，5375*6*的和為48。大多數輸入的和不超過100，意味著幾萬個電話號碼都會聚集在數組前100的位置，所以是不可行的。
2、乘法
所有數字相乘，積為381150。這似乎是可行的，但出現了這樣的問題：lesk、lsek、slke……的積是一樣的，每一個數字鍵還對應著3個字母，意味著重復的概率會很高。
3、改進后的乘法
①字母相同但字母序不同的字符串，可以通過這樣的方式來避免沖突：每一個數字先乘以序號，然后再與其它值相乘。
②每一個數字鍵對應了3個英文字母，如果用戶沒有輸入字母在數字鍵中的序號，是沒辦法再進一步精確計算的。能考慮的方向只能是根據給定的單詞表來做概率統計，所以不予考慮。
4、位置沖突
即使用改進后的乘法，不同的姓名字母計算得出的積依然還是可能會發生重復，那么當發生沖突后應該怎么辦？
順序保存到下一個空白位置？仔細想想這是行不通的。如果下一個空白位置剛好又是另外的字母集合的積，那就產生了二次沖突。
幸好，還有質數。
質數只能被1和自身整除，那么上述乘法得出的任何積都不可能是質數，所以質數位置是沒有保存電話號碼的。
因此，以當前積為起點向右搜索下一個質數，如果該質數位置依然被使用，那么就繼續查找下一個最近的質數……
至此，問題似乎是解決了。
用戶輸入一串數字，根據公式計算得到積，返回該下標位置的電話號碼。如果不正確，再順序查找后面的質數，直到某個質數下標的數組元素為空為止，最后返回所有查找到的電話號碼。大部分情況下，只需要O(1)的時間復雜度就可以找到電話號碼。
5、數組太大
唯一的問題是，按照上述思路建立的數組實在是太大了。一個姓名有10個字母，假如每一個字母對應的數字都是9，最后得到的積約是9的17次方。這意味著要建立9^17大小的數組，這是完全不可行的。
6、后來
即使不考慮數組過大因素，以我當時初學編程的水平，這樣的程序也是沒有能力寫出來的。
我之所以還原這個思考的過程，是覺得獨立思考的過程非常有趣也很有價值。想想，其實現有的算法都是當年那些大牛在實際工程中一步一步尋求解決方案而最終推導得到的。
因此，當在工程中碰到一些棘手的難題時，只要樂于思考分解問題并尋求每一個小問題解決方案，那么很多所謂的難題都是可以解決的。
后來看了《數據結構與算法分析.Java語言描述》，我才知道原來我的思路其實就是開放尋址法（Open Addressing）。
JDK的HashMap使用的則是分離鏈接法(separate chaining)。不同：增加了桶的概念來保存沖突的數據；進行求余運算來降低數組大小。
那么，就談談Java中的HashMap吧。
四、HashMap結構及算法詳解
HashMap的本質依然是數組，而且是一個不定長的多維數組，近似于下圖這樣的結構：
1、簡單介紹
HashMap中的數組保存鏈表的頭節點。
保存數據：
計算key的hashCode，再與數組長度進行求余運算得到數組下標(鏈表頭節點)。
如果該位置為空，生成一個新的鏈表節點并保存到該數組。
如果該位置非空，循環比對鏈表的每一個節點：已經存在key相同的節點，覆蓋舊節點；不存在key相同的節點，將新節點作為鏈表的尾節點（注：查看JDK1.8中的源碼，新節點總是加入到鏈表末尾，而不是如JDK1.6一般作為鏈表頭節點）。
查找數據：
計算key的hashCode，再與數組長度進行求余運算得到數組下標(鏈表頭節點)。如果鏈表不為空，先比對首節點，如果首節點key相同（hashCode相同且equals為true），直接返回首節點的value；首節點key不同則順序遍歷比對鏈表其它節點，返回key相同的節點的value（未找到key相同的節點則返回null）。
HashMap引入鏈表的目的就是為了解決上一節討論過的重復沖突問題。
注意事項：
如果所有key的hashcode相同，假定均為0，則0%4 = 0，所有元素就會都保存到鏈表0，保存和查找每一個數據都需要遍歷鏈表0。那么，此時的HashMap實質上已經退化成了鏈表，時間復雜度也從設計的O(1)上升到了O(n/2)。
為了盡可能地讓HashMap的查找和保存的時間復雜度保持在O(1),就需要讓元素均勻地分布在每一個鏈表，也就是每一個鏈表只保存一個元素。
那么影響因素有哪些？
一是key的hashcode不能重復，如果重復就肯定會有鏈表保存至少2個元素；二是哈希函數設計，如果只是簡單的求余，那么余數會有大量重復；三是鏈表的大小，如果100個元素要分布在長度為10的數組，無論怎么計算都會導致其中有鏈表保存多個元素，最好的情況是每個鏈表保存10個；
下面分別詳細介紹這三個因素的算法設計。
2、hashcode生成
這是String類的hashCode生成代碼。
　　public int hashCode() {　　　　int h = hash;　　　　if (h == 0 && value.length > 0) {　　　　　　char val[] = value;　　　　　　for (int i = 0; i < value.length; i++) {　　　　　　　　h = 31 * h + val[i];　　　　　　}　　　　　　hash = h;　　　　}　　　　return h;　　}
String類的value是char[]，char可以轉換成UTF-8編碼。譬如，’a’、’b’、’c’的UTF-8編碼分別是97,98,99；“abc”根據上面的代碼轉換成公式就是：
h = 31 * 0 + 97 = 97；h = 31 * 97 + 98 = 3105；h = 31 * 3105 + 99 = 96354；
使用31作為乘數因子是因為它是一個比較合適大小的質數：如值過小，當參與計算hashcode的項數較少時會導致積過小；如為偶數，則相當于是左位移，當乘法溢出時會造成有規律的位信息丟失。而這兩者都會導致重復率增加。
如果使用32作為乘數因子(相當于 << 5)，以字符串“abcabcabcabcabc”為例，它的hashcode的每一步計算結果如下圖：
如上圖所示，字符串末尾每3個字母就會產生一個重復的hashcode。這并不是一個巧合，即使換成其它的英文字母，也有很容易產生重復，而使用質數則會大大地減少重復可能性。有興趣的可以參照上圖去作一下左位移運算，會發現這并不是偶然。
《Effective Java》一書中詳細描述了hashcode的生成規則和注意事項，有興趣的可以去看看。
從源代碼的hashCode()方法可知，String類對象保存了已經計算好的hashCode，如果已經調用過hashCode()方法，那么第二次調用時不會再重新生成，而是直接返回已經計算好的hashCode。
String對象總是會存放到String類私有維護的常量池中，不顯式使用new關鍵字時，如果常量池中已經有value相同的對象，那么總是會返回已有對象的引用。因此，很多情況下生成hashCode這種比較昂貴的操作實際上并不需要執行。
3、哈希函數設計
現在，已經得到了重復率很低的hashCode，還有什么美中不足的地方嗎？
擾動函數
　　static final int hash(Object key) {　　　　　　int h;　　　　　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);　　}
下圖還是以字符串“abcabcabcabcabc”為例，使用上面方法得到的運算過程和結果。
為什么要先無符號右位移16位，然后再執行異或運算？看看下圖的二進制的與運算，你就會明白。
你會發現只要二進制數后4位不變，前面的二進制位無論如何變化都會出現相同的結果。為了防止出現這種高位變化而低位不變導致的運算結果相同的情況，因此需要將高位的變化也加入進來，而將整數的二進制位上半部與下半部進行異或操作就可以得到這個效果。
為什么要使用與運算？
因為哈希函數的計算公式就是hashCode % tableSize，當tableSize是2的n次方(n≥1)的時候，等價于hashCode & (tableSize – 1)。
擾動函數優化前：1954974080 % 16 = 1954974080 & (16 – 1) = 0擾動函數優化后：1955003654 % 16 = 1955003654 & (16 – 1) = 6
這就是為什么需要增加擾動函數的原因。
源代碼詳解
代碼解釋之前需要補充說明一下，jdk1.8引入了紅黑樹來解決大量沖突時的查找效率，所以當一個鏈表中的數據大到一定規模的時候，鏈表會轉換成紅黑樹。因此在jdk1.8中，HashMap的查找和保存數據的最大時間復雜度實際上就是紅黑樹的時間復雜度O(logN)。
以下是HashMap中的保存數據的方法源代碼，相信經過以上的描述，已經非常容易看懂這一段代碼。
　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {　　　　Node<K,V>[] tab;　　　　//HashMap數組　　　　Node<K,V> p;　　　　　　//初始化需要保存的數據　　　　int n;　　　　　　　　　//數組容量　　　　int i;　　　　　　　　　//數組下標　　　　/* 如果數組為空或0，初始化容量為16 */　　　　if ((tab = table) == null || (n = tab.length) == 0){　　　　　　n = (tab = resize()).length;　　　　}　　　　/* 使用哈希函數獲取數組位置(如果為空，保存新節點到數組) */　　　　if ((p = tab[i = (n - 1) & hash]) == null){　　　　　　tab[i] = newNode(hash, key, value, null);　　　　}　　　　/* 如果數組位置已經有值，則使用下列方式保存數據 */　　　　else {　　　　　　Node<K,V> e;　　　　//臨時節點保存新值　　　　　　K k;　　　　　　　　//臨時變量用于比較key　　　　　　//如果頭節點與新節點的key的hash值相同 且 key的值相等，e賦值為舊節點　　　　　　if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){　　　　　　　　e = p;　　　　　　}　　　　　　//如果頭節點是一個紅黑樹節點，那么e將保存為樹節點　　　　　　else if (p instanceof TreeNode){　　　　　　	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);　　　　　　}　　　　　　//如果頭節點與新節點不同，且頭節點不是紅黑樹節點，循環比對鏈表的所有節點　　　　　　else {　　　　　　　　for (int binCount = 0; ; ++binCount) {　　　　　　　　　　if ((e = p.next) == null) {　　　　　　　　　　　　//如果直到鏈表尾未找到相同key的節點，將新結點作為最后一個節點加入到鏈表　　　　　　　　　　　　p.next = newNode(hash, key, value, null);　　　　　　　　　　　　//如果鏈表節點數大于等于8-1，轉換成紅黑樹；轉換成紅黑樹的最小節點數是8　　　　　　　　　　　　if (binCount >= TREEIFY_THRESHOLD - 1){　　　　　　　　　　　　　　treeifyBin(tab, hash);　　　　　　　　　　　　}　　　　　　　　　　　　break;　　　　　　　　　　}　　　　　　　　　　//如果循環過程中發現新舊key的值相同，跳轉：是否覆蓋舊值　　　　　　　　　　if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){　　　　　　　　　　　　break;　　　　　　　　　　}　　　　　　　　　　p = e;　　　　　　　　}　　　　　　}　　　　　　//是否覆蓋舊值　　　　　　if (e != null) {　　　　　　　　V oldValue = e.value;　　　　　　　　//如果新值不為空且（允許修改舊值 或 舊值為空），覆蓋舊節點的值　　　　　　　　if (!onlyIfAbsent || oldValue == null){　　　　　　　　　　e.value = value; 	　　　　　　　　}　　　　　　　　afterNodeaccess(e);　　//回調函數，這里是空函數，但在linkedHashMap中實現了此方法　　　　　　　　return oldValue;　　　　//返回舊值　　　　　　}　　　　}　　　　//用于比較判斷是否在遍歷集合過程中有其它線程修改集合，詳情請網上搜索fail-fast快速失敗機制　　　　++modCount;　　　　//當key數量大于允許容量時進行擴容。允許容量在HashMap中是數組長度 * 裝填因子(默認0.75)　　　　if (++size > threshold){　　　　	resize();　　　　}　　　　//回調函數，這里是空函數，但在linkedHashMap中實現了此方法　　　　afterNodeInsertion(evict);　　　　return null;　　}
簡化后的偽代碼
　　putval(key, value){　　　　index = key.hashcode % tablesize;　　　　if(null == table[index]){　　　　　　table[index] = new node(key, value);　　　　}else{　　　　　　firstNode = table[index];　　　　　　nextNode = firstNode.next;　　　　　　while(nextNode.hasNextNode()){　　　　　　　　//如果找到相同key的舊節點，覆蓋舊節點　　　　　　　　if(key == nextNode.key){　　　　　　　　　　nextNode = new node(key, value);　　　　　　　　　　　　break;　　　　　　　　}　　　　　　　　//如果到隊列末尾依然沒有找到相同key的舊節點，將新結點加入到最后一個節點的末尾　　　　　　　　if(nextNode.next == null){　　　　　　　　　　nextNode.next = new node(key, value);　　　　　　　　　　break;　　　　　　　　}　　　　　　　　nextNode = nextNode.next;　　　　　　}　　　　}　　}
鏈表大小設計
代碼注釋中已經稍有提及，這里再分別展開討論。
①容量選擇
HashMap的初始容量是 1 << 4，也就是16。以后每次擴容都是size << 1，也就是擴容成原來容量的2倍。如此設計是因為 2^n-1(n≥1)的二進制表示總是為重復的1，方便進行求余運算。
《數據結構與算法分析.Java語言描述》一書中的建議是容量最好是質數，有助于降低沖突，但沒有給出證明或實驗數據。
質數雖然是神奇的數字，但個人感覺在這里并沒有特別的用處。
根據公式index = hashCode % size可知，無論size是質數還是非質數，index的值區間都是0至(size-1)之間，似乎真正起決定作用的是hashCode的隨機性要好。
這里先不下結論，待以后再寫一個隨機函數比較下質數和非質數重復率。
②裝填因子
裝填因子默認是0.75，也就是說如果數組容量為16，那么當key的數量大于12時，HashMap會進行擴容。
裝填因子設計成0.75的目的是為了平衡時間和空間性能。過小會導致數組太過于稀疏，空間利用率不高；過大會導致沖突增大，時間復雜度會上升。
關于其它
紅黑樹是在JDK 1.8中引入的，想用簡單的語言來講清楚紅黑樹的數據結構、增刪改查操作及時間復雜度分析，這是一個復雜且艱難的任務，更適合單獨來描述，因此留待以后吧。
五、最小完美哈希函數(Minimal Perfect Hash Function, MPHF)
Jdk中的HashMap解決了任意數據集的時間復雜度問題，所設計的哈希函數在未知數據集的情況下有良好的表現。
但如果有一個已知數據集(如Java關鍵字集合)，如何設計一個哈希函數才能同時滿足以下兩方面的要求：
⑴ 容器容量與數據集合的大小完全一致；⑵ 沒有任何沖突。
也就是說，當給定一個確定的數據集時，如果一個哈希函數能讓容器的每一個節點有且僅有一個數據元素，這樣的哈希函數便稱之為最小完美哈希函數。
最近在研究編譯原理，提到說如何解決關鍵字集合的O(1)時間復雜度的查找問題，提到了可以采用最小完美哈希函數。看到一個這樣的名詞，瞬間就覺得很好很高大上。
學習Java的同學注意了！！！ 學習過程中遇到什么問題或者想獲取學習資源的話，歡迎加入Java學習交流群，群號碼：183993990  我們一起學Java！