哈希表的定義、查找及分析-資料下載頁
2025-03-10 18:29本頁面
【正文】 ), 散列表的表長為 m，地址序列 // Hi=(hash(key)+di)% m, di=1,2,… ,m 1 j=hash(k)； if(shtable[j]==nullrecd) return(0)； else if(shtable[j].key==k)return(j)； else do{ j=(j+1) % m； } //線性探測再散列 while(shtable[j].key≠k shtable[j]≠nullrecd) if (shtable[j]==nullrecd) return(0)； else return(j)； } } // hashsrch 16 二 . 分析 比較次數(shù)取決于 三個(gè)因素 ： 哈希函數(shù)、處理沖突的方法、哈希表的裝填因子 在一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。 (1)查找成功時(shí)的平均查找長度 ①線性探測 ASLl ≈ ②隨機(jī)探測、二次探測 ASLr ≈ ③鏈地址法 ASLc ≈ )1( 1 121 ??? )ln(1 ?? ?? 21 ??17 例：已知一個(gè)含有 100個(gè)記錄的表，關(guān)鍵字為中國人姓氏的拼音，請給出此表的一個(gè)哈希表設(shè)計(jì)方案，要求它在等概率情況下查找成功的平均查找長度不超過 3。 )1(1121???ASLl = ≤3， (1) 用線性探測再散列處理沖突建立散列表存儲(chǔ) 則由 ： ASLl ≤3，可求出 ? 求得 ? ≤4/5 18 (3) 關(guān)鍵字分析 ： 開頭 az，最長 6位。 選擇 hash函數(shù)： hash(key) = 5*(i1) + L 其中， i為第一個(gè)字母在字母表中的序號(hào)， L為關(guān)鍵字的長度。 (2) 設(shè)表長： 由 ?=記錄長度 n/表長 m , 表長 m = n/? ≥(100*5)/4=125 取表長 m = 133 19 、 、 、 、 、 作業(yè) 20
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1