第9章散列結(jié)構(gòu)2025/6/111散列結(jié)構(gòu)的特點(diǎn)；簡單的散列函數(shù)；創(chuàng)建字典；字典與字符、單詞的頻率；字典與數(shù)據(jù)緩存；OrderedDict類；對象作為關(guān)鍵字。

9.1散列結(jié)構(gòu)的特點(diǎn)2025/6/112生活中有些數(shù)據(jù)之間可能是密切相關(guān)的一對，例如，一副手套，一雙鞋子，一對夫妻等，即數(shù)據(jù)的邏輯結(jié)構(gòu)是成對的，即不是線性也不是樹形結(jié)構(gòu)，一對數(shù)據(jù)與另一對數(shù)據(jù)之間也無須有必然的關(guān)系。如何存儲這樣的數(shù)據(jù)對，也是數(shù)據(jù)結(jié)構(gòu)非常關(guān)心的，以下要介紹的散列結(jié)構(gòu)，就是存儲“數(shù)據(jù)對”的最重用的手段之一.2025/6/1139.1散列結(jié)構(gòu)的特點(diǎn)1散列結(jié)構(gòu)與散列表數(shù)據(jù)對，也稱作"鍵-值"對，鍵和值都是某種類的實(shí)例，即對象。敘述時可以把這"鍵-值"對記作(key,value)，稱key是關(guān)鍵字、value是鍵值或值。散列結(jié)構(gòu)使用兩個集合存儲對象，一個集合稱作關(guān)鍵字集合，記作Key。另一個是值的集合，記作Value。Key集合中的節(jié)點(diǎn)（或稱元素）負(fù)責(zé)存儲關(guān)鍵字，所有關(guān)鍵字對應(yīng)的全部值稱作散列結(jié)構(gòu)的值集合，記作Value，即Value中的節(jié)點(diǎn)負(fù)責(zé)存儲值。稱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)鍵字映射到散列表中一個位置，即映射到散列表中的某個節(jié)點(diǎn)。2025/6/1149.1散列結(jié)構(gòu)的特點(diǎn)1散列結(jié)構(gòu)與散列表hash()函數(shù)本質(zhì)上就是集合Key到整數(shù)集合

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

對于不同的關(guān)鍵字，比如，key1，key2是Key中兩個節(jié)點(diǎn)，即兩個關(guān)鍵字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是兩個不同的節(jié)點(diǎn)。但節(jié)點(diǎn)中的對象可能是相同的（數(shù)組的兩個不同的元素中的值可能是相同的）。②為了保證第①點(diǎn)，讓hash()函數(shù)映射出的全部節(jié)點(diǎn)，分散地分布在一塊連續(xù)的內(nèi)存中，這也是人們把Value稱作一個散列表的原因。由于散列表中的節(jié)點(diǎn)是隨機(jī)、分散分布的，所以我們不在散列表上定義任何關(guān)系（見第1章）。散列表或散列二字不是指數(shù)據(jù)之間的關(guān)系，而是形容存儲形式的特點(diǎn)（hash()函數(shù)映射存儲位置）。如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少沖突的可能性，以及在沖突不可避免時能給出解決的問題的算法。2025/6/1179.1散列結(jié)構(gòu)的特點(diǎn)1散列結(jié)構(gòu)與散列表如果出現(xiàn)hash(key1)和hash(key2)相同，就稱關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少沖突的可能性，以及在沖突不可避免時能給出解決的問題的算法。為了保證第（1）點(diǎn)和第（2）點(diǎn)，散列函數(shù)除了在算法要有全面的考慮外（本章不介紹繁雜的hash()函數(shù)算法，理解其作用即可），還需要通過裝載因子來保證第（1）點(diǎn)，裝載因子就是Value中節(jié)點(diǎn)的數(shù)目與給其分配給的是一塊連續(xù)的內(nèi)存的大小的比值，即Value中節(jié)點(diǎn)的數(shù)目和數(shù)組hashValue[]的長度的比值。裝載因子是0.75被公認(rèn)的比較好的數(shù)值，它是時間和空間成本之間的良好折中，因?yàn)榻o的內(nèi)存空間越大，越能保證第（1）點(diǎn)，但同時會使得hash()函數(shù)的映射速度慢一些。當(dāng)Value中節(jié)點(diǎn)的數(shù)目越來越多時，例如達(dá)到總內(nèi)存大小的一半時，就要重新調(diào)整內(nèi)存，即分配新的數(shù)組，并把原數(shù)組hashValue[]的值復(fù)制到新的數(shù)組中，新的數(shù)組成為Value的新的一塊連續(xù)內(nèi)存。2025/6/1189.1散列結(jié)構(gòu)的特點(diǎn)2查找、添加、刪除的特點(diǎn)由散列結(jié)構(gòu)的特點(diǎn)可以知道，使用關(guān)鍵字查找、刪除、添加Value中的節(jié)點(diǎn)，時間復(fù)雜度都是

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

2025/6/11119.2簡單的散列函數(shù)擴(kuò)建停車位

2025/6/11129.2簡單的散列函數(shù)擴(kuò)建停車位每當(dāng)一輛車來到停車場，如果用散列函數(shù)計算了若干次，得到的車位號對應(yīng)的車位上都是已經(jīng)停放了車輛，這個時候，就擴(kuò)建停車場、讓其容量增加2倍，然后再用散列函數(shù)計算車位號……，如此這般，只要內(nèi)存足夠大，總能找到停車位，如圖所示意。由于用散列函數(shù)的算法是隨機(jī)的，所以，某個時刻以后，擴(kuò)建停車場的概率就很小了。2025/6/11139.2簡單的散列函數(shù)例子1模擬散列結(jié)構(gòu)的停車場ch9_1.pych9_1.py中的ParkingSequential類使用順序辦法增加停車場的車位parking_chained.py中的ParkingChained類使用鏈?zhǔn)睫k法增加停車場的車位。9.3創(chuàng)建字典2025/6/1114字典是Python中的一種數(shù)據(jù)結(jié)構(gòu)、是內(nèi)置dict類的實(shí)例（對象），字典使用哈希表（HashTable）來實(shí)現(xiàn)，即是一種基于散列函數(shù)的數(shù)據(jù)結(jié)構(gòu)。字典的鍵通過散列函數(shù)計算得到一個哈希值，然后根據(jù)哈希值將鍵對應(yīng)的值對存儲在相應(yīng)的位置上。字典通過鍵即可快速地訪問到對應(yīng)的值，而不需要遍歷整個字典，即字典可用于存儲’鍵-值’對（見9.1節(jié)的散列結(jié)構(gòu)）。Python的字典通過散列函數(shù)和沖突解決技術(shù)實(shí)現(xiàn)了高效的鍵-值對存儲和查找，這使得字典成為Python中非常重要且高效的數(shù)據(jù)結(jié)構(gòu)之一。2025/6/11159.3創(chuàng)建字典1.創(chuàng)建空字典2.初始化字典3.用已有字典創(chuàng)建字典使用花括號{}來創(chuàng)建一個空字典。通過指定’鍵-值’對的方式來初始化字典。使用dict()構(gòu)造方法從已有的字典（’鍵-值’對的序列）創(chuàng)建字典。2025/6/11169.3創(chuàng)建字典4.字典對關(guān)鍵字類型的要求5.字典的基本操作Python默認(rèn)字典的關(guān)鍵字（鍵）必須是不可變的對象（特殊情況見9.5節(jié)），通常是字符串、數(shù)字或元組。這是因?yàn)樽值涫峭ㄟ^哈希表來實(shí)現(xiàn)的，需要保證鍵的不可變的性質(zhì)才能保證哈希的穩(wěn)定性。1.）獲取值：使用鍵來獲取對應(yīng)的值。2.）添加或修改鍵值對：直接添加新的’鍵-值’對，或修改已有的鍵的值。2025/6/11179.3創(chuàng)建字典5.字典的基本操作3.)刪除’鍵-值’對:使用del關(guān)鍵字或pop()方法。4.）獲取所有鍵或值：使用keys()、values()或items()方法。2025/6/11189.3創(chuàng)建字典6.遍歷字典使用關(guān)鍵字遍歷，輸出全部的值；直接輸出全部的值；輸出全部的關(guān)鍵字；輸出全部的鍵值對。2025/6/11199.3創(chuàng)建字典例子2ch9_2.pych9_2.py中首先創(chuàng)建一個空字典carMAp，然后向空字典carMap添加4個’鍵-值’對，再用carMap創(chuàng)建另一個字典mapNew。修改字典mapNew的’鍵-值’對，并不影響字典carMapr中的’鍵-值’對。創(chuàng)建字典并添加、刪除“鍵-值”對9.4字典與字符、單詞頻率2025/6/1120●每次讀取文件的一個字符，如果是字母，并且字典中還沒有(key,value)：(字母,次數(shù))，字典就添加(key,value)：(字母，次數(shù))，如果字典中已經(jīng)有(key,value)：(字母，次數(shù))，就更新該(key,value)：(字母，次數(shù))，將其次數(shù)增加1。●每次讀取文件的一個單詞，如果字典中還沒有(key,value)：(單詞，次數(shù))，字典就添加(key,value)：(單詞，次數(shù))，如果字典中已經(jīng)有(key,value)：(單詞，次數(shù))，就更新該(key,value)：(單詞，次數(shù))，將其次數(shù)增加1。2025/6/11219.4字典與字符、單詞頻率例子3ch9_3.pych9_3.py借助字典統(tǒng)計文本文件input.txt中字母和單詞出現(xiàn)的次數(shù)。統(tǒng)計字母、單詞出現(xiàn)的次數(shù)input.txt9.5

字典與數(shù)據(jù)緩存2025/6/1122

2025/6/11239.5字典與數(shù)據(jù)緩存例子4ch10_5.pych9_4.py將頻繁使用的階乘放在Hash類的字典中，并借助Hash類的字典計算一些組合.使用字典緩存數(shù)據(jù)9.6OrderedDict類2025/6/1124collections模塊中的OrderedDict類的實(shí)例也是存儲’鍵-值’對的數(shù)據(jù)結(jié)構(gòu)，稱OrderedDict類的實(shí)例為有序字典。字典和有序字典的區(qū)別是如下兩點(diǎn)：（1）字典（dict）：字典中的’鍵-值’對的順序是不固定的，因此，迭代字典時，鍵值對的順序是不確定的(不一定是添加鍵值對的順序)。（2）有序字典（OrderedDict）：有序字典會記住插入鍵值對的順序（這也是稱他為有序字典的緣由），并且在迭代時會按照插入順序返回鍵值對。這意味著，無論何時向有序字典中添加新的鍵值對，這個新的鍵值對都會被放置在有序字典的末尾。2025/6/11259.6OrderedDict類例子5有序字典ch9_5.pych9_5.py中使用了有序字典。注意：有序字典需要用鏈表記住順序，相對于字典有序字典會使用更多的內(nèi)存空間。9.7對象作為關(guān)鍵字2025/6/1126默認(rèn)情況下，字典的關(guān)鍵字（鍵）必須是不可變的對象，通常是整數(shù)、浮點(diǎn)數(shù)、字符串、元組等（列表不可以作為關(guān)鍵字）。如果需要用對象作為字典的關(guān)鍵字，那么創(chuàng)建對象的類需要重載哈希函數(shù)（hash()）。重載