ds7 dict數(shù)據(jù)結(jié)構(gòu)和算法Python語言版字典集合

7，字典和集合-息處理的基礎(chǔ)。數(shù)據(jù)需要和使用，因此需要檢索 具體情況，因此要考慮各種不同的字典實(shí)現(xiàn)技術(shù)更一般的問題是需要根據(jù)某些線索找出相關(guān)數(shù)據(jù)，可能需要做更復(fù)雜的匹配，或者“模糊”的匹配，基于內(nèi)容的匹配。例如網(wǎng)絡(luò)上的檢索。這些都是字典概念的發(fā)展動(dòng)態(tài)字典的插入刪除操作可能導(dǎo)致字典結(jié)構(gòu)的變化。要支持長期使用，還需要考慮字典在動(dòng)態(tài)變化中能否保持良好的結(jié)構(gòu)，能否保證良好的檢索效率？（字典的性能不應(yīng)該隨著反復(fù)操作而逐漸）ASL（AverageSearchLength），定義（n為字典的項(xiàng)數(shù)）：ASL=i

cipii的檢索長度和概率。如果各元素檢索概率相等，就有pi=1/n，ASL=1/n∑ci。還可能需要考慮找不到的情況 關(guān)聯(lián)(Association)是二元組class (self,key,value):self.key=keyself.value= (self,other):#有時(shí)（有些操作）returnself.key< (self,returnself.key<other.keyorself.key== (self):#return"Assoc({0},{1})".format(self.key,Assocx的值是關(guān)聯(lián)，x.key取得其關(guān)鍵碼，x.value取得其關(guān)聯(lián)值定義<和<=是因?yàn)橛袝r(shí)可能需要比較數(shù)據(jù)項(xiàng)，如使用sortedPythonlistAssoctuplelist檢索就是在用關(guān)鍵碼在表中查找（順序查找）。遇到關(guān)鍵碼key相appenddel實(shí)現(xiàn)，或者基于要?jiǎng)h除項(xiàng)的內(nèi)容，用remove操作實(shí)現(xiàn)list作為內(nèi)部表示，自己定義一個(gè)字典類，該類的對象就插入的元素放在最后，O(1)n

使之具有可利用的結(jié)構(gòu)，從而提高檢索的效率如果關(guān)鍵碼取自一個(gè)有序集（關(guān)鍵碼集合有某種序，例如整數(shù)的小于，字符串的字典序），就可以將字典了的項(xiàng)按關(guān)鍵碼排列（從小到大或從大到?。?。由于數(shù)據(jù)項(xiàng)排列有序，可以采用二分法實(shí)現(xiàn)快速檢索其基本過程是（假設(shè)元素按關(guān)鍵碼的升序排列）：2defbisearch(lst,key):low,high=0,len(lst)-1whilelow<=high:#mid=(low+high)//2ifkey==lst[mid].key:returnlst[mid].valueifkey<lst[mid].key:high=mid-1#low=mid+1O(n操作；刪除時(shí)可以用二分法檢索，但實(shí)際刪除后需要移動(dòng)數(shù)據(jù)項(xiàng)，所以也是O(n)操作115 012 5678951282036,9344數(shù)等于該結(jié)點(diǎn)的層數(shù)加1

檢索成功時(shí)所做比較次數(shù)不超過樹的深度。n個(gè)結(jié)點(diǎn)二分判定樹的高度不超過log2n。二分法檢索成功時(shí)的比較次數(shù)不超過log2n+1充二叉樹的外部結(jié)點(diǎn)）13-19的方框表示被檢索關(guān)鍵碼值在和之間。檢索到達(dá)方框就是失敗

由此可見，檢索不log2n+1這是基于檢索中的判定操作形成的判

平均檢索長度（設(shè)n=2j–j是搜索的“深度”

ASL

1

i

1

2m 2k- i1m如果元素個(gè)數(shù)n恰好 1

(2j2i120+21+…+2k-1=2k-則最大檢索長度為k；對于一2k-1n2k+1-1，最大檢

1(j2n1

j2i1所以，n元字典的二分法檢索 (j2j2jn最大檢索長度為log2(n

n1n

2(n1)優(yōu)點(diǎn)：檢索速度快，O(log插入刪除時(shí)需要數(shù)據(jù)項(xiàng)順序，O(n)操作（檢索插入或刪除的位置可以用二分法，O(logn)，但完成操作仍需要O(n)時(shí)間）操作；檢索和刪除需要順序掃描檢查，O(n)操作操作；檢索和刪除需要順序掃描檢查，平均查半個(gè)表，O(n)操作必須采用連續(xù)方式表示。如果數(shù)據(jù)集很大（M或者幾個(gè)G或更大的數(shù)據(jù)集），連續(xù)實(shí)現(xiàn)方式就很難接受了但是，一般而言，關(guān)鍵碼可能不是整數(shù)（不能作為下標(biāo)）如，學(xué)生學(xué)號有10位數(shù)字，取值范圍達(dá)到100億方法：選定一個(gè)整數(shù)下標(biāo)范圍（通常以0或1開始）建立續(xù)表；選定一個(gè)從關(guān)鍵碼集合到該下標(biāo)范圍的適當(dāng)?shù)挠成鋒keyh(key)keyh(key)h就稱為散列函數(shù)，又稱哈希（hash）函數(shù)或雜湊函數(shù)，是從可處理、、檢索工作中。例如：h把一個(gè)大集合的元素映射一個(gè)小集合里，顯然不可能是單射，必然key1≠ h(key1)＝此時(shí)就說出現(xiàn)（碰撞），也稱key1和key2為同義負(fù)載因子

關(guān)鍵碼和位置區(qū)間是事先確定的，作為散列函數(shù)的基礎(chǔ)集合（參數(shù)域和值域）。散列函數(shù)就是兩個(gè)有限集之間的函數(shù)，可以任意選擇，但其選擇可能影響出現(xiàn)的概率（很顯然）。最重要的考慮：基本考慮下，人們提出了許多設(shè)計(jì)散列函數(shù)的方法的關(guān)鍵碼和分布情況事先未知，上述分析方法就沒用了

m的整數(shù)p得到的余數(shù)（或者余數(shù)加1）作為散列地址m2pm的最大素?cái)?shù)（如果連續(xù)表的下標(biāo)從1開始，可以用keymodp+1）m128，256，512，1024時(shí)，p127，251，采用除余法法時(shí)，如果用偶數(shù)作為除數(shù)，就會(huì)出現(xiàn)偶數(shù)關(guān)鍵碼得到偶數(shù)散列值，奇數(shù)關(guān)鍵碼得到奇數(shù)散列值的情況如果關(guān)鍵碼集合的數(shù)字位數(shù)較多，可考慮采用較大的除數(shù)，然后去掉最低位（或去掉最低的一個(gè)或幾個(gè)二進(jìn)制位），排除最低位的規(guī)律性。還可以考慮其他方法，目標(biāo)是去掉規(guī)律性r的數(shù)，將其轉(zhuǎn)換為十進(jìn)制或二進(jìn)制數(shù)。通常r取一個(gè)素?cái)?shù)例，取r=13。對關(guān)鍵碼335647，可以計(jì)算出：(335647)13=3*135+3*1345*1336*132+4*137= 整數(shù)散列的方法。通常最后用除余法把關(guān)鍵碼歸入所需范圍字符的編碼），把一個(gè)字符串看作以某個(gè)整數(shù)為基數(shù)的“數(shù)”2931內(nèi)消解方法（在基本區(qū)內(nèi)解決元素外消解方法（在基本區(qū)之外解決元素已經(jīng)有關(guān)鍵碼不同的項(xiàng)，就知道出現(xiàn)了，必須處理Hi=(h(key)+di)modm為不超過表長的數(shù)，did0=h(key空閑就直接存入（d0）否則就逐個(gè)試探位置Hi，直至找到第一個(gè)空位時(shí)把數(shù)據(jù)項(xiàng)存入di=0,1,2,3,4h2dii*h2(key)例：設(shè)key為整數(shù)，取h(key)=keymod13。設(shè)有關(guān)鍵碼集合 ={18,73,10,5,68,99,22,32,46,58,25}h(key 8,10, 8, 6,12} 23456789 之間。其他探查法也可能出現(xiàn)這種情況，但可能稍好h(key)=keymod13；h2(key)=keymod5+0123456789在開地址法散列表上做檢索，工作過程與插入類似。對給定的key否則根據(jù)散列表的探查序列找到“下一地址”并回到步驟到對應(yīng)項(xiàng)后簡單地將其刪掉，有可能影響后面的檢索操作

外消解的 把所有關(guān)鍵碼 的數(shù)據(jù)項(xiàng)都保存在這個(gè)溢出表里采用了公共溢出區(qū)的散列表，散列表的負(fù)載因子有可能超過項(xiàng)的，可以發(fā)現(xiàn)很多可能的設(shè)計(jì)。最簡單的技術(shù)是“拉鏈法”h(keykeymod關(guān)鍵碼集合：{18,73,10,05,68,99,27,41,51,32,算出的位置：{ 8,10, 8, 6,把同一個(gè)散列值的數(shù)據(jù)項(xiàng)收集到一起：{{},{{27},{41},{68{05,18},{32},{},{99,73},{},{10},{},{25,51}

K={18,73,99,27,41,51,32,h(key)