第9章二叉樹與TreeSet類2024/11/919.1二叉樹的基本概念2024/11/92一棵樹上的每個(gè)結(jié)點(diǎn)至多有2個(gè)子結(jié)節(jié)點(diǎn)，稱這樣的樹是二叉樹。沒有任何結(jié)點(diǎn)的二叉樹被稱為空二叉樹。一個(gè)結(jié)點(diǎn)如果有2個(gè)子結(jié)點(diǎn)，那么把一個(gè)稱為左子結(jié)點(diǎn)，把另一個(gè)稱為右子結(jié)點(diǎn)，如果只有1個(gè)子結(jié)點(diǎn)，那么這個(gè)子結(jié)點(diǎn)也要分為是左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)。2024/11/939.1二叉樹的基本概念●左子樹與右子樹一個(gè)結(jié)點(diǎn)和它的左、右子結(jié)點(diǎn)是父子關(guān)系。一個(gè)結(jié)點(diǎn)的左、右子結(jié)點(diǎn)是兄弟關(guān)系，二者互稱為兄弟結(jié)點(diǎn)，即有相同父結(jié)點(diǎn)的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)。●父子關(guān)系與兄弟關(guān)系把二叉樹的一個(gè)結(jié)點(diǎn)的左子節(jié)點(diǎn)看作一個(gè)樹的根節(jié)點(diǎn)的話，那么以左子節(jié)點(diǎn)為根的樹也是一個(gè)二叉樹，稱作該節(jié)點(diǎn)的左子樹（如果沒有左子結(jié)點(diǎn)，左子樹是空樹），同樣把此結(jié)點(diǎn)右子節(jié)點(diǎn)看作一個(gè)樹的根節(jié)點(diǎn)的話，以右子節(jié)點(diǎn)為根的樹也是一個(gè)二叉樹（如果沒有右子結(jié)點(diǎn)，右子樹是空樹）。一個(gè)樹，就是由根結(jié)點(diǎn)和它的左子樹和右子樹所構(gòu)成。2024/11/949.1二叉樹的基本概念●樹的層

樹用倒置的樹形來表示，結(jié)點(diǎn)按層從上向下排列，根結(jié)點(diǎn)是第0層。二叉樹從也是從根開始定義，根為第0層，根的子結(jié)點(diǎn)為第1層，以此類推。除了第0層，每一層上的結(jié)點(diǎn)和上一層中的一個(gè)結(jié)點(diǎn)有關(guān)系，但可能和下一層的至多2結(jié)點(diǎn)有關(guān)系。即根結(jié)點(diǎn)沒有父節(jié)點(diǎn)，其它結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但至多有2個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)沒有子結(jié)點(diǎn)。2024/11/959.1二叉樹的基本概念●滿二叉樹（FullBinaryTree）每個(gè)非葉結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的是滿二叉樹?！裢昝蓝鏄?PerfectBinaryTree)

2024/11/969.1二叉樹的基本概念●完全二叉樹(CompleteBinaryTree)完全二叉樹從根結(jié)點(diǎn)到倒數(shù)第二層的結(jié)點(diǎn)數(shù)目都是滿的，最后一層可以不滿，但最后一層葉子結(jié)點(diǎn)都是靠左對齊（按最后一層從左向右的序號(hào)，一個(gè)挨著一個(gè)靠左對齊），并且從左向右數(shù)，只允許最后一個(gè)葉子結(jié)點(diǎn)可以沒有兄弟結(jié)點(diǎn)，而且如果最后一個(gè)葉子結(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)的話，它必須是左子結(jié)點(diǎn)。2024/11/979.1二叉樹的基本概念●樹的高度與深度一個(gè)葉結(jié)點(diǎn)所在的層的層數(shù)加1（層是從0開始的，只有一個(gè)根結(jié)點(diǎn)的二叉樹高度為1，規(guī)定空二叉樹的高度是0），稱作這個(gè)葉節(jié)點(diǎn)的高度，所有葉節(jié)點(diǎn)中，其高度最大者稱為二叉樹的高度.從根結(jié)點(diǎn)（包括根結(jié)點(diǎn)）按照父子關(guān)系找到一個(gè)葉結(jié)點(diǎn)所經(jīng)歷過的結(jié)點(diǎn)（包括葉結(jié)點(diǎn)）數(shù)目，稱作這個(gè)葉結(jié)點(diǎn)的深度。所有葉節(jié)點(diǎn)中，其深度最大者的深度稱為樹的深度。不難得知，樹的深度和高度是相等的，只是敘述的方式不同而已。

9.2遍歷二叉樹2024/11/98遍歷二叉樹有三種常見的方式，分別是前序遍歷，中序遍歷和后序遍歷。2024/11/999.2遍歷二叉樹●前序遍歷

publicvoidpreOrder(Nodep){//前序遍歷if(p!=null){p.visited();//輸出ppreOrder(p.left);//遞歸遍歷左子樹preOrder(p.right);//遞歸遍歷右子樹}}ABDFECG2024/11/9109.2遍歷二叉樹●中序遍歷

publicvoidinOrder(Nodep){//中序遍歷if(p!=null){inOrder(p.left);p.visited();inOrder(p.right);}}FDBEACG2024/11/9119.2遍歷二叉樹●后序遍歷FDBECGA

publicvoidpostOrder(Nodep){//后序遍歷if(p!=null){postOrder(p.left);postOrder(p.right);p.visited();}}9.3二叉樹的存儲(chǔ)2024/11/912二叉樹的結(jié)點(diǎn)的存儲(chǔ)方式通常為鏈?zhǔn)酱鎯?chǔ)，即一個(gè)結(jié)點(diǎn)中含有一個(gè)對象，以及左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的引用。對于一個(gè)沒有增加限制的二叉樹，給出通用的添加、刪除結(jié)點(diǎn)的算法是不可能的，理由是在鏈?zhǔn)酱鎯?chǔ)的二叉樹中，要確定一個(gè)結(jié)點(diǎn)的位置，需要知道它的父結(jié)點(diǎn)和它在父結(jié)點(diǎn)的位置（是左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)）。因此，在進(jìn)行添加或刪除操作時(shí)，需要先找到要添加或刪除的結(jié)點(diǎn)的位置，而這個(gè)過程會(huì)涉及到一系列的判斷和遍歷操作，因而比較復(fù)雜。不同的二叉樹可能有不同的限制條件，因此沒有通用的算法適用于所有的情況。但是，對于二叉查詢樹，人么就可以給出有關(guān)的算法，見稍后的9.5節(jié)。2024/11/9139.3二叉樹的存儲(chǔ)Node.java例子1例子1中的BinaryTree類負(fù)責(zé)創(chuàng)建的二叉樹，其結(jié)點(diǎn)Node是鏈?zhǔn)酱鎯?chǔ)的。Example9_1.javaBinaryTree.java例子1的主類，使用BinaryTree類創(chuàng)建二叉樹，并分別使用前序、中序和后序遍歷了這棵二叉樹，同時(shí)查詢了某個(gè)對象是否和樹上的某個(gè)結(jié)點(diǎn)中的對象相同.9.4平衡二叉樹2024/11/914平衡二叉樹：①左子樹和右子樹深度之差的絕對值不大于1，②左子樹和右子樹也都是平衡二叉樹。

9.5二叉查詢樹2024/11/915籠統(tǒng)的二叉樹很難能形成有效算法，所以本節(jié)先給出二叉查詢樹，然后介紹兩種經(jīng)典的平衡二叉查詢樹。2024/11/9169.5二叉查詢樹●二叉查詢樹二叉查詢樹（BinarySearchTree，簡稱BST）的每個(gè)結(jié)點(diǎn)node都存儲(chǔ)一個(gè)可比較大小的對象，且滿足以下條件①node的左子樹中所有結(jié)點(diǎn)中的對象都小于node結(jié)點(diǎn)中的對象；②node的右子樹中所有結(jié)點(diǎn)的對象都大于等于node節(jié)點(diǎn)的中的對象；③左、右子樹都是二叉查詢樹。如果按中序遍歷二叉查詢樹，輸出的對象剛好是升序排列。所以也稱二叉查詢樹是有序二叉樹。按中序遍歷輸出了樹上的結(jié)點(diǎn)中的數(shù)據(jù)：ABCDEFG2024/11/9179.5二叉查詢樹●二叉查詢樹二叉查詢樹的任意結(jié)點(diǎn)中的對象大于左子結(jié)點(diǎn)中的對象，小于等于右子結(jié)點(diǎn)中的對象。但是，如果一個(gè)二叉樹的任意結(jié)點(diǎn)中的對象大于左子結(jié)點(diǎn)中的對象，小于等于右子結(jié)點(diǎn)中的對象，它不一定是二叉查詢樹.2024/11/9189.5二叉查詢樹Node.java例子2Example9_1.javaBinaryTree.java例子2中的主類使用例子1的BinaryTree類負(fù)責(zé)創(chuàng)建了二叉樹查詢樹，并按中序遍歷輸出了樹上的結(jié)點(diǎn)中的數(shù)據(jù)。2024/11/9199.5二叉查詢樹●平衡二叉查詢樹

平衡二叉查詢樹的查找操作非常類似二分法，由于是平衡二叉查詢樹，查詢過程中，結(jié)點(diǎn)的數(shù)目近似以2的方冪在減少，所以它的查詢時(shí)間復(fù)雜度和二分法的查詢時(shí)間復(fù)雜度相同.2024/11/9209.5二叉查詢樹Node.java例子3Example9_3.javaBinaryBST.java

平衡二叉查詢樹129231056191722282024/11/9219.5二叉查詢樹●紅黑樹紅黑樹是一種平衡的二叉搜索樹。它的平衡性質(zhì)的維護(hù)主要是通過顏色標(biāo)記節(jié)點(diǎn)等操作來達(dá)成。

Java實(shí)現(xiàn)的二叉搜索樹是紅黑樹（見稍后的TreeSet類），講解紅黑樹，內(nèi)部算法細(xì)節(jié)超出了本書的范圍。2024/11/9229.5二叉查詢樹●AVL樹AVL樹是根據(jù)兩位發(fā)明者Adel’son-Velskii和Landis命名的一種平衡二叉搜索樹。

Java實(shí)現(xiàn)的二叉搜索樹是紅黑樹（見稍后的TreeSet類），講解紅黑樹，以及AVL樹的內(nèi)部算法細(xì)節(jié)超出了本書的范圍。9.5TreeSet樹集2024/11/923TreeSet<E>泛型類實(shí)現(xiàn)了SortedSet接口。2024/11/9249.6TreeSet樹集創(chuàng)建一個(gè)TreeSet<E>類的對象必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等）即指定樹集的結(jié)點(diǎn)里的對象的類型。例如，指定E是Integer：TreeSet<Integer>treeOne=newTreeSet<>();或TreeSet<Integer>treeOne=newTreeSet<Integer>();TreeSet類不允許有兩個(gè)結(jié)點(diǎn)的對象相同，即大小一樣的對象。

樹集使用add(Eobj)方法向樹集添加結(jié)點(diǎn)。樹集使用addAll(Collection<?extendsE>c)方法添加多個(gè)結(jié)點(diǎn)到樹集，結(jié)點(diǎn)中的對象可以是參數(shù)指定的集合中的結(jié)點(diǎn)中的對象。2024/11/9259.6TreeSet樹集例子4Example9_4.java例子4中的主類Example9_4中首先創(chuàng)建一個(gè)空樹集treeOne，然后向空樹集treeOne添加4個(gè)節(jié)點(diǎn)，隨后再用treeOne創(chuàng)建樹集treeTwo。用新的大小關(guān)系創(chuàng)建treeTree，然后向treeTree添加結(jié)點(diǎn)，結(jié)點(diǎn)中的對象和treeOne的相同。9.6樹集的基本操作2024/11/926publicEfirst()返回樹集上節(jié)點(diǎn)值最小的節(jié)點(diǎn)中的對象。publicElast()返回樹集上節(jié)點(diǎn)值最大的節(jié)點(diǎn)中的對象。publicbooeleanadd(Eobj)樹集使用該方法向其添加結(jié)點(diǎn)，但需要注意的是，如果樹集上已經(jīng)有節(jié)點(diǎn)值是obj將無法將值是ob的結(jié)點(diǎn)添加到樹集上，此時(shí)返回false表示添加失敗。publicbooleanaddAll(Collection<?extendsE>c)樹集使用該方法向其添加多個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)值可以是參數(shù)指定的集合中的結(jié)點(diǎn)中的對象，即c可以是鏈表，棧，隊(duì)列或另一個(gè)樹集。但需要注意的是，c中如果有相同的對象，只能有一個(gè)被添加到樹集上。2024/11/9279.7樹集的基本操作例子5RandomByTree.java

Example9_5.java雙色球的每注投注號(hào)碼由6個(gè)紅色球號(hào)碼和1個(gè)藍(lán)色球號(hào)碼組成。6個(gè)紅色球的號(hào)碼互不相同、號(hào)碼是1至33的隨機(jī)數(shù)；藍(lán)色球號(hào)碼是1至16的一個(gè)隨機(jī)數(shù)。例子5中的主類Exmple9_5使用RandomByTree類的getRandom(intnumber,intn)方法模擬雙色球。2024/11/9289.7樹集的基本操作例子6ConnectNumber.javaExample9_6.java

例子6的ConnectNumber類的intgetMaxConnectNumber(int…m)方法返回幾個(gè)正整數(shù)最大的連接數(shù)，intgetMaxConnectNumber(int…m)返回幾個(gè)正整數(shù)的最小連接數(shù)。9.8樹集的視圖2024/11/929樹集是有序集，因此，樹集的視圖也是有序集，規(guī)定視圖在添加結(jié)點(diǎn)時(shí)，不可以添加大于視圖中最大值的結(jié)點(diǎn)，也不可以添加小于視圖中最小值的結(jié)點(diǎn)，即對于視圖subView，subView添加的結(jié)點(diǎn)的節(jié)點(diǎn)值不能大于sunView.last()的結(jié)點(diǎn)值，不能小于subView.first()的結(jié)點(diǎn)值。publicSortedSet<E>subSet(Efrom,Eto)返回樹集的一個(gè)視圖，視圖中的結(jié)點(diǎn)由樹集上結(jié)點(diǎn)值大于等于from結(jié)點(diǎn)值、小于to結(jié)點(diǎn)值的結(jié)點(diǎn)所構(gòu)成。如果from結(jié)點(diǎn)值等于to結(jié)點(diǎn)值，方法返回null，如果from結(jié)點(diǎn)值小于to結(jié)點(diǎn)值，會(huì)觸發(fā)運(yùn)行異常：IllegalArgumentException。2024/11/9309.8樹集的視圖例子7Example9_7.java例子7的主類Example9_7獲取的樹集的視圖，查詢了視圖中的結(jié)點(diǎn)，并對視圖進(jìn)行了添加和刪除結(jié)點(diǎn)的操作.樹集的視圖是樹集的一個(gè)子集，更改視圖的結(jié)點(diǎn)（增加或刪除節(jié)點(diǎn)）都會(huì)使得當(dāng)前樹集發(fā)生同步的改變，同樣地，如果更改樹集的結(jié)點(diǎn)（增加或刪除節(jié)點(diǎn)），就也會(huì)使得視圖發(fā)生同步的相應(yīng)的改變，即樹集的視圖和原樹集會(huì)同步變化，這也是視圖的本意。9.9樹集與數(shù)據(jù)統(tǒng)計(jì)2024/11/931

2024/11/9329.9樹集與數(shù)據(jù)統(tǒng)計(jì)例子8Example9_8.java例子8中的主類Example9_8對統(tǒng)計(jì)了隨機(jī)數(shù).9.10樹集與過濾數(shù)據(jù)2024/11/933第4章的4.3曾講過過濾數(shù)組，即去除數(shù)組中的某些數(shù)據(jù)。使用樹集來過濾數(shù)據(jù)會(huì)更加方便，而且能發(fā)揮樹集，在刪除、查詢方面的速度優(yōu)勢。經(jīng)常使用下列方法來過濾數(shù)據(jù)。publicbooleanremoveAll(Collection<?>c)刪除節(jié)點(diǎn)值在c里的結(jié)點(diǎn)publicbooleanretainAll(Collection<?>c)保留節(jié)點(diǎn)值在c里的結(jié)點(diǎn)publicbooleanremoveIf(Predicate<?superE>filter)刪除滿足filter給出的條件的結(jié)點(diǎn)。2024/11/9349.10樹集與過濾數(shù)據(jù)例子9Example9_9.java例子9中的主類Example9_9的樹集使用樹集提供的方法實(shí)現(xiàn)過濾數(shù)據(jù)。2024/11/9359.10樹集與過濾數(shù)據(jù)例子10HandleRecurring.java例子10中的HandleRecurring類的handleRecurring(int[]arr)方法處理數(shù)組arr中重復(fù)的數(shù)據(jù)，該方法返回的數(shù)組中的數(shù)據(jù)是arr中去掉重復(fù)數(shù)據(jù)后的數(shù)據(jù)（重復(fù)的數(shù)據(jù)只保留一個(gè)）。學(xué)習(xí)例子10時(shí)，注意這樣的知識(shí)點(diǎn)：如果想動(dòng)態(tài)更改結(jié)點(diǎn)的大小關(guān)系，就需要使用TreeSet(Comparator<?superE>comparator)構(gòu)造方法創(chuàng)建一個(gè)新的樹集newTree，該樹集上結(jié)點(diǎn)中的對象使用新的大小關(guān)系比較大小，然后newTree.addAll(tree)把原樹集tree上的結(jié)點(diǎn)中的對象添加到新樹集newTree上的結(jié)點(diǎn)中。Example9_10.java2024/11/9369.11樹集與節(jié)目單例子11ProgramList.javaExample9_11.java編輯一場舞臺(tái)演出節(jié)目單，最糟糕的是把兩個(gè)不同的節(jié)目安排在了相同的演出時(shí)間、引起麻煩。如果使用樹集來存放節(jié)目單中的節(jié)目，就會(huì)避免這樣的麻煩事情發(fā)生，理由是，節(jié)目單里的節(jié)目按演出時(shí)間比較大小，樹集能保證樹集上不能有大小相同的兩個(gè)對象。例子11中的ProgramList類按時(shí)間比較其實(shí)例的大小。例子11的主類Example9_11將節(jié)目單的節(jié)目存放在樹集上，然后輸出樹集上的節(jié)目.第10章散列表與HashMap類2024/11/93710.1散列結(jié)構(gòu)的特點(diǎn)2024/11/938生活中有些數(shù)據(jù)之間可能是密切相關(guān)的一對，例如，一副手套，一雙鞋子，一對夫妻等，即數(shù)據(jù)的邏輯結(jié)構(gòu)是成對的，即不是線性也不是樹形結(jié)構(gòu)，一對數(shù)據(jù)與另一對數(shù)據(jù)之間也無須有必然的關(guān)系。如何存儲(chǔ)這樣的數(shù)據(jù)對，也是數(shù)據(jù)結(jié)構(gòu)非常關(guān)心的，以下要介紹的散列結(jié)構(gòu)，就是存儲(chǔ)“數(shù)據(jù)對”的最重用的手段之一.2024/11/93910.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表數(shù)據(jù)對，也稱作"鍵-值"對，鍵和值都是某種類的實(shí)例，即對象。敘述時(shí)可以把這"鍵-值"對記作(key,value)，稱key是關(guān)鍵字、value是鍵值或值。散列結(jié)構(gòu)使用兩個(gè)集合存儲(chǔ)對象，一個(gè)集合稱作關(guān)鍵字集合，記作Key。另一個(gè)是值的集合，記作Value。Key集合中的節(jié)點(diǎn)（或稱元素）負(fù)責(zé)存儲(chǔ)關(guān)鍵字，所有關(guān)鍵字對應(yīng)的全部值稱作散列結(jié)構(gòu)的值集合，記作Value，即Value中的節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)值。稱Value為散列結(jié)構(gòu)中的散列表（hash表，也常常被音譯稱作哈希表）。簡單說，散列結(jié)構(gòu)是根據(jù)關(guān)鍵字直接進(jìn)行訪問數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，其核心思想是使用散列函數(shù)（hash()函數(shù)）把關(guān)鍵字映射到散列表中一個(gè)位置，即映射到散列表中的某個(gè)節(jié)點(diǎn)。2024/11/94010.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表hash()函數(shù)本質(zhì)上就是集合Key到整數(shù)集合

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

對于不同的關(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)中的對象可能是相同的（數(shù)組的兩個(gè)不同的元素中的值可能是相同的）。②為了保證第①點(diǎn)，讓hash()函數(shù)映射出的全部節(jié)點(diǎn)，分散地分布在一塊連續(xù)的內(nèi)存中，這也是人們把Value稱作一個(gè)散列表的原因。由于散列表中的節(jié)點(diǎn)是隨機(jī)、分散分布的，所以我們不在散列表上定義任何關(guān)系（見第1章）。散列表或散列二字不是指數(shù)據(jù)之間的關(guān)系，而是形容存儲(chǔ)形式的特點(diǎn)（hash()函數(shù)映射存儲(chǔ)位置）。如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問題的算法。2024/11/94310.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問題的算法。可以用鏈接法解決沖突，散列函數(shù)把和關(guān)鍵字key有相同對應(yīng)的值的那些關(guān)鍵字所對應(yīng)的存儲(chǔ)位置依次設(shè)置為一個(gè)鏈表的中不同的節(jié)點(diǎn)（鏈表頭節(jié)點(diǎn)是key對應(yīng)的存儲(chǔ)位置），這樣一來，就會(huì)增大查詢Value中值的時(shí)間復(fù)雜度。如果散列函數(shù)設(shè)計(jì)的合理，那么一般不會(huì)發(fā)生關(guān)鍵字沖突或發(fā)生關(guān)鍵字沖突的概率非常小，因此也就不需要使用鏈?zhǔn)椒椒ń鉀Q沖突或使用鏈?zhǔn)椒椒ń鉀Q沖突的概率很小。鏈接法是最后保證不同關(guān)鍵字對應(yīng)的不同節(jié)點(diǎn)（不同的存儲(chǔ)位置）的最后辦法。2024/11/94410.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)，即非?？斓牟樵兯俣龋瑫r(shí)又將查詢數(shù)據(jù)（Value）的索引分離到另一個(gè)獨(dú)立的集合中（Key）。數(shù)組最大的缺點(diǎn)就是將索引（下標(biāo)）和數(shù)組元素綁定，因此，一旦創(chuàng)建數(shù)組，就無法更改索引，即無法再改變數(shù)組的長度。而散列結(jié)構(gòu)可以隨時(shí)添加一個(gè)“鍵-值”對（一個(gè)關(guān)鍵字，一個(gè)相應(yīng)的值），或刪除一個(gè)“鍵-值”對。10.2簡單的散列函數(shù)2024/11/945通過簡單的例子：停車場，進(jìn)一步理解散列結(jié)構(gòu)，后面我們將使用Java的HashMap類實(shí)現(xiàn)的散列結(jié)構(gòu)。2024/11/94610.2簡單的散列函數(shù)●順序擴(kuò)建停車位當(dāng)Value中節(jié)點(diǎn)的數(shù)目越來越多時(shí)，比如達(dá)到總內(nèi)存大小的一半時(shí)，就要重新調(diào)整內(nèi)存，即分配新的數(shù)組，并把原數(shù)組hashValue[]的值復(fù)制到新的數(shù)組中，新的數(shù)組成為Value的新的一塊連續(xù)內(nèi)存。汽車停車場（模擬散列表）初始狀態(tài)有10個(gè)連續(xù)的車位，相當(dāng)于散列結(jié)構(gòu)中分配給散列表Value的一塊連續(xù)的內(nèi)存空間（數(shù)組的長度是10）。假設(shè)汽車的車牌號(hào)是3位數(shù)的正整數(shù)，相當(dāng)于散列結(jié)構(gòu)中的Key集合中節(jié)點(diǎn)里的關(guān)鍵字。停車場可以根據(jù)需要，隨時(shí)順序地?cái)U(kuò)大停車場，即連續(xù)地?cái)U(kuò)建停車位。

2024/11/94710.2簡單的散列函數(shù)●順序擴(kuò)建停車位

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

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

2024/11/96510.8散列表與數(shù)據(jù)緩存例子7Hash.javaExample10_7.java例子7中的Hash類將頻繁使用的階乘放在散列表中(用到第3章例子3中的SumMulti類)10.9TreeMap類2024/11/96610.9TreeMap類2024/11/967在類的層次上，TreeMap<K,V>泛型類HashMap<K,V>泛型類不同，HashMap<K,V>泛型類直接實(shí)現(xiàn)Map接口，TreeMap<K,V>泛型類不是直接實(shí)現(xiàn)Map接口，而是實(shí)現(xiàn)NavigableMap接口，該接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如圖前圖。稱TreeMap<K,V>泛型類的實(shí)例或創(chuàng)建的對象是一個(gè)映射樹。10.9TreeMap類2024/11/968在存