散列文件的組織方式
散列文件是利用散列存儲方式組織的文件亦稱直接存取文件即根據文件中關鍵字的特點設計一個散列函數和處理沖突的方
法將記錄散列到存儲設備上
散列表與散列文件比較
基桶和溢出桶
在散列文件的存儲單位叫桶(Bucket)假如一個桶能存放m個記錄則當桶中已有m個同義詞的記錄時存放第m+個同義詞會發
生溢出需要將第m+個同義詞存放到另一個桶中通常稱此桶為溢出桶相對地稱前m個同義詞存放的桶為基桶
注意
① 溢出桶和基桶大小相同相互之間用指針相鏈接
② 當在基桶中沒有找到待查記錄時就沿著指針到所指溢出桶中進行查找因此希望同一散列地址的溢出桶和基桶在磁盤上
的物理位置不要相距太遠最好在同一柱面上
【例】某一文件有個記錄其關鍵字分別為桶的
容量m=桶數b=用除余法作散列函數H(key)=key%由此得到的散列文件如下圖所示
散列文件的查找操作
在散列文件中查找的過程
() 根據給定值求出散列桶地址
() 將基桶的記錄讀人內存進行順序查找
() 若找到關鍵字等於給定值的記錄則檢索成功;否則讀人溢出桶的記錄繼續進行查找
散列文件的刪除操作
在散列文件中刪去一個記錄僅需對被刪記錄作刪除標記即可
散列文件的特點
散列文件的優點
() 文件隨機存放記錄不需進行排序
() 插入刪除方便
() 存取速度快;不需要索引區節省存儲空間
散列文件的缺點
() 不能進行順序存取只能按關鍵字隨機存取
() 詢問方式限於簡單詢問
() 在經過多次插入刪除後可能造成文件結構不合理需要重新組織文件
From:http://tw.wingwit.com/Article/program/sjjg/201311/23536.html
