9.4 込錬燕臥孀(墫鑑隈)!侃尖喝融議圭隈
匯. 蝕慧協峽隈
侭僚蝕慧協峽隈?軸頁喇購囚鷹誼欺議込錬仇峽匯稀恢伏阻喝融?匆祥頁傍?乎仇峽厮将贋慧阻方象圷殆?祥肇儖孀和匯倖腎議込錬仇峽?峪勣込錬燕怎校寄?腎議込錬仇峽悳嬬孀欺?旺繍方象圷殆贋秘。
孀腎込錬仇峽圭隈載謹?和中初府眉嶽?
1. ?來冥霞隈
Hi=(Hash(key)+di) mod m ( 1≤i < m )
凪嶄?
Hash(key)葎込錬痕方
m 葎込錬燕海業
di 葎奐楚會双1?2?……?m-1?拝di=i
‐箭9.12/購囚鷹鹿葎{47?7?29?11?16?92?22?8?3}?込錬燕燕海葎11?Hash(key)=key mod 11?喘?來冥霞隈侃尖喝融?秀燕泌和? 47、7、11、16、92 譲頁喇込錬痕方誼欺議短嗤喝融議込錬仇峽遇岷俊贋秘議?Hash(29)=7?込錬仇峽貧喝融?俶儖孀和匯倖腎議込錬仇峽?
喇H1=(Hash(29)+1) mod 11=8?込錬仇峽8 葎腎?繍29 贋秘。総翌?22、8 揖劔壓込錬仇峽貧嗤喝融?匆頁喇H1 孀欺腎議込錬仇峽議?
遇Hash(3)=3?込錬仇峽貧喝融?喇
H1=(Hash(3)+1) mod 11=4 挽隼喝融?
H2=(Hash(3)+2) mod 11=5 挽隼喝融?
H3=(Hash(3)+3) mod 11=6 孀欺腎議込錬仇峽?贋秘。
?來冥霞隈辛嬬聞及i 倖込錬仇峽議揖吶簡贋秘及i+1 倖込錬仇峽?宸劔云哘贋秘及i+1 倖込錬仇峽議圷殆延撹阻及i+2 倖込錬仇峽議揖吶簡?……?咀緩?辛嬬竃孖載謹圷殆壓屢惣議込錬仇峽貧“均持”軟栖?寄寄週詰阻臥孀丼楕。葎緩?辛寡喘屈肝冥霞隈?賜褒込錬痕方冥霞隈?參個鋲“均持”諒籾。
2. 屈肝冥霞隈
Hi=(Hash(key)±di) mod m
凪嶄?
Hash(key)葎込錬痕方
m 葎込錬燕海業?m 勣箔頁蝶倖4k+3 議嵎方(k 頁屁方)
di 葎奐楚會双12?-12?22?-22?……?q2?-q2 拝q≤1/2 (m-1)
挽參貧箭喘屈肝冥霞隈侃尖喝融?秀燕泌和? 斤購囚鷹儖孀腎議込錬仇峽峪嗤3 宸倖購囚鷹嚥貧箭音揖?
Hash(3)=3?込錬仇峽貧喝融?喇
H1=(Hash(3)+12) mod 11=4 挽隼喝融?
H2=(Hash(3)-12) mod 11=2 孀欺腎議込錬仇峽?贋秘。
3. 褒込錬痕方冥霞隈
Hi=(Hash(key)+i*ReHash(key)) mod m (i=1?2?……?m-1)
凪嶄?
Hash(key)?ReHash(key)頁曾倖込錬痕方?
m 葎込錬燕海業
褒込錬痕方冥霞隈?枠喘及匯倖痕方Hash(key)斤購囚鷹柴麻込錬仇峽?匯稀恢伏仇峽喝融?壅喘及屈倖痕方ReHash(key)鳩協卞強議化海咀徨?恷朔?宥狛化海咀徨會双喇冥霞痕方儖孀腎議込錬仇峽。
曳泌?Hash(key)=a 扮恢伏仇峽喝融?祥柴麻ReHash(key)=b?夸冥霞議仇峽會双葎
H1=(a+b) mod m?H2=(a+2b) mod m?……?Hm-1=(a+(m-1)b) mod m
屈. 性全隈
譜込錬痕方誼欺議込錬仇峽囃壓曝寂[0?m-1]貧?參耽倖込錬仇峽恬葎匯倖峺寞?峺?匯倖全?軸蛍塘峺寞方怏ElemType *eptr[m]?秀羨m 倖腎全燕?喇込錬痕方斤購囚鷹廬算朔?啌符欺揖匯込錬仇峽i 議揖吶簡譲紗秘欺*eptr[i]峺?議全燕嶄。
‐箭9.l3/購囚鷹會双葎47,7,29,11,16,92,22,8,3,50,37,89,94,21?込錬痕方葎Hash(key)=key mod 11
喘性全隈侃尖喝融?秀燕泌夕9.21。
眉. 秀羨匯倖巷慌吝竃曝
譜込錬痕方恢伏議込錬仇峽鹿葎[0?m-1]?夸蛍塘曾倖燕?
匯倖児云燕ElemType base_tbl[m]?耽倖汽圷峪嬬贋慧匯倖圷殆?
匯倖吝竃燕ElemType over_tbl[k]?峪勣購囚鷹斤哘議込錬仇峽壓児云燕貧恢伏喝融?夸侭嗤宸劔議圷殆匯舵贋秘乎燕嶄。臥孀扮?斤公協峙kx 宥狛込錬痕方柴麻竃込錬仇峽i?枠嚥児云燕議base_tbl[i]汽圷曳熟?飛屢吉?臥孀撹孔?倦夸?壅欺吝竃燕嶄序佩臥孀。