#12 利用 Hash Table 來改進 FindSum4()

在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：

當時我們用了 if ( i != j ) 的方式來做為一種 Optimization 的做法，當 ary 的元素越來越多時，整個程式的時間複雜度還是會往 O(n²) 靠近．理論上，這樣程式的時間複雜度還是 O(n²)．

先前的文章介紹了 Hash function 的好處，我們可以運用 Hash 的概念在這一個程式，

(以上是C#程式碼) 整個程式是 O(n).

從時間複雜度的角度來看，我們利用 hash 將程式的 O(n²) 變成 O(n)，而付出的代價是什麼呢 ? 付出的代價就是我們使用了 hash 在記憶體上的空間，最上面的程式是不需要有特別額外的記憶體空間，但第二個程式使用 hash 付出了 O(n) 的空間複雜度，這種用空間換取時間的情況在軟體的世界是非常常見的，因為在大部份的情況下我們比較在乎程式能在多久的時間內完成．

希望這個用 hash 來改進程式空間複雜度的例子能夠激發出你在日常工作上的想像力．

閱讀全文

#11 如何快速搜尋資料 - 利用 Hash function/Hash table

前面文章講了 binary search，這篇文章來介紹另一個好用而且非常常見的分類方法，它叫做 Hash．談到 Hash 時，通常包含兩個部份，一個是 Hash function，另一個是 Hash table．在業界的產品上，如 .Net/Java 等，都有提供業界標準的 hash function 以上一些 Hash table 的應用，如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用．首先，我們先談 Hash function．

Hash function 有一個很重要的特點是運算快速，那要多快呢? 最好是  O(1)，也就是指運算的速度不應該與輸入量的大小有關．換言之，你可以想像成你有兩個字串要輸入 hash function，其中一個字串很長，另一個字串很短，當你同時輸入到 hash function 運算時，得到結果的時間是一樣的．若用數學來表示，它就是 output = H (intput) ，其中 H 就是 hash function．

實行 Hash 的方法有無數種，你可以寫一個很簡單的．Hash 的實作要怎麼寫，這必須取決於你用 hash function 的目的是什麼．例如，你只是希望把一大堆的資料做一個簡單的分類，那麼你的 hash function 就可以用簡單的 mod (數學的求餘數) 來達成．舉個例子，有一些整數，而你要把他們分類到三個籃子裡，最簡單的方法就是求 3 的餘數，餘數如果是 0，那就放在第一個籃子，如果是 1，那就放在第二個籃子，以此類推．所以，你的整數數字經過 hash function 運算後就會被分成三個群組．今天若有人要找這些整數數字中有沒有 77 這個數字，那麼他只要到第三個籃子 ( 77 mod 3 = 2)，然後把第三個籃子裡面的數字全部找過一遍就知道有沒有 77了．以這例子來看，在尋找 77 的過程中，我們只需要尋找 1/3 的數字，另外有 2/3 的數字放在另外兩個籃子裡是不需要去找的，這等於加快了找資料的時間．所以，從這個例子來看，Hash 的分類法還蠻好用的，如果今天籃子夠多的話，這樣等於每個籃子裡面所儲存的數字越更少，因此找到數字的速度就會更快．

如果你的 hash function 的目的不像前面談的做分類這麼單純的話，則 hash function 的實作就得符合你的目的才行．在一般基本的加解密裡，多多少少會用到一點 hash function 的功能，如果此時 hash function 寫的太過簡單，這將造成加解密不夠 "強"．什麼樣才叫做夠 "強" 的 hash function 呢? 前面說的，output = H(input)，input 是你所定義的輸入範圍，可能是所有的字串，可能是所有的數字，也可能是所有的正整數．output 也是你定義的輸出範圍．通常來說一個夠強的 hash function 都會給出相同長度的 output．也就是說，H(1) = KI87CJDL , H(-100) = O9DI3KJ4 等等．Hash function 的目的並不是要加解密，output / input 的關係不用是一對一，所以一個 hash function 很有可能讓兩個或多個 input 得到相同的 output，例如 H(54839) = H(abcd)，只要你 "很難" 能找到兩個 input 會得到相同的 output，我們就可以稱這個 hash function 夠強，其中 "很難" 的意思就是你得花很多時間才能找到．

當一個 hash function 夠強時，它就具有單向和不可逆的特性，也就是說因為 "很難" 找到兩個 output 會得到同一個 input，因此當你看到 hash function 的 output 時，你就 "很難" 知道 input 會是什麼，就算你找到了一個，也不代表它就是目標 input，因為多個 input 會得到相同 output．"很難" 不代表不可能，只是很難而己．

你只要選到一個適合的 hash function，便能幫你處理很多的事情，適合不等於要夠強，主要符合你的需求即可，如前面說的資料分類功能．Java 和 .Net 平台都提供了業界裡常用的 Hash function，比如 MD5 或 SHA 演算法，提供了不同運算位元長度 ．而 Hash table 就是讓 input 經過 hash function 計算之後，讓 output 值做為放到籃子的依據，就像 Java 的 Hashmap 或 .Net 的 HashSet 之類的資料結構．如前面所說的，籃子越多，資料就能分更多的群組，所以當一樣數量的資料量要分類時，籃子越多的，裡面放的資料就更少．

接下來，你認為把 input 透過 hash function 得到 output 放到一個籃子裡，它的 Big O 怎麼算呢 ? 如果籃子都是空的，那就是 O(1)，因為此時只是一個簡單的數學運算，如前面提的求餘數 mod．這個運算跟資料數量大小沒有關係，如果你自己寫的 hash function 不是 O(1)，那就問題大了，因為這失去了 hash table 的意義．如果籃子不是空的呢 ? 這就要看籃子是用什麼資料結構做的．一般來說都會用 List，所以有一個新的資料放到籃子時，如果籃子已經有資料了，那麼新的資料就會被加到 List 的最前面，這動作也是 O(1)，所以使用 Hash table 時，平均來說，它的 Big O 就是 O(1)，也就是說當你使用 Hash table 時，平均來說，你找到資料是 O(1)，這個比用 Array 的 O(n) 來的快，也比用 Binary search (Olog(n)) 的方式要來的快．

閱讀全文

#10 資料結構 List

List 一般稱為 Linked List，這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素，這也稱為單向的 Linked List，如下圖所示：

這種單向的 List 應用在許多的情況下，例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念．每個 List 都是由一個或多個元素所組成，而每個元素都有相同的資料結構，以上圖為例，元素裡包含了一個 decimal 和一個 pointer，這個指標所代表的是下一個元素的記憶體位址．所以，如果你要找 List 裡一共有多少元素時，就必須要從第一個元素一直移動到最後一個元素才能得知這個 List 一共有多少的元素．如果要尋找 List 中是不是有某一個元存在，唯一的方法也是得從第一個元素開始，然後沿著 pointer 到下一個元素一直找到最後．以上的動作若用 Big O 來表達都是 O(n)，其中 n 是元素的個數．

顯然跟 Array 比起來，List 在數元素的個數和尋找元素都慢了許多，但 List 也有其優點，由於 List 裡的元素之間是透過 pointer 來指向下一個元素的位址，所以下一個元素的位址可以隨意變更．也就是說當你想要插入或刪除一個元素到 List，這動作就變得相當有簡單．

上圖就是一個刪除元素的結果，只要把 pointer 指向到下下一個元素時，略過中間那一個元素就可以了，最後記得把中間元素從記憶體中釋放即可．其程式碼看起來如下：

nextNode = currentNode.next;
currentNode.next = currentNode.next.next;
free(nextNode);

如果新加入一個元素的話，其程式碼看起來如下：

ListNode newNode = new ListNode();
newNode.next = currentNode.next;
currentNode.next = newNode;

以上兩段程式碼中的 next 就是 pointer 所指向下一個元素的記憶體位址．由於 List 中的元素在實體的記憶體或硬碟空間中不需要相鄰在一起，因此讓插入元素和刪除元素的動作變得簡單．

閱讀全文

#9 Binary search 的 Big O ?

這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?

我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．

Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成 50 個，再下一個就變成 25 個，以此類推．用數學的角度來看就形成了 2^y = n，其中 n 是資料輸入量，而 y 是尋找的次數，把式子轉變一下就形成了 y = log(n) ，其中這個 log 不是以 10 為基底，是以 2 為基底．所以，Binary search 的 Big O 就是 O(log(n))．

未來，寫程式的時候，如果你發現你的資料已排序好，那就記得多利用 Binary search 來做資料尋找，而不要一個一個找．因此，你也知道 O(log(n)) 的程式是比 O(n) 的程式還要來的快．

一般來說，寫 Binary search 有兩種寫法，一種是 recursive，另一種是 iterative.

Recursive :
          bool BSearch(int[] A, int target, int start, int end)
         {
             if (start < end) return false;
             int mid = (start + end) / 2;
             if (A[mid] == target)
                 return true;
             else if (target > A[mid])
                 return BSearch(A, target, mid + 1, end);
             else
                 return BSearch(A, target, start, mid - 1);
         }

Iterative :
         bool BSearch(int[] A, int target)
         {
             int start = 0;
             int end = A.Length - 1;
             while (start < end)
             {
                 int mid = (start + end) / 2;
                 if (A[mid] == target)
                     return true;
                 else if (target > A[mid])
                     start = mid + 1;
                 else
                     end = mid - 1;
             }
             return false;
         }

在沒有其他特別條件限制的情況下，Iterative 的寫法比較容易懂也比較好維護，同時也能避免 stack overflow (未來文章會再介紹) 的問題，所以多建議使用 Iterative 的寫法．

閱讀全文

#8 如何快速搜尋資料 - Binary Search

在以前還沒念電腦科學之前，對於快速搜尋這件事情完全沒什麼概念，唯一知道就是在一堆資料裡面一個一個找了，對於沒念過電腦科學的人來說，一個一個找是最直覺也是最簡單的方法．想像一個情況，一個 Array 裡面有一百個整數，假設每一個整數的值都不一樣，那麼我們想要知道這個 Array 裡面有沒有 77 這個數字，最直接的方法就是從 Array 的第一個元素找到最後一個元素，最好的情況是 77 這數字剛好在 Array 的第一個位置，那麼很快就可以找到了，若最壞的情況是 77 落在 Array 的最後一個位置或是 77 根本不在這裡面，那麼我們就必須從第一個元素找到最後一個元素．從我們之前講的 Big O 來看，這樣的搜尋所花的時間複雜度是 O(n)．這樣的情況有沒有可能更有效率呢?

如果我們今天很幸運得到一個已經排序好的 Array，那麼我們還需要從第一個找到最後一個嗎? 看來不一定喔! 想一想，如果是一個已經排序好的 Array，我們要從什麼地方開始找會比較好 ? 看看下圖的 Array，如果你要找 77 的話，你打算要怎麼找才能快一點．

在電腦科學的基礎課程中提供了一個簡單的方法，簡單的說就是用二分法來找，也就是 binary search．這個方法很簡單，一開始先從中間的位置開始找，以上圖的例子來看，中間是 55，如果我們要找 77 ，我們就知道 77 一定會在後面，不會在前面，原因就是這些元素都已經從小到大排序好了．接著，再用相同的方法，把後面的內容 (64,77,82,97) 再從中間找，而上述的例子剛好就找到了 77，所以一下子就找到了目標.

Binary search 是一個很簡單的概念，也是許多搜尋技術最基礎的想法．當我們再在一堆資料裡面去找某一個特定目標時，如果這一堆資料沒有特別的分類方法時，則很難產生出一個有效率的尋找過程，但如果這一堆資料經過了特別的分類方法，則就有機會產生出一個有效率的尋找過程．以 Binary search 來說，把資料排序好就是這個分類方法，而每次從中間元素開始找就是依這個分類方法而提出的有效率的尋找過程．

如果把層次拉到資料庫的產品，資料庫會有一堆的資料，而資料庫可以建立 B-tree，然後透過這個 B-tree 來尋找資料，所以資料庫引擎才能快速找到目標資料．B-tree 就是上述所說的分類方法，而在 B-tree 上游走就是上述的有效率的尋找過程．

如果把層次拉到像 Google 那樣的搜尋引擎，他們一定有很多的伺服器做索引之用，然後這些伺服器可以為同一個使用者要求來服務，所以當你輸入某個關鍵字時，才能如此快速得到結果，只不過這種層次的分類方法和有效率的尋找過程都是相當複雜的分散式程式．

閱讀全文

#7 系統上線了，我需要拿掉資料庫裡 foreign key 嗎?

前面講了一些基礎的內容，這篇文章來談談一些較實務面的經驗．

還記得許多年前在台北工作的時候，曾經在工作上發生一個經驗，當時我負責幫一個公司做一個小系統．這是一個簡單的小型商業系統，是一個 web application，在前端的部份分成兩項專案，其中一個專案是供給客戶登入各式各樣的資料，另一個專案是供管理者登入做資料的驗證與管理，而後端的部份是一個資料庫．在這個小專案裡，我負責前端客戶登入資料以及資料庫的設計，而管理者資料管理的部份是由該公司的工程師負責．

當整個專案在進行到後期的階段時，工程師們便開始為各項功能做驗證．在當時我並不清楚他們工程師負責的部份寫的如何，但是有件事情我倒是記得很清楚．某一天下午，該公司的工程師不知遇上了什麼技術上的問題，結果他們的主管就跑來找我，一付倚老賣老的姿態來跟我說話．這位主管說，我們過去做案子的情況都是這樣，當系統準備上線時都會把 foreign key 拿掉，以減少程式的執行時發生錯誤．老實說，我當時聽了他的說明，他只是要告訴我移除 foreign key 好讓他們那部份的程式不會出錯．當時我也沒深究他們工程師的程式是怎麼寫的，只是覺得奇怪．但畢竟那是他們的專案，既然他們都這樣要求了，所以就把資料庫裡相關的 foreign key 都移除了．

現在看看，你們公司是不是也會這樣呢 ? 是什麼原因造成你們會決定拿掉 foreign key 呢 ? Foreign Key 是維持資料一致性的其中一個方法，拿掉有什麼好處呢 ? 對資料庫引擎來說倒是變的比較輕鬆，因為某個欄位上如果有 foreign key 的限制，每當該欄位的資料在被修改時，資料庫引擎都得去檢查 foreign key 對應回去的那一個表格是不是有合法的資料存在．如果資料不存在的話，資料庫引擎就必須產生錯誤訊息．因為資料庫引擎做的事變少了，因此完成指令的時間將會變快，這樣聽起來好像蠻不賴的．但如果這麼不賴的話，何必要有 foreign key 的存在呢 ? 前面曾提到，foreign key 是維持資料一致性的其中一個方法．如果你把 foreign key 拿掉了，也就代表資料庫引擎不會為你檢查資料是否合法，所以如果程式撰寫或是邏輯上處理有問題時，就很容易造成幽靈資料．所謂的幽靈資料就是在 foreign key 的欄位上的資料在對應的 primary key 欄位上沒有這樣的資料，因此當你要做 table join 時，那些資料便不會被 join 起來．用一個簡單的例子來看: 資料庫中有兩個表格，第一個表格是客戶表格，第二個表格是訂單表格．客戶表格的 primary key 是 Customer ID，訂單表格的 primary key 是 Order ID，而這兩個表格有一個關聯就是透過 Customer ID 形成的，因此訂單表格的 Customer ID 就是客戶表格 Customer ID 的 foreign key．

Customer ID	Customer Name
A1	客戶一
A2	客戶二

Order ID	Customer ID
O1	A1
O2	A3

如果今天把這訂單表格 Customer ID 的 foreign key 拿掉之後，那就表示當你在新增或更新訂單表格時，Customer ID 並不會受到客戶表格的 Customer ID 所限制，因此就合法可以出現 A3 的客戶編號在訂單表格裡，但麻煩的是客戶表格裡沒有 A3 編號存在，所以訂單編號 O2 就變成了所謂的幽靈資料．

當然，以上是很簡單的例子，你覺得不可能發生，但如果專案夠大，開發的工程師比較多而且整個團隊沒有一個有紀律的開發方法時，當你把資料庫的 foreign key 拿掉，那麼發生幽靈資料的機率便會很高．這時候影嚮的可是整個專案的品質，甚至會影響到客戶的信任度．所以，到底該不該把 foreign key 拿掉，我能給的建議就是，應該是去查看為何程式會出錯，而不該把錯怪在 foreign key 上．只要 database schema 的設計是合理的，foreign key 就不應該出錯，而是程式的邏輯有問題．因此，我還是建議你別拿掉 foreign key，因為我覺得資料庫裡的資料一致性比拿掉 foreign key 所獲得的效能提升還來的重要．

閱讀全文