淺談雜湊碼設計

許多程式語言都提供基於雜湊（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++實作的線性搜尋函式。經過一番檢視後，我發現該場合搜尋的對象數量不多，原生速度夠快，線性搜尋的成本相較於雜湊函式的運算負擔，反而少了許多。

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