那在了解Division Method之後，我們來練習基礎以字串為來源資料的Hash Function的實作應用：



「請將"mygod"這個字串轉成hash值？」



概念一：ASCII表，每個字母(ex. t)在程式中都代表著一個數字，比如說 'A' = 65, 'z' = 122



概念二：hash function要怎麼寫幾乎都行，但一個大目標是盡量地避免結果出現collision (也就是避免出現，不同input卻有相同output的狀況)

因此對於magic number通常會使用質數(ex. 31)；比如說，老師這邊想用以下邏輯將一個字串轉成hash值



hash("mygod") = m * (31⁴) + y * (31³) + g * (31²) + o * (31¹) + d * (31⁰)

➤ ➤  經過ASCII轉碼後，會變成

hash("mygod") = 109 * (31⁴) + 121 * (31³) + 103 * (31²) + 111 * (31¹) + 100 * (31⁰) = 104371024



1. 在上面這個hash function的實作中，老師為了區別出不同位置的字母，所以採用了31^x。

2. 另外為了區分出相同位置不同字母，老師再利用了ASCII表，將字母各自轉成不同的數字。


這邊有著一個有趣且重要的意義：我們將一個字串的「字母」+「順序」透過hash絞碎簡化成一個「數字」概念！



最後，根據我們的儲存空間限制，我們必須去限縮最後結果的「落點範圍」。



最現實的問題就是，每個資料型態都有他的儲存空間限制，也就是最大最小值。



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

所以，在整個計算hash的過程中，我們必須不斷的去進行限縮落點範圍，這個步驟我們主要目的：

➤  避免值太大或太小，超過資料形態的範圍 (keyword: overflow)



而根據前人經驗，我們大部分會使用 10^9+7 這個常數，做為我們的long的分群計算。

因此，如果我們從概念層面來看這次的hash整個過程，目前就會變成



module_number = 10^9+7 = 1000000007

hash("mygod") % module_number  = 104371024



然而關於%，還有一個地方要去顧：

在程式語言中，如果我們對一個負數 -5 % 3 = -2，結果是一個負數。

但這樣是不正確的，在數學上 -5 % 3 = 1，結果要是0以上，因此我們需要下列的module方法，來適應程式語言的數學特性：

如果 num % mod 之後是負的
所以 + mode 把它轉回正的
但如果 num % mod 原本就是正的，再 + mod 之後又有可能太大超出mod的範圍，所以再一次 % mod
private long mod(long num, long mod) {
    return ( num % mod + mod) % mod;
}
那麼，最後我們則有：



String source = "mygod";

int hashed_value = hash(source);

int hashed_moded_value = mode(hashed_value);



實作範例：

package com.Hash;

public class hash_basic {

    private static long hash(String str) {
        int magic_nubmer = 31; // you can pick other prime number
        int module_number = 1000000007;
        long hashedbucket = 0;
        for (int i = 0; i < str.length(); i++) {
            /** step01: move ALL left each round **/
            hashedbucket *= magic_nubmer; // leverage multiplication to show different char position
            hashedbucket = mod(hashedbucket, module_number);
            /** step02: add the newly right-most char **/
            hashedbucket += str.charAt(i); // leverage ASCII chart to convert char into int
            hashedbucket = mod(hashedbucket, module_number);
            /** stepall: use % to categorize & avoid overflow in every step **/
        }

        return hashedbucket;
    }

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

    public static void main(String[] args) {
        String str = "mygod";
        long hashed_moded_result = hash(str);
        System.out.println("result: " + hashed_moded_result); // 104371024
    }

}