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