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

2024/11/9510.1散列結構的特點●散列結構與散列表對于一個關鍵字，比如key1，如果hash(key1)=98，那么key1關鍵字對應的節點就是數組hashValue第98個元素，即hashValue[98]。2024/11/9610.1散列結構的特點●散列結構與散列表一個散列函數，即hash()函數需保證下列兩點：①

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

（如果關鍵字沖突，使用了鏈接法）散列結構具有數組的優點，即非常快的查詢速度，同時又將查詢數據（Value）的索引分離到另一個獨立的集合中（Key）。數組最大的缺點就是將索引（下標）和數組元素綁定，因此，一旦創建數組，就無法更改索引，即無法再改變數組的長度。而散列結構可以隨時添加一個“鍵-值”對（一個關鍵字，一個相應的值），或刪除一個“鍵-值”對。10.2簡單的散列函數2024/11/99通過簡單的例子：停車場，進一步理解散列結構，后面我們將使用Java的HashMap類實現的散列結構。2024/11/91010.2簡單的散列函數●順序擴建停車位當Value中節點的數目越來越多時，比如達到總內存大小的一半時，就要重新調整內存，即分配新的數組，并把原數組hashValue[]的值復制到新的數組中，新的數組成為Value的新的一塊連續內存。汽車停車場（模擬散列表）初始狀態有10個連續的車位，相當于散列結構中分配給散列表Value的一塊連續的內存空間（數組的長度是10）。假設汽車的車牌號是3位數的正整數，相當于散列結構中的Key集合中節點里的關鍵字。停車場可以根據需要，隨時順序地擴大停車場，即連續地擴建停車位。

2024/11/91110.2簡單的散列函數●順序擴建停車位

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

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

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

2024/11/93410.9TreeMap類TreeMap中的Value是紅黑樹，是按著Key中的關鍵字的大小關系排序的，這就意味著Value紅黑樹上可以有相同的對象，即可以有兩個結點中的對象是相同的，甚至，所有結點中的對象都可以是相同的。

2024/11/93510.9TreeMap類例子8Example10_8.java例子8中，主類Example10_8使用了TreeMap的一些常用方法。2024/11/93610.9TreeMap類例子9Example10_9.java例子9的主類Example10_9獲取的映射樹的視圖，查詢了視圖中的”鍵-值”對，并對視圖進行更新操作。2024/11/93710.9TreeMap類例子10Example10_10.javaStudent.javaKeyStudent.java數映射中的Value，是按著Key中的關鍵字大小來排序的，那么，相對TreeSet（見第9章），使用映射樹對Value進行排序的方便之處就是，可以隨時更改Key中關鍵字的大小關系。例子10中的KeyStudent類實現了Comparable接口，給出了樹映射的Key的大小關系。例子10中的主類Example10_10使用映射樹分別按數學成績和英語成績排序學生.10.10Hashtable類2024/11/938Hashtable<K,V>泛型類也實現了Java集合框架中的Map接口。Hashtable<K,V>泛型類和HashMap<K,V>泛型類的主要區別是，Hashtable<K,V>泛型類提供的方法都是同步(synchronized)方法，即是線性安全的，而HashMap<K,V>泛型類不是線性安全的。2024/11/93910.10Hashtable類例子11Example10_11.javaTarget.java例子11中的主類Example10_11里的f()方法使用兩個線程訪問HashMap散列表，由于HashMap散列表不是線程安全的，一個線程遍歷HashMap散列表的過程中，另一個線程也可以遍歷HashMap散列表。例子11中另一個主類MainCalss里的f()方法使用兩個線程訪問Hashtable散列表，兩個線程各自遍歷Hashtable散列表，由于Hashtable散列表是線程安全的，一個線程遍歷Hashtable散列表的過程中，另一個線程無法遍歷Hashtable散列表。訪問線程不安全的散列表訪問線程安全的散列表第12章常用算法與Collections類2024/11/9402024/11/9412024/11/942Collections類是Object類的一個直接子類（注意Collections比Collection多了一個字母s），該類封裝了一系列算法，例如，二分查找，排序、洗牌等算法，這些算法可用于List，Queue、Set。需要注意的是Collections是類，Collection是接口，Collections類沒有實現Collection接口.12.1排序2024/11/943

2024/11/94412.1排序例子1Score.java例子1中的主類Example12_1使用Collections類的sort()方法排序（升序）一個鏈表，首先按鏈表中的對象實現的Comparable接口給出的比較器排序鏈表，然后再指定新的比較器排序鏈表。Example12_1.java12.2二分查找2024/11/945publicstaticintbinarySearch(List<?extendsT>list,Tkey)查找對象key是否在升序的list中（list中的對象按自然序排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開始），否則返回一個負數。publicstaticintbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)查找對象key是否在升序的list中（list的元素按比較器c排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開始），否則返回一個負數。注意，排序使用的比較器的算法需要和該方法使用的比較器c的算法相同。2024/11/94612.2二分查找例子2FindWords.java例子2中的FindWords類的booleanfindWords(Stringstr,Stringkey)方法使用二分法判斷單詞key是否在str中。Example12_2.java12.3反轉與旋轉2024/11/947publicstaticvoidreverse(List<?>list)反轉list中元素的順序.publicstaticvoidrotate(List<?>list,intdistance)把list向右(distance是正整數)或向左(distance是負整數)旋轉distance個索引位置。例如，list節點中的對象依次是[a,b,c,d,e]，如果執行Colections.rotate(list,1)，那么list節點中的對象依次是[e,a,b,c,d]，如果執行Colections.rotate(list,-2)，那么list節點中的對象依次是[cdeab]。2024/11/94812.3反轉與旋轉例子3LeaveOne.javaWordReverse.java例子3中的LeaveOne類的leaveByRotate(LinkedList<Integer>list)方法通過旋轉鏈表，解決約瑟夫問題：把list向左旋轉2個索引位置，即可確定出退出圈中的人，理由是，此刻鏈表頭節點就是數到的第3個人，即要出圈的人。例子3的WordRevers類的isReverse(Stringword)方法判斷word是否是回文單詞（回文單詞和它的反轉相同）。建議讀者把這里的例子3和第4章的例子9做一個比較，體會使用旋轉list解決約瑟夫問題，能讓代碼更加簡練。Example12_3.java12.4洗牌2024/11/949我們曾在第4章的4.10節，講解過洗牌算法，即Fisher-Yates洗牌算法。Collections類將Fisher-Yates洗牌算法封裝在下列方法中：publicstaticvoidshuffle(List<?>list)使用Fisher-Yates洗牌算法排列list。2024/11/95012.4洗牌例子4例子4的主類Example12_4使用Collectiones類提供的Fisher-Yates洗牌算法演示洗牌過程。Example12_4.java12.5最大與最小2024/11/951publicstaticTmax(Collection<?extendsT>coll)按coll元素的自然序（元素實現Comparable接口中的比較器給出的大小順序），返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll)按coll元素的自然序，返回coll中的最小值。publicstaticTmax(Collection<?extendsT>coll,Comparator<?superT>comp)

按comp比較器，返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll,,Comparator<?superT>comp)按comp比較器，返回coll中的最小值。2024/11/95212.5最大與最小例子5Example12_5.java例子5中的主類Example12_5求集合中的最大值和最小值。12.6頻率2024/11/953publicstaticintfrequency(Collection<?>c,Objectobj)返回c中與指定對象obj相等的元素的數量。我們曾在第10章的例子5中，使用散列表統計文本文件中單詞出現的次數和頻率。下面的例子6使用intfrequency(Collection<?>c,Objectobj)方法統計文本文件中單詞或漢字出現的次數和頻率。2024/11/95412.5最大與最小例子6Example12_6.java例子6中的FrequencyEnglish類將英文組成的文本文件中的單詞存放在一個集合中，便于統計出不相同的單詞的總數，把單詞存放在一個鏈表中，便于統計每個單詞出現的次數，并計算出單詞出現的頻率。FrequencyChinese類將中文組成的文本文件中的漢字存放在一個集合中，便于統計出不相同的漢字的總數，把漢字存放在一個鏈表中，便于統計每個漢字出現的次數，并計算出漢字出現的頻率。FrequencyEnglish.javaFrequencyChinese.java第13章圖論2024/11/9552024/11/956

13.1無向圖2024/11/957

⒈無向圖的定義2024/11/95813.1無向圖

⒈無向圖的定義2024/11/95913.1無向圖

2鄰接點

2024/11/96013.1無向圖3.路徑

2024/11/96113.1無向圖4.連通圖

13.2有向圖2024/11/962⒈有向圖的定義

2024/11/96313.2有向圖

⒈有向圖的定義

2024/11/96413.2有向圖2鄰接點

2024/11/96513.2無向圖3.路徑

2024/11/96613.2有向圖4.強連通圖

13.3網絡2024/11/967

2024/11/96813.3網絡刻畫北京，廣州，成都和上海四個城市之間的民航航線，航線之間的權重是航線距離。2024/11/96913.3網絡刻畫北京，廣州，成都和上海四個城市之間的民航航線，航線之間的權重是航線的票價（往返的票價不盡相同）。13.4圖的存儲2024/11/9701.鄰接矩陣

13.4圖的存儲2024/11/9711.鄰接矩陣

2024/11/97213.4圖的存儲例子1Example13_1.javaGraphByMatrix.java例子1中的GraphByMatrix類使用鄰接矩陣存儲圖或網絡的邊。例子1的主類Example13_1使用GraphByMatrix類演示了無向圖、有向圖和有向網絡使用鄰接矩陣存儲邊.13.4圖的存儲2024/11/9731.鄰接表

2024/11/97413.4圖的存儲例子2Example13_2.javaGraphByLinkedList.java例子2中的GraphByLinkedList類使用鄰接鏈表存儲圖或網絡的邊。例子2的主類Example13_2使用GraphByLinkedList類演示了無向圖、有向圖和有向網絡使用鄰接鏈表存儲邊.13.4圖的遍歷2024/11/975

13.4圖的遍歷2024/11/976廣度搜索（BFS）則是從起點開始，逐層訪問所有路徑可達到的頂點，一層一層地往外擴展（廣度優先），直到所有路徑可達到的頂點都被訪問到，就結束此次遍歷過程。如果圖中仍然有沒訪問過的頂點，就在沒訪問過的頂點中，選擇一個頂點重新開始遍歷。廣度優先搜索一直到圖中再也沒有可訪問的頂點，就結束搜索過程。廣度優先搜索的算法中可以用隊列（Deque）這種數據結構體現廣度優先.2024/11/97713.5圖的遍歷例子3Example13_3.javaGraphDFS.java1.深度優先搜索（DFS）算法DFS算法描述如下。①檢查是否已經訪問了全部的頂點，如果已經訪問了全部的頂點，進行③，否則，將一個不曾訪問的頂點壓入棧，進行②。②如果棧是空，進行①，否則進行彈棧，把彈出的頂點標記為訪問過的頂點，然后把彈出的頂點的鄰接頂點壓入棧（體現深度優先），但不再對訪問過的頂點進行壓棧操作，再進行②。③算法結束。例子3中的GraphDFS類封裝了DFS算法。Vertex.java2024/11/97813.5圖的遍歷例子4Example13_4.javaGraphBFS.java2.廣度優先搜索（BFS）算法例子4中的GraphBFS類封裝了BFS算法。Vertex.javaBFS算法描述如下：①檢查是否已經訪問了全部的頂點，如果已經訪問了全部的頂點，進行③，否則，將一個不曾訪問的頂點入列，進行②。②如果隊列是空，進行①，否則進行出列操作，把出列的頂點標記