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