《淺談hash》ppt課件(文件)
【正文】 020220， 1002022， 0012321)，若取表長為 1000，則可取中間的三位數(shù)作為散列地址集： (100， 121， 201， 020， 123)。 【 例 4】 如關(guān)鍵碼 Key=58422241，要求轉(zhuǎn)換為 3 位的地址碼。 （ 236075） 13=2*135+3*134+6*133+7*13+5 =(841547)10 再進(jìn)行數(shù)字分析，比如選擇第 2,3,4,5 位，于是h(236075)=4154 A:(18,75,60,43,54,90,46,5) h(k)+c 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 54 43 18 46 60 75 90 5 A:(18,75,60,43,54,90,46,5) 46 90 18 15 75 43 60 5 15 1 1 11 1 1 1 1 1 1 Record, key link r:=m 哈希表支持的運(yùn)算主要有： 初始化 (makenull)、哈希函數(shù)值的運(yùn)算 (h(x))、插入元素(insert)、查找元素 (member)。 // 表的大小 procedure makenull。 哈希函數(shù)值的運(yùn)算根據(jù)函數(shù)的不同而變化，例如除余法的一個例子： function h(x:longint):Integer。 var orig,i:integer。 locate:=(orig+i) mod S。 begin posi:=locate(x)。 var posi:integer。 快排 +二分： 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)在要儲存和使用下面的線性表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1