圖說演算法使用JavaScript(三十九)

11-2-3摺疊法
摺疊法是將資料轉換成一串數字後,先將這串數字先拆成數個部分,最後再把它們加起來,就可以計算出這個鍵值的Bucket Address。例如有一資料,轉換成數字後為2365479125443,若以每4個字為一個部分則可拆為:2365,4791,2544,3。將四組數字加起來即為索引值:

在摺疊法中有兩個作法,如上例直接將每一部分相加所得的值作為其bucketaddress,這種作法我們稱為(移動摺疊法)。但雜湊法的設計原則之一就是降低碰撞,如果您希望降低碰撞的機會,我們可以將上述每一部分的數字中的奇數未段或偶數未段反轉,在行相加來取得其bucket address,這種改良式的作法我們稱為(邊界摺疊法 folding at the boundaries)。

請看下列的說明:

11-2-4數位分析法

數位分析法適用於資料不會更改,且為數字型態的資料,在決定雜湊函數時先逐一檢查資料的相對位置及分布情形,將重複性高的部分刪除。例如下面這個電話表,它是相當有規則性的,除了區碼全部是07外,在中間三個數字的變化也不大,假設位址空間大小m=999,我們必須從下列數字擷取適當的數字,即數字比較不集中,分布範圍較為平均(或稱亂數高),最後決定取最後那四個數字的末三碼。故最後可得雜湊表為: