杂凑表.ppt

雜 湊 表 內 容 大 綱 雜湊表的定義 雜湊表的操作 雜湊函數 碰撞處理 雜湊表資料刪除 雜湊表的範例程式 雜湊表(hash table)是一種可以快速處理資料新增、搜尋及刪除的資料結構。 利用資料的鍵值(key)直接對應至儲存位置的方法，雜湊表可以在幾次的資料比對後就完成資料加入、搜尋及刪除的動作。 雜湊表的定義 (1/2) 雜湊表(hash table)： 是一個將資料鍵值透過雜湊函數(hash function)轉換為資料儲存位置，而可快速進行資料加入、搜尋以及刪除的資料結構。 透過資料的鍵值(key)直接由雜湊函數(hash function)對應至儲存位置的方法，雜湊表可以在幾次的資料比對後就完成資料新增、搜尋及刪除的動作。 因此，雜湊表的各項操作的時間複雜度均為O(1)。下圖顯示雜湊表、雜湊函數與儲存位置的關係。 雜湊表的定義 (2/2) 雜湊表的操作 (1/1) 雜湊表的操作主要有以下三個： 新增(insert)：將一新的鍵值加入雜湊表中。 刪除(delete)：將一鍵值自雜湊表中移除。 搜尋(search)：尋找某一鍵值所在位置。 下圖顯示一個執行各種雜湊表操作的實例。 假設k為鍵值、p為雜湊表大小，在下圖的實例中，採用k%p的公式(除法)來計算鍵值的儲存位置，而當二個鍵值k1、k2對應至相同儲存位置時，這稱為發生碰撞(collision)，則採用線性探測(linear probing)的方式，依序尋找(k2+1)%p、(k2+2)%p、(k2+3)%p…等位置來作為新的儲存位置。 雜湊函數 (1/8) 雜湊表必須依賴雜湊函數(hash function)來計算出資料儲存位置，因此，雜湊函數與雜湊表有密不可分的關係。 一個雜湊函數H可以描述如下： H: H(key)=position 對雜湊表而言，若雜湊函數可以將所有的鍵值都對應到一個獨一無二的位置，則可以很單純的直接進行資料的加入、搜尋或刪除的動作。 然而，由於鍵值的可能值數目往往遠遠大於雜湊表的儲存空間，因此難免會有不同的鍵值對應到相同儲存位置的情況，我們將這種情況稱為碰撞(collision)。碰撞是雜湊表的運作中最需要用心解決的問題。 雜湊函數 (2/8) 雜湊函數可以進行資料鍵值與雜湊表儲存位置之間的轉換，一個好的雜湊函數必須具有以下的特點： 1.?計算簡單。 2.?碰撞(collision)少。 3.?不可造成雜湊表儲存位置局部偏重(bias)的狀況。 雜湊函數 (3/8) 以下我們介紹常用的雜湊函數： 1.?除法(division method)： H(key)=key mod p，其中p代表雜湊表的大小，它必須是質數(prime number)。我們將雜湊表大小p限制為質數是為了減少碰撞發生，例如，鍵值10，26，50，在p=8的情況下都會得到2的雜湊位置，即 H(10)=H(26)=H(50)=H(74)=2，若我們選擇p=7，則 H(10)=3，H(26)=5，H(50)=1，H(74)=4，其中完全沒有碰撞發生。 雜湊函數 (4/8) 2.?平方取中間為數法(mid-square method)： H(key)=mid(key2)，其中mid可以取得key2的一些中間位數。因為一個鍵值平方的中間位數與鍵值的所有位數的數字大都沒有關係，因此，不同鍵值就有較大的機率對應到不同的位置；例如：若我們取萬位數、千位數及百位數，則 H(1234)=mid(1522756)=227 H(4321)=mid=710 雜湊函數 (5/8) 3.?折疊法(folding method)： 此方法將鍵值key分割為長度為L的幾個片段，使之除了最後一個片段之外，其他所有的片段長度均相同。分段完畢之後再將所有片段相加，即可得到最後的儲存位置，例如： key=12345678989，取L=3，我們可將key分成下列幾個片段： 123、456、789、89，我們再將這些片段相加起來得到123+456+789+89=1457，其中1457就是我們儲存資料的位置。 雜湊函數 (6/8) 折疊法還有許多不同的做法，例如，我們可以將各片段進行不同的旋轉(如456可旋轉為564或645)或翻轉(如456可翻轉為654)，相加的時候也可以選擇向左對齊或向右對齊相加(如89選擇向左對齊相加，則實際加入的值為890)，甚至於再將最後片段相加的值再除以表格大小(質數p)。例如，若表格大小為97，則前述Key=123456789892的實際儲存位置=1457 mod 97=2。 雜湊函數 (7/8) 4