The two most important days in your life are the day you were born and the day you find out why. -Mark Twain

#13 利用 Hash Table 來增加你的資料處理速度

還記得十多年前參加一個專案時,自己做了一件不好的資料處理方式,當時的我還不知道什麼是 hash function.在那時候專案部份的工作需要快速地處理大量的資料,透過資料庫連線讀取資料,然後再讀取相關的參考資料,再經過運算,最後把結果再寫回資料庫,如果你的方法是讀一筆寫一筆的話,那肯定會造成大量的資料庫 I/O,所以比較適合的方法是做批次的處理,也就是一次讀取某個足夠數量的資料筆數,處理完成之後再一次寫回去,這樣可以減少資料庫的 I/O,也可以讓程式運行起來速度可以快些.

以上的想法是可行的,但當時有一個小小的挑戰是有關參考資料,因為資料在運算的過程中必需依靠其他的數據才能計算,而這些數據多達 8 萬多筆資料,簡單的說,它是三個欄位構成,第一個是分行 ID,第二個是一個會計科目 ID,第三個資料值.

分行 ID會計科目 ID資料值

第一個 ID 和第二個 ID 是有相關的,它們之間是一個 many to many 的關係,也就是說當我要尋找資料值時,我必須要知道這兩個 ID 才行.當時專案所運用的伺服器還有相當足夠的記憶體空間,算一算資料量後,我就決定把那 8 萬多筆資料全部載入到記憶體,心裡想若一開始就把這些資料載入到記憶體之後,這樣資料在批次運算的過程中就可以直接到記憶體取得相關資料,如果一來更大大地減少資料庫的 I/O.心裡打的如意算盤正是如此,但當時我卻笨笨地用 List 結構把載入這 8 萬多筆資料到記憶體中,所以每當我要找資料時,我就用一個 for loop 把這個 List 結構從頭找到尾,只要前面兩個 ID 是相等時,就抓出第三個資料值.當時心裡,資料都在記憶體裡了,就算跑一個 for loop,以 CPU 對記憶體的速度來說也算是很快了.事後跑起來,運算速度也還是改進蠻多的,所以當時不但沒對 List 結構做改善,還一直以為自己做了一件相當聰明的事情.

後來當自己念了資料結構之後才發現到當初用 List 結構是多麼笨的事情,用時間複雜度的角度來看,那是一個 O(n),其實可以做到 O(1)的.那要怎麼做到 O(1)呢? 以這個例子來說的話,我們就要做一個 hash table 裡面包著一個 hash table.

以 Java 語法為例子的話,其資料結構定義就變成

HashMap< UUID, HashMap<UUID, Integer>>

所以在讀取的時候就變成 hashMap.get( 分行 ID ).get( 會計科目 ID ) ,如果這兩個 ID 都存在的話,則使用 O(1) 就可以得到資料值.雖然資料都載入到記憶體了,透過 Hash function 的運用,我們還是可以讓整個運算再快一點.

Hash 在一般的軟體專案中用途非常的廣泛,常常是我們利用空間來換取時間的最常見的手法,因此熟悉它並且善用它一定會對你的程式執行有極大的幫助.


Share: