許多程式語言都提供基於雜湊(hash)的資料結構,例如字典或集合,這類資料結構內部會有雜湊桶(hash bucket),每個桶有個編號,加入此類資料結構的資料,須提供對應的雜湊碼,用來決定將資料置入哪一桶,若想搜尋資料,可以根據雜湊碼來立即定址,從對應的桶中取出。

空間換時間的方案

在資料量龐大時,相對於線性搜尋,或者將資料排序後進行二分搜尋,或特定資料分布下的特定搜尋演算,只要雜湊碼的演算夠迅速,定址後找到對應雜湊桶中的資料,時間複雜度就是O(1),利用此特性來進行搜尋或去重複之類的任務,經常是基於雜湊的資料結構之應用場合。

只不過這個特性是以空間作為代價,因為理想上,一個雜湊桶的裡面最好只有一筆資料,然而,資料來源不確定,雜湊碼的值也就不確定,為了盡量作到一個桶設置一個值,方向之一就是開設足夠多的空間來管理桶,另一個方向是令雜湊碼儘可能地避免重複,讓資料散落在各個桶。

最好的情況下,若有n筆資料,只使用長度為n的陣列,而n筆資料計算出來的雜湊碼,完美地各自對應n個索引,這就是完美雜湊(perfect hash)。此種情況並非不存在,例如,方形迷宮通道可以歸納為16種類型,若通道四個方向給予1、2、4、8數字,基於數字計算而得的雜湊碼會是0到15,使用簡單的陣列就可以管理通道資料了(可參考〈迷宮與王氏磚〉)。

然而,在大多數情況下,用於雜湊桶的空間往往會超過資料的筆數,因此是以空間換取時間,這是為了避免雜湊衝突,因為發生雜湊衝突的話,就要考慮資料往哪存放的問題,像是在桶中構成一組資料清單,或者是動態地尋找下個雜湊桶,無論是哪個都需額外的運算,最差的情況,還有可能讓基於雜湊的資料結構,退化為線性的資料結構(甚至淪為一種攻擊手法)。

多項式捲動雜湊

並非每個程式語言,本身就提供雜湊碼的方案,像是JavaScript、Haskell,得尋找第三方套件或自行實現,我使用OpenSCAD時就遇上了這類需求,例如,若要實現字典,首先我想到了JavaScript物件本身就是字典結構,只不過鍵只能是字串(或ES6後支援Symbol),被指定為鍵的物件,也是轉為字串後作鍵,因此,就試著去瞭解如何對字串進行雜湊。

這不難找到參考資料,閱讀一下Java的String.java原始碼即可,就實現方式而言,如果字元陣列是s,其中是基於s[0]*31ⁿ⁻¹+s[1]*31ⁿ⁻²+...+s[n-1]來計算雜湊碼,若將31視為x,這就是個多項式,這種雜湊計算方式稱為多項式捲動雜湊(Polynomial rolling hash),根據維基百科的內容而言,為了避免過大的雜湊碼,計算後可以取m的模數,選擇適當的x與m來構成不錯的雜湊函式。

m通常是雜湊桶的個數,那麼x為何選擇31呢?根據stackoverflow的討論,選擇31、33、37、39、41等,都可以有比較小的雜湊衝突,只不過質數的選擇僅是一個傳統。

一般多項式捲動雜湊是多項式,若語言在處理次方運算時是用乘法,可基於霍納法(Horner's method)轉換為多個一次多項式的乘法,以減少乘法處理的數量,也就是能用迴圈實作為31*h+s[n],其中的h是上一次迴圈計算後的雜湊碼,同時,《Effective Java》也談到Java選擇31的原因¬──在於現代VM可以將乘法31*h最佳化為(h<<5)-h。

基於同樣的原理,Java中一些物件或輔助方法的hashCode實作,多半是基於多項式捲動雜湊,並且採用31這個數字,例如,陣列相關的雜湊碼,就是取出各元素的雜湊碼,也就是以迴圈實作為31*h+elem.hashCode()的形式來計算,如果透過Objects的hash方法,傳入物件的值域來實作hashCode,最後也是轉為陣列呼叫Arrays的hashCode方法;如果透過整合開發環境,自動生成hashCode實作,也會發現當中採用31這個數字。

實現座標雜湊

基於字串來作為鍵,只是一種簡便運用字典的方式,然而,針對特定的資料也轉為字串後計算雜湊碼,就顯得沒有效率了,例如,3D建模最常面對二維或三維座標,座標的分量本身就是數字,沒必要轉為字串後再計算雜湊碼。

座標資料本身可表示為長度為2或3的陣列,基本上可用多項式捲動雜湊,若語言直接支援向量內積運算,也能與對應的一組向量計算內積,如pt*[961,31,1],其中pt是三維座標,因算出的內積有正有負,正數可以乘2,負數可以乘-2後減1,也就是將正、負結果全放至正方向的偶數與奇數位置。

另一種方式,則是採用康托爾配對函式(Cantor pairing function),簡單來說,對於兩個自然數,可視為二維座標上的x與y座標,對於第一象限的全部座標,是否有辦法將它們連成一條線呢?正如維基百科上的圖示,鋸齒狀連結就可以了,座標x、y對應的第n個點,化為公式的話就是n=1/2*(x+y)*(x+y+1)+y。

康托爾配對函式適用對象是自然數,也就是正整數,對於其他象限的座標,只要設法轉換至第一象限,同樣也能運用配對函式,方式剛才談過,座標分量正數可以乘2,負數可以乘-2後減1,得到的新座標分量若為X、Y,套用1/2*(X+Y)*(X+Y+1)+Y。

不過,由於語言的整數依不同型態會有其上限,在套用康托爾配對函式後,能配對的數量,也就是座標點的數量會有其上限,例如,單就第一象限而言,座標[32767,32767],得到的n就是2147418112,這已經接近有號整數型態的上限2147483647,若再考量其他象限轉換為第一象限的狀況,可雜湊的座標點還要再減半。

〈Mapping two integers to one〉提到了另一種配對函式的計算,如果x大於等於y,x*x+x+y,否則x+y*y,座標[32767,32767]得到的n就是1073741823,數值小上許多,也就是可表現的座標數量會更多。

另外支援xor運算的語言,〈Optimized Spatial Hashing〉談到(x p1 xor y p2 xor z p3) mod n的雜湊函式,其中xyz為座標分量,p1、p2、p3是很大的質數,文件建議73856093、19349663、83492791,有興趣可參考。

視需求而定、以評測為主

至於該採用哪一種雜湊函式,或者是雜湊桶要開多少個,一切還是以需求及評測為主;由於雜湊函式的運算本身也有其成本,若經常需要取得某些資料的雜湊值,可考量為它們儲存雜湊計算後的結果(特別是針對不可變動資料而言),例如Java的String,在首次呼叫hashCode後的結果會被保留,之後再呼叫就可以直接傳回,不再重複計算。

請別單純以理論去想像這些做法,要以實證為主,例如,就我個人經驗而言,在某個場合,將雜湊用於搜尋的一種方案時,雖然速度有所改善,然而真正效能上的大增益,卻是後來採用了OpenSCAD原生C++實作的線性搜尋函式。經過一番檢視後,我發現該場合搜尋的對象數量不多,原生速度夠快,線性搜尋的成本相較於雜湊函式的運算負擔,反而少了許多。

有機會的話,針對自身的需求,試著尋找、瞭解、實現適合的雜湊函式,這會是一個深入雜湊處理的好機會,然而記得最後,一切要以評測為主!

專欄作者


熱門新聞

Advertisement