09年自考《數據結構》各章要點二[10]

　　散列技術將結點按其關鍵字的散列地址存儲到散列表的過程稱為散列

　　散列函數的選擇有兩條標准簡單和均勻

　　常見的散列函數構的造方法

　　·平方取中法hash=int((x^)%)

　　·除余法表長為mhash=x%m

　　·相乘取整法hash=int(m*(x*Aint(x*A));A=

　　·隨機數法hash=random(x)

　　處理沖突的方法

　　開放定址法 一般形式為hi=(h(key)+di)%m≤i≤m開放定址法要求散列表的裝填因子α≤

　　·開放定址法類型

　　·線性探查法address=(hash(x)+i)%m

　　·二次探查法address=(hash(x)+i^)%m

　　·雙重散列法address=(hash(x)+i*hash(y))%m

　　·拉鏈法 是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中

　　·拉鏈法的優點

　　·拉鏈法處理沖突簡單且無堆積現象

　　·鏈表上的結點空間是動態申請的適於無法確定表長的情況

　　·拉鏈法中α可以大於結點較大時其指針域可忽略因此節省空間

　　·拉鏈法構造的散列表刪除結點易實現

　　·拉鏈法也有缺點當結點規模較小時用拉鏈法中的指針域也要占用額外空間還是開放定址法省空間

[]  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22731.html