．()散列表存儲的基本思想是用關鍵字的值決定數據元素的存儲地址
()散列表存儲中解決碰撞的基本方法
① 開放定址法 形成地址序列的公式是Hi=(H(key)+di)% m其中m是表長di是增量根據di取法不同又分為三種
a．di =…m 稱為線性探測再散列其特點是逐個探測表空間只要散列表中有空閒空間就可解決碰撞缺點是容易造成聚集即不是同義詞的關鍵字爭奪同一散列地址
b．di =… ±k(k≤m/) 稱為二次探測再散列它減少了聚集但不容易探測到全部表空間只有當表長為形如j+(j為整數)的素數時才有可能
c．di =偽隨機數序列稱為隨機探測再散列
② 再散列法 Hi=RHi(key) i=…k是不同的散列函數即在同義詞產生碰撞時用另一散列函數計算散列地址直到解決碰撞該方法不易產生聚集但增加了計算時間
③ 鏈地址法 將關鍵字為同義詞的記錄存儲在同一鏈表中散列表地址區間用H[m]表示分量初始值為空指針凡散列地址為i(≤i≤m)的記錄均插在以H[i]為頭指針的鏈表中這種解決方法中數據元素個數不受表長限制插入和刪除操作方便但增加了指針的空間開銷這種散列表常稱為開散列表而①中的散列表稱閉散列表含義是元素個數受表長限制
④ 建立公共溢出區 設H[m]為基本表凡關鍵字為同義詞的記錄都填入溢出區
O[m]
()用分離的同義詞表和結合的同義詞表解決碰撞均屬於鏈地址法鏈地址向量空間中的每個元素不是簡單的地址而是關鍵字和指針兩個域散列地址為i(≤i≤m)的第一個關鍵字存儲在地址空間向量第i個分量的關鍵字域前者的指針域是動態指針指向同義詞的鏈表具有上面③的優缺點後者實際是靜態鏈表同義詞存在同一地址向量空間(從最後向前找空閒單元)以指針相連節省了空間但易產生堆積查找效率低
()要在被刪除結點的散列地址處作標記不能物理的刪除否則中斷了查找通路
()記錄 負載因子
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22830.html
