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

一、數(shù)組是什么？

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

Java示例代碼：

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