【Algorithm】Hashing Search

使用雜湊法進行搜尋。

當初為了寫關聯法則的報告才第一次實際去研究這個題目，結果花了很久的時間還是沒有看懂其中的概念，最近從頭看一些基礎的資料結構與演算法的中文書，才發現其實概念明明很簡單啊！ 只能說要慎選入門知識學習的標的物，一開始就抱著英文猛嚼根本就是找自己麻煩而已。

關於這個題目，我想從範例反推觀念會比較簡單...

int[] ary = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };

首先這是我們要搜尋的目標陣列。

根據陣列的長度，求出大於此長度的最小質數。
※參數n值為陣列長度。

// 找出陣列大小所需的除數值數
private static int createMaxPrimeNum(int n) {
    if (primeCheck(++n))
        return n;
    else
        return createMaxPrimeNum(n);
}

// 確認輸入數是否為質數
private static boolean primeCheck(int n) {
    for (int j = 2; j * j <= n; j++) // 檢查到N的平方根即可
        if (n % j == 0) // 可被整除
            return false;
    return true;
}

我們要透過陣列值除質數取餘的方式將陣列中的元素寫入到下述的HashMap物件中

static HashMap<Integer, Integer> hashTable;

HashMap是屬於一種Collection，第一個泛型是索引(Key)，第二個是值(Value)，HashMap<索引, 值>。

// 建構雜湊表
private static void createHashTable(int[] ary) {
    hashTable = new HashMap<Integer, Integer>();
    int primeNum = createMaxPrimeNum(ary.length);
    for (int i = 0; i < ary.length; i++)
        hashTable.put(ary[i] % primeNum, i);
}

上面可以看到我寫入陣列值除質數取到的餘數為HashMap物件的索引，並以陣列索引為HaspMap物件的值。

重點來了，接下來我要搜尋比方值9在ary中的哪個位置的時候，我只需要

hashTable.get(9 % 該質數);

就可以取到9在ary中的位置了！ 相當於只要搜尋一次！

雜湊表(Hash Table)
說穿了這種方式就是用空間換時間，我在createHashTable中一次確認了所有陣列值跟陣列索引的關係，並將這份關係以對照表的形式儲存在記憶體中，使用上就可以省去搜尋比對的動作(時間)，而代價就是對照表的儲存成本(空間)。

雜湊函數(Hash Function)
雜湊函數的種類很多，它的目的是將輸入的值轉換成雜湊表的索引，讓搜尋時，目標值可以直接透過此函數轉換成雜湊表索引，在本例中即是陣列值除質數取餘為雜湊表索引，後將陣列索引存為雜湊表值，下次搜尋某陣列值，就可以同樣透過除質數取餘的方式得到該值的雜湊表索引，再透過雜湊表索引取得陣列的索引。

寫完才知道為什麼自己之前看那麼多文章都覺得很鬼打牆... 要文字表達這個概念還真的是蠻困難的...

ref：常見的雜湊函數與名詞 by.正修資管所-李春雄老師。