iT邦幫忙

DAY 30
5

檔案系統的設計與效能系列 第 30

檔案系統的設計與效能 - Hash

除了i-node,hash是另一種用來儲存磁碟資料的方法。
除了i-node,hash是另一種用來儲存磁碟資料的方法。Hash簡單的說就是透過特殊的函數**(hash function)產生對應資料的key值,而這個值要盡可能地避免重複,以減少查詢時的失誤(兩個以上的資料對應到相同的key,一般稱為碰撞**)。另外,同一個資料在同一個hash function的作用之下,永遠都會產生相同的key。反過來,輸入key值,就可以得到確切的資料。在檔案系統中,這些key值代表的是index,而這些key值就表格的形式(hash table)儲存起來。

Hash 的一大優點是,透過hash function查表只是固定時間的動作(演算法術語: constant time),但是卻點就是key的碰撞在所難免。這是一個設計上的衝突,越複雜的hash function設計可以盡可能地避免key值得碰撞,但是卻增加了設計的難度,以及影響執行的效率。比較折衷的方法有:1. 將有相同的key值的資料串再一起,2. 遇到碰撞時再次進行其他的hash function運算。第一種折衷方式是最常見的,將擁有相同key值的資料串在一起,然後再依序查詢。理論上只要hash function不要太差,這個串列就不會太長,影響也就有限了。

Hash 本身還有兩個(小)缺點,剛剛說到key值以hash tabale的形式儲存下來,這表格當然是有所限制的。而如果表格小一點,占用的空間可以少一點,但是相對的資料碰撞的機會就增加;反之,表格大一點,減少了資料碰撞,但是也造成空間的浪費。有一中動態hash table的設計,但是每當table變更時,key值就需要重新計算,這樣反而影響效能。還有,key值本身沒有順序,所以無法在hash table中進行尋訪的動作(in-order traversal),這動作是為了加速查詢的結果。

系列文章


上一篇
檔案系統的設計與效能 - B+ Tree
下一篇
檔案系統的設計與效能 - 綠能的相關研究
系列文
檔案系統的設計與效能32

1 則留言

0
modernsarah
iT邦研究生 4 級 ‧ 2010-11-03 10:59:28

灑花恭喜大大和我在同一天練成~
Oh~Yeah~終於解脫了~~

chiounan iT邦研究生 1 級 ‧ 2010-11-04 13:57:28 檢舉

也恭喜你呀。開心

我要留言

立即登入留言