Hash Function實作主要有三種：

「Division Method」
「Multiplication Method」
「Mid-Square Method」
這三種實作，根據「隨機結果」程度排序的話(小->大)：

Division Method < Multiplication Method < Mid-Square Method



然而，在解題應用上，Division Method是更實用的，因為他能根據客製化邏輯，很彈性的來調整我們的hash function，非常好用。(後續單元馬上就會介紹字串的實際應用，重要觀念)

也因此，老師不建議大家花太多時間去深入了解，為什麼Multiplication Method、Mid-Square Method比較厲害，

因為這屬於學術領域，與我們需要的太遙遠；我們身為開發者只需知道他們隨機性大小關係就很夠用了。



什麼是 Division Method？



hash(a) = a % b = c

Ex. hash(29) = 29 % 10 = 9



輸入：a

資料範圍/分組：b

輸出： c



其實這個式子，就是一個hash function的核心實作概念。

其中%(取餘數)的運用有著兩種意義：



1. 將資料限縮在特定範圍內

2. 將資料進行分群



比如說在JAVA中，long的範圍是 -2⁶³ ~ (2⁶³ - 1)，如果我們hashed value大於小於這個值，那麼就會出現計算失真，也就是錯誤。

因此，我們需要透過%取餘數的方式，來限縮我們最終資料的落點。



什麼是 Multiplication Method？(非重點內容，可有空時再回頭看就好)



hash(a) = n (a * b % 1) = c

Ex. hash(29) = 100 * (29 * 0.61 % 1) = 69



輸入：a

資料範圍/分組：n

隨機常數：b

輸出：c



如果我們要更理解這個方法，可以再拆解成下列這樣：

STEP01：拿到某個隨機產出的小數點值：(29 * 0.61 % 1)

STEP02：根據資料範圍/分組條件，將小數點值呈上n：100 * (29 * 0.61 % 1)



而之所以 Multiplication Method 能產生更隨機hash值，是因為有更多的數字在乘法的時候，「交錯參與」到結果的每個數字的產生。

但 Division Method 卻只是取餘數作為最後結果，相對隨機性小了許多。



什麼是 Ｍid-Square Method？(非重點內容，可有空時再回頭看就好)



hash(a) = (a * a) % b1 / b2 = c

Ex. hash(29) = (29 * 29) % 100 / 10 = 4



輸入：a

去頭常數：b1

去尾常數：b2

輸出：c



如果我們要更理解這個方法，可以在拆解成下列這樣：

STEP01：拿到輸入值的平方：(29 * 29) = 841

STEP02：將平方值去頭去尾，取中間數字最為最後hash值：(29 * 29) ％ 100 / 10 = 4



而這種取平方、再取中間數字的方式，又比 Multiplication Method的隨機性更高，因為更多的數字「交錯參與」到最終結果的每個數字的產生。(越來越學術了)



結論：

不論是用哪種方式實作 Hash Function，我們的目的都是相同的：

1. 盡最大可能避免「碰撞」的發生，因此結果值越隨機越平均則越好

2. 限縮最終結果值的範圍，避免超出儲存空間限制

3. 對最終結果值進行分群



最後，老師這邊還是提供三種hash function完整的程式碼實作，給大家參考(一樣，建議大家有空再看後面兩種就好，不是重點)：

package com.Hash;

public class hash_methods_all {

    private static long hash_division(Long input_value) {
        int modulo_number = 1000000007;
        return mod(input_value, modulo_number);
    }

    private static long hash_multiplication(Long input_value) {
        long range_limit = 1000000007;
        double random_a = 0.618033;
        double fraction = input_value * random_a % 1;
        return (long) (range_limit * (fraction));
    }

    private static long hash_midsquare(Long input_value) {
        // ___XXX___ // pick 4th~6th numbers (from right to left)
        Long input_value_squared = input_value * input_value;
        Long hashed_output = input_value_squared % 1000000; // 去頭
        hashed_output = hashed_output / 1000; // 去尾

        return hashed_output;
    }

    private static long mod(long n, long m) {
        return (n%m + m) % m;
    }

    public static void main(String[] args) {

        Long input_value = 1234567890L;
        Long hashed_output = hash_division(input_value);
        System.out.println("result(division): " + hashed_output); // 104371024
        hashed_output = hash_multiplication(input_value);
        System.out.println("result(multiply): " + hashed_output); // 760370021
        hashed_output = hash_midsquare(input_value);
        System.out.println("result(midsquare): " + hashed_output); // 52 (out of 15241578750190"52"100)

    }

}