[高等教育]數(shù)據(jù)結(jié)構(gòu)第9章查找(參考版)
2025-01-22 18:43本頁面
【正文】 。 ? 搜索成功的平均搜索長(zhǎng)度 是指 搜索到表中已有記錄的平均探查次數(shù) 。 ? 用 平均搜索長(zhǎng)度 ASL (Averagy Search Length)衡量散列方法的搜索性能。 0 1 2 3 4 5 6 7 8 9 10 60 17 29 38 (1) (1) (1) (4) ? 當(dāng)發(fā)生沖突時(shí) , 探查下一個(gè)關(guān)鍵字。 ? 舉例，采用線性探測(cè)再散列的方法處理時(shí)，結(jié)果如下圖所示。 ? 又有一組關(guān)鍵字為 17， 60， 29， 38。 k2 (3) 偽隨機(jī)探測(cè)再散列 : di = 偽隨機(jī)數(shù)序列 舉例 ? 假設(shè)哈希表的長(zhǎng)度為 11，即 n=11,哈希函數(shù)H(key)=key MOD 11， 則哈希地址集合為 0 ～ 10，此時(shí)的哈希表為空，如下圖所示。 通常用的處理沖突的方法 ? 開放定址法 – (1) 線性探測(cè)再散列 – (2) 二次探測(cè)再散列 – (3) 偽隨機(jī)探測(cè)再散列 ? 再哈希法 ? 鏈地址法 ? 建立一個(gè)公共溢出區(qū) ? ” 空 “ 的哈希地址 Hi的計(jì)算公式為： Hi = (H(key)+di) MOD n i=1,2,…,k(k ≤n1) (925) 其中， H(key)是哈希函數(shù)， n為哈希表的長(zhǎng)度。 – 在處理沖突過程中，可能得到一個(gè)地址序列 Hi，i=1,2,… ,k, Hi∈ [0,n1]。 – 若設(shè)散列表地址集合為 0 到 n1，當(dāng)要 加入 一個(gè)記錄 R2時(shí) , 用它的關(guān)鍵字 ，通過散列函數(shù) H( ) 的計(jì)算，得到它的哈希地址 j(0 ≤ j ≤ n1)，但是發(fā)現(xiàn)這個(gè)位置上已經(jīng)被另一個(gè)記錄 R1 占據(jù)了。 ? 處理沖突的基本思想： – 所有的記錄都直接放在散列表數(shù)組中。 – 需要注意的是，使用上面的散列函數(shù)計(jì)算出來的地址范圍是 0到 22（不到 24，因?yàn)槌龜?shù) p=23），因此， 從 23到 24只可能在處理溢出時(shí)達(dá)到這些地址 。 – 取質(zhì)數(shù) p= 23（不大于 25的質(zhì)數(shù)），散列函數(shù) hash ( key ) = key % p。 ? 質(zhì)數(shù)和合數(shù) ：只有 1和它本身兩個(gè)約數(shù)的數(shù)，叫質(zhì)數(shù)；除了 1和它本身兩個(gè)約數(shù)外，還有其它約數(shù)的數(shù)，叫合數(shù) 。 散列函數(shù)為 H (key) = key 940000 則有 H (942148) = 2148 H (941269) = 1269 H (940527) = 527 H (941630) = 1630 H (941805) = 1805 H (941558) = 1558 H (942047) = 2047 H (940001) = 1 ? ? 設(shè)散列表中允許的地址數(shù)為 n。 哈希函數(shù)的構(gòu)造方法 ? 此類函數(shù)取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址： H ( key ) ＝ a * key + b { a, b為常數(shù) } 由于這類散列函數(shù)是一對(duì)一的映射，而且散列地址集合的大小與關(guān)鍵字集合的大小相同，因此一般不會(huì)產(chǎn)生沖突，但是實(shí)際應(yīng)用很少。 ? 關(guān)鍵字經(jīng)過 哈希 函數(shù)計(jì)算出來的 “ 隨機(jī)地址 ”應(yīng)能均勻分布在整個(gè)地址空間中：若 key 是從關(guān)鍵字集合中隨機(jī)抽取的一個(gè)關(guān)鍵字， 哈希 函數(shù)應(yīng)能以同等概率 取 0 到 n1 中的每一個(gè)值。 我們稱這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵字為 同義詞 。 則有： hash(12361) = hash(07251) = hash(03309) = hash(30976) = 13444。 因此有可能經(jīng)過散列函數(shù)的計(jì)算 ， 把不同的關(guān)鍵字映射到同一個(gè)散列地址上 ， 這就產(chǎn)生了 沖突 (Collision)。 ? 散列函數(shù)是一個(gè)壓縮映象函數(shù) 。 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1