雜湊 ( hashing )

雜湊 ( hashing )
　
　　雜湊法 ( hashing ) 的搜尋與一般的搜尋法 ( saerching ) 不同。在 Hashing 中，鍵值 ( key value
　　) 或識別字 ( identifier ) 在記憶體的位址是經由函數 ( function ) 轉換而得。此種函數，一般稱之
　　為雜湊函數 ( hashing function ) 或鍵值對應位址轉換 ( key to address transformation ) 。
　
　　　　　　　　　　　　
　
　　雜湊法具有以下四項優點：
　　(１) 使用雜湊法搜尋，檔案不須事先排序 ( sorting ) 。
　　(２) 在沒有碰撞 ( collision ) 及溢位 ( overflow ) 的情形下，只需一次讀取即可，且搜尋的速度與
　　　　資料量的多寡無關。
　　(３) 保密性高，若不知雜湊函數，無法擷取到資料。
　　(４) 可做資料的壓縮 ( data compression ) ，利用適當的散置函數，可將資料壓縮到一個較小的
　　　　範圍內，以節省空間。
　
雜湊函數 ( hashing function )
　
　　一般常見的雜湊函數有下列幾種方法：
　
　　(１) 平方後取中間位數 ( mid - square )
　
　　　　此法是將鍵值平方後，然後視儲存空間的大小來決定取幾位。
　　　　
　　　　【範例】
　　　　　　　　鍵值 k = 113586 。令 m = 9999 ，故 m 為 4 位數的正整數。
　　　　　　　　則 h( k ) = k2 取中間四位數
　　　　　　　　　　　 = 12901779369 取中間 4 位數
　　　　　　　　　　　　= 1779
　
　　　　　　　　m 為儲存空間的大小。
　
　　(２) 折疊法 ( folding )
　
　　　　此法是將鍵值分為數段，除了最後一段外，其餘各段皆須等長，然後將每一段相加，即可
　　　　得到其所對應的位址。在相加的時後，有兩種方式：
　
　　　　(ａ) 位移折疊 ( shift folding )
　　　　　　將各段向左邊靠齊後相加。
　　　　(ｂ) 邊界折疊 ( folding at the boundaries )
　　　　　　將奇數位段或偶數位段反轉後相加。
　
　　　　【範例】
　　　　　　　　如有一個鍵值為 12320324111220 ，其儲存位址為何？
　
　　　　　　　　假設將其分為 5 段，如下所示：
　

　
　　(３) 除法 ( Division )
　
　　　　此法利用模數運算，將識別字 X 除以某一個數值 M ，取其餘數當做 X 的位址。這個位址
　　　　介於 0 ~ M-1 之間。
　
　　　　即 fD ( X ) = X mod M
　
　　(４) 數位分析法 ( digit analysis )
　
　　　　此法適用於大量的靜態資料，亦即所有的鍵值均事先知道，然後檢查所有的數位，分析每
　　　　一數位是否均勻分佈，將不均勻的數位刪除，然後根據儲存空間的大小來決定數位的數目
　　　　。
　
　　　　【範例】
　　　　　　有五位學生的學號分別是：
　　　　　　ST1 = 682203
　　　　　　ST2 = 682171
　　　　　　ST3 = 693214
　　　　　　ST4 = 695252
　　　　　　ST5 = 691340
　
　　　　　　令 m = 100 ，那我們只能挑選兩位數當做每一個學號的 Hashing Function 數值。可利
　　　　　　用統計的方法，分析各數位的分佈情形，方法如下：
　


　　　　　　　SKi 之值越小者，表示 Di 分佈越均勻，因此，我們選擇 D1 和 D2 當做 Hashing
　　　　　　　Function 的數值，故 h(ST1) = 03 ，h(ST2) = 71，h(ST3) = 14，h(ST4)=52，h
　　　　　　　(ST5) = 40
　
解決溢位的方法 ( overflow handing )
　
(１) 線性探測 ( linear probing )

　　又稱為線性開放定址 ( linear open addressing )。其做法是將雜湊位址視為環狀的空間，當溢位
　　發生時，以線性方式從下一號桶開始探測，找尋一個空的儲存位址將資料存入。如下圖所示：
　

　
(２) 鏈結串列 ( chaining )
　
　　是將雜湊空間建立成 b 個串列，起初只有 b 個串列首，只放起始位址，並不放資料，相同位址
　　的鍵值，將形成一個鏈結串列。如下圖所示：
　

　
　　平均探測次數 = 每個節點探測次數之總合 / 節點數
　
　　如上圖， 49 , 23 , 53 , 41 探測數為 1 次，30 , 60 為 2 次，67 為 3 次，節點數為 49 , 23 , 53
　　, 41 , 30 , 60 , 67 等 7 個。
　　故平均比較(探測)數 = ( 1+1+1+1+2+2+3 ) / 7 = 11 / 7
　
(３) 平方探測 ( quadratic probing )
　
　　此法是改善線性探測的缺失，避免相近的鍵值聚在一起。當 f(x) 的位址發生溢位時，下一次是
　　探測 ( f(x) + i2 ) mod b 與 ( f(x) - i2 ) mod b ，其中 1<= i <= ( b-1 ) / 2 ，b 是具有 4j+3 型式的
　　質數。
　
(４) 再雜湊 ( rehashing )
　
　　設置一系列的雜湊函數 g1 , g2 , g3 , .... , gm 。當使用 g1 產生溢位時，則改用 g2 ，若 g2 又
　　發生溢位時，則改用 g3 ，直到沒有溢位發生為止。
　
相關名詞
　
完美雜湊 ( Perfect Hashing )
　
　　完美雜湊 ( Perfect Hashing ) 係指沒有碰撞 ( collision )，亦沒有溢位 ( overflow ) 的雜湊法。一
　　般用於靜態表 ( static table ) 中，由於所有的鍵值均已事先得知，因此可設計出一完美雜湊法
　　來處理。
　
桶 ( bucket )
　
　　雜湊表中儲存資料的位置，每個位置被給定一個唯一的位址，稱之為 bucket address 。
　
槽 ( slot )
　
　　每一個桶可能有好幾個儲存區，此儲存區便稱之為槽 ( slot ) 。每一個槽可以容納一個記錄。

碰撞 ( collision )
　
　　當兩個不同的識別字經過雜湊函數運算後，落在相同的 bucket address ，稱之為碰撞。
　
溢位 ( overflow )
　
　　如果一個識別字經過雜湊函數運算後，所對應的 bucket 已經滿了，就稱之為溢位。
　
同義字 ( Synonym )

P2P-Freenet

Freenet 是一種無中控儲存系統，著重在anonymity 上，但是卻花費很多在無法預測的retrieval 時間。每個Peer 儲存了路由表格，其中包含了鄰接點的位置along with numeric keys corresponding to itemsstored in them。這個表格也幫助路由來要求最接近儲存Peer 的key values。這種搜尋的工作就像用backtracking 的演算法來爬陡峭的山壁，就是傳送最多hops 數目的訊息，如果當中沒有正確的位置就導向另一條路徑。Peers 在新的路由表格中增加了新的entry，反之它們接收到不管是一個從參加的peer 傳來的announcement message 或是一個傳送到未知的peer 的query message。在Freenet中，nodes 可以自由地加入或離開這個網路
本身檔案的存在時間長短並不重要，而且檔案會重複在多台機器上。

P2P－Chord

Chord [7]是由麻省理工學院所提出的lookup（key）的演算法，其建立拓樸的方式主要是將每一個加入節點IP 位址利用雜湊函數（Hashing function），產生一個節點代碼（Node ID），這個代碼會對應到一個由N 個整數所形成的邏輯代碼環（identifier circle），代表節點的位置，如圖 2-1 所示，N1、N8、…、N51等節點，即是透過雜湊函數產生代碼，並對應到邏輯代碼環上的位置概念圖。當所加入的節點將檔案分享到Chord 的系統時，Chord 也是利用雜湊函數將所分享的檔案產生代碼，對應到環狀代碼環上的節點儲存起來。例如代碼為1的檔案，則儲存在節點代碼1 中，代碼為2~8 的檔案則儲存在節點代碼8 中，依此類推。為了加快檔案搜尋的速度，每個節點都會維護一個路由表（Fingertable），路由表內所記錄的為每個節點的次節點（successor）的位置，所謂次節點就是沿著邏輯代碼環順時鐘方向前進所遇到的第一個節點，紀錄次節點的內容為（ n + 2i−1 ），n 為該節點的代碼，1≤ i ≤ logN 。因此，當節點搜尋檔案時，則利用代碼來比對節點中的路由表，進行繞送。我們以圖 2-1 舉例說明，當節點代碼8 要搜尋檔案代碼42 時，節點代碼8 則透過節點中的路由表，開始尋找檔案存在的位置。



圖 2-1 的繞送表中，我們可以知道到N8+32 所對應到節點代碼為N42，因此，透過節點的繞送表查詢，可以直接跳躍到所查詢的到的節點，而不需要依照順時鐘方向依序詢問代碼環上的節點，而達到加快搜尋的速度。

P2P計算技術展望

技術上，一個純P2P應用必須貫徹只有對等協議，沒有伺服器和客戶端的概念。但這樣的純P2P應用和網路是很少的，大部分稱為P2P的網路和應用實際上包含了或者依賴一些非對等單元，如DNS。同時，真正的應用也使用了多個協議，使節點可以同時或分時做客戶端，伺服器，和對等節點。完全分散的對等網路已經使用了很多年了，像 Usenet(1979年)和FidoNet(1984年)這兩個例子。

很多P2P系統使用更強的對等點（稱為超級對等點(Super Node)）作為伺服器，那些客戶節點以星狀方式連接到一個超級對等點上。

在1990年代末期，為了促進對等網路應用的發展，SUN公司增加了一些類到java技術中，讓開發者能開發分散的實時聊天的applet和應用，這是在即時通信流行之前。這個工作現在有JXTA工程來繼續實現。

P2P系統和應用已經吸引了電腦科學研究的大量關注，一些卓越的研究計劃包括Chord計劃,
ARPANET, the PAST storage utility, P-Grid（一個自發組織的新興覆蓋性網路），和CoopNet內容分發系統。

P2P－Tapestry

Tapestry是由加州柏克萊大學所提出的點對點搜尋架構。其架構也是先由雜湊函數將節點的IP 與檔案轉成代碼，所不同的是其代碼為16 進位的數字所組成。Tapestry 點對點系統架構的節點加入與搜尋檔案的方式，主要都是利用節點代碼之間字尾比對的方式來形成一個網路拓樸。
當新節點加入時，新節點必須先透過系統所預設的閘道節點（Gateway node）取得其路由表最接近的節點位置資訊，再透過最接近節點內的路由表與新加入的節點代碼做字尾比對，找出最接近的新加入節點的代碼，以此類推直到找到與新加入節點最接近的節點，與其連接並取得其節點所負責管理的檔案位址資料。其主要的搜尋方式與節點的佈建方式都與前述的演算法大同小異。

P2P－Pastry

Pastry是由微軟倫敦康橋軟體研究所所提出的點對點搜尋演算法，Pastry點對點系統與Chord 點對點系統都是利用環狀邏輯拓樸架構來設計的點對點網路架構。

Pastry 系統也是利用兩個不同的雜湊函數將節點IP 與檔案轉換成128-bit的節點代碼與檔案代碼，而每個節點也有路由表（routing table）來記錄節點的代碼與檔案代碼間對應關係的資料，如下圖所示。為了達到快速搜尋的目的，Pastry 系統節點的路由表將所記錄的節點分為Leaf set、Routing table 以及Neighborhood set 三個部分。

其中，Leaf set 所記錄的為與節點所相鄰的節點代碼，而Neighborhood set 所儲存的資訊為相近的節點代碼。當需要搜尋檔案時，每個節點會先搜尋比對是否在Leaf set 或是Neighborhood 內。而Routing table 所記錄的資訊為與節點代碼有相同前置碼（prefix）的節點。下圖所示的節點路由表為節點代碼10233102 的路由表。

當Pastry 在做檔案搜尋時，會先判斷所要尋找的節點是否在Leaf set 或是Neighborhood set 中。如果存在則可以馬上找到檔案存在的節點。如果沒有在Leaf set 或是Neighborhood set 中，則透過Routing table中的前置碼，找出最接近的的節點，再從所找出最接近的節點繼續搜尋。

P2P－CAN（Content-Addressable Network）

CAN是由AT&T 所提出點對點搜尋演算法，CAN 是利用多維座標空間概念來建構的點對點架構。下圖即為一個包含五個節點二維座標系統的CAN架構概念圖。

如節點A 所擁有的座標空間為（0-0.5,0-0.5），節點B 所用有的座標空間為（0.5-1.0,0-0.5）。接下來，我們利用下圖來說明CAN 點對點建立的演算法。當一個新的節點欲加入CAN 系統時，新加入的節點會透過一個起始點（Bootstrap）隨機的選擇系統中的節點，並送出加入（JOIN）系統的訊息給隨機選擇的節點。當被選擇到的節點收到加入的訊息時，則均分其所擁有的座標空間。如下圖所示，當節點E 加入節點D 的區域時，則D 將其所擁有座標空間均分給E。

而在CAN 的系統中檔案的儲存方式是當節點欲分享新的檔案加入CAN 系統時，CAN 系統會將其檔案名稱依照雜湊函數計算出一個座標，並將檔案資訊儲存在此座標空間的節點。當節點欲搜尋檔案時，CAN 也是利用每個節點所擁有的路由表（coordinate routing table）來搜尋檔案。路由表內所儲存的資料為記錄在座標空間中相鄰節點的IP 位址及所擁有的空間資訊。因此，當起始點收到系統中節點要求搜尋檔案的訊息時，起始點會先利用雜湊函數計算出此檔案所代表的座標，起始點會從系統中任意選擇一個節點，並將搜尋檔案的座標送給被起始點所選擇的節點。被選擇到的節點收到檔案資料訊息時，會先查詢檔案資料是否存在節點中，如果存在則回報檔案訊息給提出搜尋檔案的節點。如果不存在，則節點會依照節點中的路由表，依據貪婪演算法（greedy algorithm）找出一個與檔案座標最接近的節點，並轉送此查詢訊息，依照此搜尋方式直到找到檔案為止。