淺談hashppt課件-展示頁
2025-05-08 03:10本頁面
【正文】 000919697 997 000310329 329 分析： 關(guān)鍵碼是 9 位的，地址是 3 位的，需要經(jīng)過數(shù)字分析丟掉 6 位。 本方法適用于所有關(guān)鍵字已知，并對關(guān)鍵字中每一位的取值分布情況作出了分析。而素數(shù)的約數(shù)是最少的，因此我們選用大素數(shù)。也就是說余數(shù)的分布變得 不均勻了。因此上式的值就只有 b+1 種可能了。 其中， [b div a]的取值范圍是不會超過 [0， b]的正整數(shù)。一般地說，如果 m 的約數(shù)越 多，那么沖突的幾率就越大。 除余法 選擇一個適當?shù)恼麛?shù) m，用 m 去除關(guān)鍵碼，取其余數(shù)作為地址，即： h(Key)= Key mod m， 這個方法應用的最多，其關(guān)鍵是 m 的選取 ,一般選 m 為小于某個區(qū)域長度 n 的最大素數(shù)（如例 1 中 取 m=13），為什么呢？就是為了盡力避免沖突。 也就是我們所學過的桶排序； 這樣時間效率會變成 O(1) 一次查找 VS 多次查找（找 K次） O(K*n) O(K) 桶排的弊端 A:(18,75,60,43,54,90,46) h[i]:=i mod 13 0 1 2 3 4 5 6 7 8 9 10 11 12 18 mod 13=5 75 mod 13=10 60 mod 13=8 43 mod 13=4 54 mod 13=2 90 mod 13=12 46 mod 13=7 使用一個下標范圍比較大的數(shù)組 a來存儲元素， 設(shè)計一個函數(shù) h，對于要存儲的元素 node， 取一個關(guān)鍵字 key，算出一個函數(shù)值 h(key),把 h(key)作為數(shù)組下標，用 a[h(key)]存儲 node 也可以簡單理解為， 按照關(guān)鍵字為每一個元素進行“分類”，然后將這個元素儲存在相應的“類”所對應的地方 A:(18,75,60,43,54,90,46,5,15,33) h[i]:=i mod 13 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 18 mod 13=5 75 mod 13=10 60 mod 13=8 43 mod 13=4 54 mod 13=2 90 m
教學課件相關(guān)推薦
鄂ICP備17016276號-1