第10章散列表與HashMap類(lèi)2024/11/9110.1散列結(jié)構(gòu)的特點(diǎn)2024/11/92生活中有些數(shù)據(jù)之間可能是密切相關(guān)的一對(duì)，例如，一副手套，一雙鞋子，一對(duì)夫妻等，即數(shù)據(jù)的邏輯結(jié)構(gòu)是成對(duì)的，即不是線性也不是樹(shù)形結(jié)構(gòu)，一對(duì)數(shù)據(jù)與另一對(duì)數(shù)據(jù)之間也無(wú)須有必然的關(guān)系。如何存儲(chǔ)這樣的數(shù)據(jù)對(duì)，也是數(shù)據(jù)結(jié)構(gòu)非常關(guān)心的，以下要介紹的散列結(jié)構(gòu)，就是存儲(chǔ)“數(shù)據(jù)對(duì)”的最重用的手段之一.2024/11/9310.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表數(shù)據(jù)對(duì)，也稱作"鍵-值"對(duì)，鍵和值都是某種類(lèi)的實(shí)例，即對(duì)象。敘述時(shí)可以把這"鍵-值"對(duì)記作(key,value)，稱key是關(guān)鍵字、value是鍵值或值。散列結(jié)構(gòu)使用兩個(gè)集合存儲(chǔ)對(duì)象，一個(gè)集合稱作關(guān)鍵字集合，記作Key。另一個(gè)是值的集合，記作Value。Key集合中的節(jié)點(diǎn)（或稱元素）負(fù)責(zé)存儲(chǔ)關(guān)鍵字，所有關(guān)鍵字對(duì)應(yīng)的全部值稱作散列結(jié)構(gòu)的值集合，記作Value，即Value中的節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)值。稱Value為散列結(jié)構(gòu)中的散列表（hash表，也常常被音譯稱作哈希表）。簡(jiǎn)單說(shuō)，散列結(jié)構(gòu)是根據(jù)關(guān)鍵字直接進(jìn)行訪問(wèn)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，其核心思想是使用散列函數(shù)（hash()函數(shù)）把關(guān)鍵字映射到散列表中一個(gè)位置，即映射到散列表中的某個(gè)節(jié)點(diǎn)。2024/11/9410.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表hash()函數(shù)本質(zhì)上就是集合Key到整數(shù)集合

2024/11/9510.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表對(duì)于一個(gè)關(guān)鍵字，比如key1，如果hash(key1)=98，那么key1關(guān)鍵字對(duì)應(yīng)的節(jié)點(diǎn)就是數(shù)組hashValue第98個(gè)元素，即hashValue[98]。2024/11/9610.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表一個(gè)散列函數(shù)，即hash()函數(shù)需保證下列兩點(diǎn)：①

對(duì)于不同的關(guān)鍵字，比如，key1，key2是Key中兩個(gè)節(jié)點(diǎn)，即兩個(gè)關(guān)鍵字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是兩個(gè)不同的節(jié)點(diǎn)。但節(jié)點(diǎn)中的對(duì)象可能是相同的（數(shù)組的兩個(gè)不同的元素中的值可能是相同的）。②為了保證第①點(diǎn)，讓hash()函數(shù)映射出的全部節(jié)點(diǎn)，分散地分布在一塊連續(xù)的內(nèi)存中，這也是人們把Value稱作一個(gè)散列表的原因。由于散列表中的節(jié)點(diǎn)是隨機(jī)、分散分布的，所以我們不在散列表上定義任何關(guān)系（見(jiàn)第1章）。散列表或散列二字不是指數(shù)據(jù)之間的關(guān)系，而是形容存儲(chǔ)形式的特點(diǎn)（hash()函數(shù)映射存儲(chǔ)位置）。如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問(wèn)題的算法。2024/11/9710.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問(wèn)題的算法?？梢杂面溄臃ń鉀Q沖突，散列函數(shù)把和關(guān)鍵字key有相同對(duì)應(yīng)的值的那些關(guān)鍵字所對(duì)應(yīng)的存儲(chǔ)位置依次設(shè)置為一個(gè)鏈表的中不同的節(jié)點(diǎn)（鏈表頭節(jié)點(diǎn)是key對(duì)應(yīng)的存儲(chǔ)位置），這樣一來(lái)，就會(huì)增大查詢Value中值的時(shí)間復(fù)雜度。如果散列函數(shù)設(shè)計(jì)的合理，那么一般不會(huì)發(fā)生關(guān)鍵字沖突或發(fā)生關(guān)鍵字沖突的概率非常小，因此也就不需要使用鏈?zhǔn)椒椒ń鉀Q沖突或使用鏈?zhǔn)椒椒ń鉀Q沖突的概率很小。鏈接法是最后保證不同關(guān)鍵字對(duì)應(yīng)的不同節(jié)點(diǎn)（不同的存儲(chǔ)位置）的最后辦法。2024/11/9810.1散列結(jié)構(gòu)的特點(diǎn)●查找、添加、刪除的特點(diǎn)由散列結(jié)構(gòu)的特點(diǎn)可以知道，使用關(guān)鍵字查找、刪除、添加Value中的節(jié)點(diǎn)，時(shí)間復(fù)雜度通常都是

（如果關(guān)鍵字沖突，使用了鏈接法）散列結(jié)構(gòu)具有數(shù)組的優(yōu)點(diǎn)，即非?？斓牟樵兯俣?，同時(shí)又將查詢數(shù)據(jù)（Value）的索引分離到另一個(gè)獨(dú)立的集合中（Key）。數(shù)組最大的缺點(diǎn)就是將索引（下標(biāo)）和數(shù)組元素綁定，因此，一旦創(chuàng)建數(shù)組，就無(wú)法更改索引，即無(wú)法再改變數(shù)組的長(zhǎng)度。而散列結(jié)構(gòu)可以隨時(shí)添加一個(gè)“鍵-值”對(duì)（一個(gè)關(guān)鍵字，一個(gè)相應(yīng)的值），或刪除一個(gè)“鍵-值”對(duì)。10.2簡(jiǎn)單的散列函數(shù)2024/11/99通過(guò)簡(jiǎn)單的例子：停車(chē)場(chǎng)，進(jìn)一步理解散列結(jié)構(gòu)，后面我們將使用Java的HashMap類(lèi)實(shí)現(xiàn)的散列結(jié)構(gòu)。2024/11/91010.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位當(dāng)Value中節(jié)點(diǎn)的數(shù)目越來(lái)越多時(shí)，比如達(dá)到總內(nèi)存大小的一半時(shí)，就要重新調(diào)整內(nèi)存，即分配新的數(shù)組，并把原數(shù)組hashValue[]的值復(fù)制到新的數(shù)組中，新的數(shù)組成為Value的新的一塊連續(xù)內(nèi)存。汽車(chē)停車(chē)場(chǎng)（模擬散列表）初始狀態(tài)有10個(gè)連續(xù)的車(chē)位，相當(dāng)于散列結(jié)構(gòu)中分配給散列表Value的一塊連續(xù)的內(nèi)存空間（數(shù)組的長(zhǎng)度是10）。假設(shè)汽車(chē)的車(chē)牌號(hào)是3位數(shù)的正整數(shù)，相當(dāng)于散列結(jié)構(gòu)中的Key集合中節(jié)點(diǎn)里的關(guān)鍵字。停車(chē)場(chǎng)可以根據(jù)需要，隨時(shí)順序地?cái)U(kuò)大停車(chē)場(chǎng)，即連續(xù)地?cái)U(kuò)建停車(chē)位。

2024/11/91110.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位

2024/11/91210.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位每當(dāng)一輛車(chē)來(lái)到停車(chē)場(chǎng)，如果用散列函數(shù)計(jì)算了若干次，得到的車(chē)位號(hào)對(duì)應(yīng)的車(chē)位上都是已經(jīng)停放了車(chē)輛，這個(gè)時(shí)候，就擴(kuò)建停車(chē)場(chǎng)、讓其容量增加2倍，然后再用散列函數(shù)計(jì)算車(chē)位號(hào)……，如此這般，只要內(nèi)存足夠大，總能找到停車(chē)位，如圖所示意。由于用散列函數(shù)的算法是隨機(jī)的，所以，某個(gè)時(shí)刻以后，擴(kuò)建停車(chē)場(chǎng)的概率就很小了。2024/11/91310.2簡(jiǎn)單的散列函數(shù)●鏈?zhǔn)綌U(kuò)展停車(chē)位當(dāng)用散列函數(shù)計(jì)算出同樣的車(chē)位數(shù)時(shí)，比如都是9，就把二者的停車(chē)位分別指定為同一個(gè)鏈表中的不同的兩個(gè)節(jié)點(diǎn)，鏈表的頭節(jié)點(diǎn)是數(shù)組的第9個(gè)元素。2024/11/91410.2簡(jiǎn)單的散列函數(shù)例子1Key.javaExample10_1.java例子1中的ParkingOne類(lèi)使用順序辦法增加停車(chē)場(chǎng)的車(chē)位，ParkingTwo類(lèi)使用鏈?zhǔn)睫k法增加停車(chē)場(chǎng)的車(chē)位。Car.javaParkingOne.javaParkingTwo.java例子1中的主類(lèi)Example10_1模擬了兩個(gè)停車(chē)場(chǎng)的停車(chē)情況。10.3HashMap類(lèi)2024/11/915HashMap<K,V>泛型類(lèi)繼承Map泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了Map泛型接口中的抽象方法。HashMap<K,V>泛型類(lèi)的對(duì)象為散列表,散列表的Key集合是實(shí)現(xiàn)Set接口的一個(gè)實(shí)例，Key集合中不允許有兩個(gè)結(jié)點(diǎn)中的對(duì)象相同，即大小一樣的兩個(gè)結(jié)點(diǎn)，Key中不同的key對(duì)應(yīng)的Value中的節(jié)點(diǎn)是不同的，但Value中的節(jié)點(diǎn)中的對(duì)象，即數(shù)據(jù)可以是相同的，就像數(shù)組的不同元素（節(jié)點(diǎn)）里可以存放相同的數(shù)據(jù)。HashMap<K,V>泛型類(lèi)提供的添加、刪除、查找等操作的時(shí)間復(fù)雜度都是O(1).2024/11/91610.3HasMap類(lèi)HashMap<K,V>泛型類(lèi)直接實(shí)現(xiàn)了Map接口，注意，沒(méi)有實(shí)現(xiàn)SortedMap接口。2024/11/91710.3HasMap類(lèi)例子2Example10_2.java聲明一個(gè)HashMap<K,V>泛型類(lèi)的對(duì)象，即散列表，必須要指定Key和Value的具體類(lèi)型，類(lèi)型是類(lèi)或接口類(lèi)型（不可以是基本類(lèi)型，比如int、float、char等）即指定Key中節(jié)點(diǎn)里的對(duì)象的類(lèi)型和Value中節(jié)點(diǎn)里的對(duì)象的類(lèi)型。例如，指定K是String類(lèi)型、V是Car類(lèi)型，例如：HashMap<String,Car>hashMap=newHashMap<>();或HashMap<String,Car>hashMap=newHashMap<String,Car>();Car.java例子2中的主類(lèi)Example10_2中首先創(chuàng)建一個(gè)空散列表hashMapOne，然后向散列表hashMapOne添加4個(gè)”鍵-值”對(duì)，隨后再用hashMapOne創(chuàng)建另一個(gè)散列表hashMapTwo。10.4散列表的基本操作2024/11/918publicVput(Kkey,Vvalue)向散列表添加”鍵-值”對(duì)，即將key存儲(chǔ)在Key中，把value放置在Value中，如果添加成功返回null。需要注意的是，如果散列表Key中已經(jīng)有了鍵key，那么當(dāng)前添加的”鍵-值”對(duì)將替換已存在的”鍵-值”對(duì)，并返回舊”鍵-值”對(duì)中的value值，即返回被替換的”鍵-值”對(duì)的值。publicVputIfAbsent(Kkey,Vvalue)如果散列表Key中沒(méi)有key，則添加該鍵值對(duì)(key,value)到散列表，并返回null，如果散列表Key中已經(jīng)有鍵key，則返回舊key對(duì)應(yīng)的value(不做添加操作)。10.4散列表的基本操作2024/11/919publicVget(Objectkey)返回”鍵-值”對(duì)(key,value)中的value，如果key不在集合Key中，方法返回null。publicbooleancontainsKey(Objectkey)判斷Key中是否有關(guān)鍵字key，有返回true，否則返回false。publicbooleancontainsValue(Objectvalue)判斷Value中是否有value，有返回true，否則返回false。publicbooleanisEmpty()如果散列表中沒(méi)有任何"鍵-值"對(duì)，則返回true，否則返回false。10.4散列表的基本操作2024/11/920publicVremove(Objectkey)刪除關(guān)鍵字key組合的”鍵-值”對(duì)(key,value)，并返回value。publicVreplace(Kkey,Vvalue)如果散列表Key已有key，就用(key,value)替換已有的key組合的”鍵-值”對(duì)，并返回替換后的value，如果Key中沒(méi)有關(guān)鍵字key，不進(jìn)行替換操作，并返回null。publicvoidclear()刪除散列表的全部”鍵-值”對(duì)。2024/11/92110.4散列表的基本操作例子3Example10_3.java例子3的主類(lèi)Example10_3使用了HashMap<K,V>泛型類(lèi)的一些常用方法。10.5遍歷散列表2024/11/922publicvoidforEach(BiConsumer<?superK,?superV>action)對(duì)散列表中的所有(key,value)執(zhí)行給定的action操作，直到所有(key,value)對(duì)都被處理或操作引發(fā)異常。BiConsumer是一個(gè)函數(shù)接口，該接口里的抽象方法是voidaccept(Kk,Vv)。使用forEach()方法時(shí)將一個(gè)Lambda表達(dá)式傳遞給action，例如：（k,v）->{System.out.println(v);}。forEach()方法將Lambda表達(dá)式中的k,v，依次取散列表中的(key,value)。2024/11/92310.5遍歷散列表例子4Example10_4.java例子4的主類(lèi)Example10_4將正整數(shù)和正整數(shù)的平方根（最多保留3位小數(shù)）作為(key,value)存放在一個(gè)散列表中，然后遍歷散列表。10.6散列表與字符、單詞頻率2024/11/924●每次讀取文件的一個(gè)字符，如果是字母，并且散列表中還沒(méi)有(key,value)：(字母,次數(shù))，散列表就添加(key,value)：(字母，次數(shù))，如果散列表中已經(jīng)有(key,value)：(字母，次數(shù))，就更新該(key,value)：(字母，次數(shù))，將其次數(shù)增加1。●每次讀取文件的一個(gè)單詞，如果散列表中還沒(méi)有(key,value)：(單詞，次數(shù))，散列表就添加(key,value)：(單詞，次數(shù))，如果散列表中已經(jīng)有(key,value)：(單詞，次數(shù))，就更新該(key,value)：(單詞，次數(shù))，將其次數(shù)增加1。2024/11/92510.6散列表與字符、單詞頻率例子5LettersFrequency.java例子5中的LettersFrequency類(lèi)負(fù)責(zé)統(tǒng)計(jì)文本文件中字符出現(xiàn)的次數(shù)和頻率，WordsFrequency負(fù)責(zé)統(tǒng)計(jì)文本文件中單詞出現(xiàn)的次數(shù)和頻率。WordsFrequency.javaExample10_5.java例子5中Example10_5.java中的主類(lèi)Example10_5使用LettersFrequency類(lèi)統(tǒng)計(jì)了Example10_5.java里字母出現(xiàn)的次數(shù)和頻率，另外一個(gè)主類(lèi)MainClass使用WordsFrequency統(tǒng)計(jì)了Example10_5.java里單詞出現(xiàn)的次數(shù)和頻率。10.7散列表與單件模式2024/11/926●單件模式

保證一個(gè)類(lèi)僅有一個(gè)實(shí)例，并提供一個(gè)訪問(wèn)它的全局訪問(wèn)點(diǎn)。散列表可以用來(lái)存儲(chǔ)已知的數(shù)據(jù)，在后續(xù)的操作中，通過(guò)散列表查找是否已經(jīng)存在，從而實(shí)現(xiàn)唯一性驗(yàn)證的功能。因此在實(shí)現(xiàn)的具體代碼中可以借助散列表來(lái)實(shí)現(xiàn)單件模式。2024/11/92710.7散列表與單件模式例子6SingletonSun.javaExample10_6.java例子6中的SingletonSun類(lèi)實(shí)現(xiàn)了單件模式，SingletonSun類(lèi)只能創(chuàng)建一個(gè)“太陽(yáng)”。在例子6中，SingletonSun類(lèi)中的getInstance()方法檢查散列表中是否已經(jīng)存在當(dāng)前類(lèi)的實(shí)例對(duì)象，如果不存在則創(chuàng)建一個(gè)新的，然后將其存儲(chǔ)到散列表中，并返回該實(shí)例。這樣就保證了SingletonSun類(lèi)在整個(gè)程序中只能創(chuàng)建它的一個(gè)對(duì)象。10.8散列表與數(shù)據(jù)緩存2024/11/928

2024/11/92910.8散列表與數(shù)據(jù)緩存例子7Hash.javaExample10_7.java例子7中的Hash類(lèi)將頻繁使用的階乘放在散列表中(用到第3章例子3中的SumMulti類(lèi))10.9TreeMap類(lèi)2024/11/93010.9TreeMap類(lèi)2024/11/931在類(lèi)的層次上，TreeMap<K,V>泛型類(lèi)HashMap<K,V>泛型類(lèi)不同，HashMap<K,V>泛型類(lèi)直接實(shí)現(xiàn)Map接口，TreeMap<K,V>泛型類(lèi)不是直接實(shí)現(xiàn)Map接口，而是實(shí)現(xiàn)NavigableMap接口，該接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如圖前圖。稱TreeMap<K,V>泛型類(lèi)的實(shí)例或創(chuàng)建的對(duì)象是一個(gè)映射樹(shù)。10.9TreeMap類(lèi)2024/11/932在存儲(chǔ)數(shù)據(jù)上，TreeMap<K,V>泛型類(lèi)和HashMap<K,V>泛型類(lèi)似，映射樹(shù)也是存儲(chǔ)"鍵-值"對(duì)，但映射樹(shù)不是散列結(jié)構(gòu)。映射樹(shù)也是使用兩個(gè)集合存儲(chǔ)對(duì)象，一個(gè)集合稱作關(guān)鍵字集合，記作Key。另一個(gè)是值的集合，記作Value。TreeMap<K,V>的Key集合也是實(shí)現(xiàn)Set接口的一個(gè)實(shí)例，映射樹(shù)中按著Key集合中的關(guān)鍵字的大小關(guān)系，將關(guān)鍵字key對(duì)應(yīng)的value，存放在一個(gè)紅黑樹(shù)（平衡二叉搜索樹(shù)，見(jiàn)第9章）上，即映射樹(shù)的Value是一棵紅黑樹(shù)，這也是TreeMap<K,V>類(lèi)名的來(lái)歷。10.9TreeMap類(lèi)2024/11/933

2024/11/93410.9TreeMap類(lèi)TreeMap中的Value是紅黑樹(shù)，是按著Key中的關(guān)鍵字的大小關(guān)系排序的，這就意味著Value紅黑樹(shù)上可以有相同的對(duì)象，即可以有兩個(gè)結(jié)點(diǎn)中的對(duì)象是相同的，甚至，所有結(jié)點(diǎn)中的對(duì)象都可以是相同的。

2024/11/93510.9TreeMap類(lèi)例子8Example10_8.java例子8中，主類(lèi)Example10_8使用了TreeMap的一些常用方法。2024/11/93610.9TreeMap類(lèi)例子9Example10_9.java例子9的主類(lèi)Example10_9獲取的映射樹(shù)的視圖，查詢了視圖中的”鍵-值”對(duì)，并對(duì)視圖進(jìn)行更新操作。2024/11/93710.9TreeMap類(lèi)