[ 資料結構 小學堂 ] 搜尋 : 雜湊搜尋法

前言 :
雜湊法這個主題通常被放在和搜尋法一起討論, 主要原因是雜湊法不僅被用於資料搜尋外, 在資料結構的領域中, 你還能將它用在資料的建立, 插入, 刪除與更新. 例如符號表在電腦上的應用很廣泛, 包含組譯程式, 編譯程式與資料庫使用的資料字典等, 都是利用提供的名稱來找到對應的屬性. 符號表依其特性可以分成兩類 : 靜態表 和動態表. 而雜湊表則是屬於靜態表的一種, 我們將相關資料與鍵值儲存在一個固定大小的表格中.

雜湊法簡介 :
基本上, 所謂雜湊法就是將本身的鍵值, 經由特定的數學運算或使用其他的方法, 轉換成相對應的資料儲存位址. 而雜湊所使用的數學函數就稱為 "雜湊函數". 現在我們來介紹有關雜湊函數的相關名詞 :
* Bucket (桶) :

雜湊表中儲存資料的位址, 每一個位置定應到唯一的一個位址 (Bucket Address). 桶就好像一筆記錄.

* Slot (槽) :

每一筆紀錄中可能包含好幾個欄位, 而Slot 就是指 "桶" 中的欄位.

* Collision (碰撞) :

若兩筆不同資料, 經過雜湊運算後, 對應到相同位址時, 稱為碰撞.

* 溢位 :

如果資料經過雜湊函數運算後, 所對應的 Bucket 已滿, 則會使 Bucket 發生溢位.

* 雜奏表 :
儲

存紀錄的連續記憶體. 雜湊表是一種類似資料表的索引表格, 其中可分為 n 個 Bucket, 每個 Bucket 又可以分為 m 個 Slot, 如下圖所示 :

* 同義字 :

當兩個識別字 I1 及 I2, 經過雜湊函數運換後所得到的數值相同, 及 f(I1) = f(I2), 則稱 I1 與 I2 對於雜湊函數 f 是同義字.

* 載入密度 (Loading Factor) :

所謂載入密度是指識別字的使用數目除於雜湊表內槽的總數 :

如果載入密度越大, 則表示雜湊空間的使用率越高, 碰撞或溢位的機率越高

* 完美雜湊 :

指沒有碰撞又沒有溢位的雜湊函數.

在此建議在設計雜湊函數應遵循底下幾個原則 :

1. 降低碰撞及溢位的產生.
2. 雜湊函數不宜過於複雜, 越容易計算越佳.
3. 盡量把文字的鍵值轉換成數字的鍵值, 以利雜湊函數的運算.
4. 所設計的雜湊函數計算所得的值, 盡量能均勻分布在每一桶中. 不要過度集中在某些桶內, 這樣就可以降低碰撞與減少溢位的處理.

This message was edited 1 time. Last update was at 20/06/2010 00:46:35