淺談hashppt課件-wenkub
2023-05-14 03:10:20 本頁面
【正文】 d 13=2 90 mod 13=12 46 mod 13=7 使用一個下標(biāo)范圍比較大的數(shù)組 a來存儲元素， 設(shè)計一個函數(shù) h，對于要存儲的元素 node， 取一個關(guān)鍵字 key，算出一個函數(shù)值 h(key),把 h(key)作為數(shù)組下標(biāo)，用 a[h(key)]存儲 node 也可以簡單理解為， 按照關(guān)鍵字為每一個元素進(jìn)行“分類”，然后將這個元素儲存在相應(yīng)的“類”所對應(yīng)的地方 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 mod 13=12 46 mod 13=7 5 mod 13=5 15 mod 13=2 31 mod 13=5 哈希表、哈希函數(shù)、沖突 如何解決沖突，下面再說 A:(18,75,60,43,54,90,46) C=2(負(fù)的也可以 ) m[20]:=18 m[77]:=75 m[62]:=60 m[45]:=43 m[56]:=54 m[92]:=90 m[48]:=46 C=0時 直接定址法 以關(guān)鍵字 Key 本身或關(guān)鍵字加上某個數(shù)值常量 C 作為散列地址的方法。一般地說，如果 m 的約數(shù)越 多，那么沖突的幾率就越大。因此上式的值就只有 b+1 種可能了。而素數(shù)的約數(shù)是最少的，因此我們選用大素數(shù)。 Key H(Key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 329 分析： 關(guān)鍵碼是 9 位的，地址是 3 位的，需要經(jīng)過數(shù)字分析丟掉 6 位。 【 例 3】 將一組關(guān)鍵字 (0100， 0110， 1010， 1001， 0111)平方后得 (0010000， 0012100， 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1