Hash(雜湊) 授課者:李驕芸
Outline Hash table Keyword Hash Function Overflow Handling
Hash table 在靜態表中，我們將識別字存在固定大小的表格中，這個表格稱之hash table。 Hash是經由一個事先設計好的hash function算出某識別字x的位置，即 為x的位置。 Hash Function 雜湊函數 識別字 位址
Keyword Bucket(桶):儲存在記憶體中的一塊循序空間。可將雜湊表分為b個桶。 Slot(槽):每個桶中有s個槽。 Collision(碰撞):兩個不同的識別字經過雜湊函數運算後落在相同的桶。 Overflow(溢位):若經過雜湊過程後,該識別字必須放在一個已經滿的桶中,將產生溢位。
Hash Function---Mid-Square 將識別字轉成一個數值,再求它的平方值,然後再取其中間的幾個位數作為桶的位址. 由於平方值的中間幾個位數通常和識別字的所有字元有關,所以會有較高的機率產生不同的位址. EX. CFGA3671(轉成數值)13476241(取平方值)762(取中間三位數)
Hash Function---Division(1/2) 將識別字x除以某個數值M,取其餘數作為x的位址. M是除數,求出的餘數介於0至M-1之間.
Hash Function---Division(2/2) 若利用除法將345, 728, 251, 490, 15放入12個桶中,除數M為12,雜湊函數為f(x)=x%12. f(345)=9, f(728)=8, f(251)=11, f(490)=10, f(15)=3 X X 6 1 7 2 8 728 3 15 9 345 4 10 490 5 11 251
Hash Function--- Folding(1/3) Shift folding(移動摺疊) Ex.將識別字X=16732942159812每三個位元取一組,求出bucket address如右: P1 167 P2 329 P3 421 P4 598 P5 12 加總結果 1527
Hash Function--- Folding(2/3) Boundary at the folding(邊界摺疊) 先將偶數部份的位元反轉過來,接著將奇數與偶數部份的最右邊位元對齊相加,所得結果即是.
Hash Function--- Folding(3/3) Boundary at the folding P1 167 P2 329 P3 421 P4 598 P5 12 反轉 923 反轉 895 加總結果 2418
Overflow Handling---Linear probing(1/2) 線性探測法,又稱為linear open address. 將雜湊表以一維陣列來表示,若陣列大小為size,則每個元素的位址是0 ~ size-1. 若在位址i發生溢位時,以線性的方式找下一個位置((i+1)%size),若有空的位置則放入,否則繼續往下一個線性位置. 當無法找到空的位置,則表示位置都滿了.
Overflow Handling---Linear probing(2/2) 假設雜湊函數為識別字的第一個字母順序,例如:第一個字母為A,則放入編號為0的桶子.以線性方式依序將識別字C, C1, F, A, A1, A2, Z, Z1,雜湊表的大小為26. A A1 C C1 A2 F Z1 .. Z f(A)=0 f(A1)=0 ->(0+1)%26=1 f(C)=2 f(C1)=2 ->(2+1)%26=3 f(A2)=0 ->(0+1)%26=1 ->..(3+1)%26=4 f(F)=5 f(Z1)=25-> (25+1)%26=0.. ->(5+1)%26=6 F(Z)=25 0 1 2 3 4 5 6 …. 25
Overflow Handling---Linked List(1/2) 將雜湊表以b個串列表示,將落在同一個桶子(bucket)的識別字加在同一個串列上,每個串列表示一個桶子,每個節點為該桶子的槽(slot).直到沒有可用的節點空間為止.
Overflow Handling---Linked List(2/2) 將識別字C, C1, F, A, A1, A2, Z, Z1,依序以鏈結串列法建成雜湊表如下: A A1 A2 null 0 1 2 ……5…….25 null C C1 null … F … Z Z1 null