淺談hashppt課件(完整版)
【正文】 5,60,43,54,90,46) C=2(負的也可以 ) 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 作為散列地址的方法。因此上式的值就只有 b+1 種可能了。 Key H(Key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 329 分析： 關(guān)鍵碼是 9 位的，地址是 3 位的，需要經(jīng)過數(shù)字分析丟掉 6 位。 【 例 4】 如關(guān)鍵碼 Key=58422241，要求轉(zhuǎn)換為 3 位的地址碼。 // 表的大小 procedure makenull。 var orig,i:integer。 begin posi:=locate(x)。 快排 +二分： O(n)=n log2n 哈希表： O(n)=由于哈希函數(shù)的不同，時間復(fù)雜度很難估計 下面來看一下兩種排法的時間效率對比 1 2 3 4 5 6 7 8 9 10 11 12 但是，不能保證每個元素與函數(shù)值都是一一對應(yīng)的，因此極有可能出現(xiàn)不同元素卻出現(xiàn)了相同的函數(shù)值 如 15 和 28對于 h(key):=key mod 13 有相同的函數(shù)值 —2 這樣就產(chǎn)生了“沖突” 另一個函數(shù) I 現(xiàn)在要儲存和使用下面的線性表： A: (1,75,324,43,1353,90,46). 上述兩種方法分別造成了時間和空間上的大量浪費，尤其是數(shù)據(jù)范圍較廣時，可以對第二種方法進行優(yōu)化 設(shè)計一個函數(shù) h(key):=key mod 13 然后把 key儲存在 a[h(key)]中， 這樣的話定義一個 0..12的數(shù)組就夠了 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1