Hashtables（雜湊表）是什麼？
有些人可能會不曉得什麼是 Hashtables（雜湊表），沒關係這邊大概講一下 JS 的 Hashtables 是什麼，在 Objects and Hash Tables in Javascript 篇文章裡有一句話這麼說：
a particular data structure which utilizes javascript objects to create a numerically indexed structure to store key-value pairs
以上可以知道 Hashtables 在 JS 是由物件（objects）創造一個數值索引的結構來存 key 和 value。如果想深入了解的話可以看這篇：白話的 Hash Table 簡介。
什麼時候用 Hashtables 而不是 Array？
在大量資料中做查詢的時候就很適合用 Hashtables。
這邊我用維基百科上『最暢銷專輯及歌手』，來說明什麼時候該用 Hashtables 而不是 Array：
我們要做的是把這些資料都先給存起來，之後查詢任何一位歌手的專輯銷量。假設我們想要知道 Rolling Stones 專輯銷量多少時，我應該要很快地得到 89.5 這個數字。
接下來我們各別用 Array 和 Hashtables 看看如何做查詢這件事。
Array
如果我想要儲存資料在 array 中，JS 做法會像以下這樣：
這邊注意到我們 push 到 myData 陣列中的每一筆資料都用 array 給包住，這樣我們才能明確知道哪個歌手的銷售量是多少，執行完後我們就得到了一個二維陣列。
儲存資料是我們要做的一件事情，但真正重要的是我們想要輕鬆的找到銷售量，接下來我們用以下這段程式碼來取得目標歌手的專輯銷售量：
這邊注意到，我們使用 map 來歷遍陣列中的每個項目，並用 find 檢查陣列的 index 0（歌手名）是否與我們要查找的歌手相同，如果相同的話就 return 出該歌手的專輯銷售量。
用以下這張圖來看，我們有一個陣列，其中包含長度為 n 的陣列，TARGET_ARTIST 就在這個陣列中的某個地方
因為 map 這個方法是從陣列索引 0 開始迭代，並用 find 找符合條件式的值，所以如果我們不知道 TARGET_ARTIST 在陣列哪裡並想找到它，則需要從陣列的開頭開始找，然後遍歷每一項，並檢查其內容是否與 TARGET_ARTIST 值匹配，
如果 TARGET_ARTIST 位於陣列的開頭，則不會有太多的項目要經過，從而可以快速找到目標。如果陣列長度不長，剛好 TARGET_ARTIST 在陣列的末尾也不會花太多的時間，但設想一下這個陣列長度 n 如果是一萬呢？
平均而言，我們在陣列查找的時間與陣列長度成正比，JS 又是單執行緒所以在查找陣列的時候畫面就會卡住，效能會因此受影響。
Hashtables
現在我們來看看 Hashtables 會是什麼樣的清況，跟之前一樣先把資料存起來然後再做查找：
這邊建立一個空物件 myData ，在這個物件裡我們用歌手名當作 properties（或稱 keys），用專輯銷售量當作 value，取得指定的歌手專輯銷量，我們要做的就是傳入 property（歌手名）到 myData 物件中：
console.log(myData["ABBA"]); // 54.4我們只要呼叫 myData["ABBA"] 電腦就會幫我們計算出 54.4，所有要點就是在這，這個方式簡潔又簡單，但這個背後的運行原理是非常複雜的。
這裡用簡化的圖來表示雜湊表:
當要加入資料到 hashtable 時，需要明確的指定 key 和 value ，其實就是普通的把值存入到物件裡而已：
myData[“Pink Floyd”] =”110.1";上面這個例子的 key 是 “Pink Floyd”，而 value 是 110.1 ，當 hashtalbe 看到 key 的時候，會把 key 的值丟進一個程序叫 hashing，之後從這個 hashing function 裡 output 出一個編號，這個編號表示我們 value 所要存進 hashtable 裡的位置。
如果想從 hashtable 裡取值的話，所要做的就是提供我們創建時同樣的 key 就好了，當 hashtable 看到這個 key 時 hashing function 會回傳出和創建時一模一樣的編號（儲存的位置），我們就可以藉由這個編號快速的找到 hashtable 裡的值了。
不像陣列，並不需要歷遍整個 hashtable 來找值，因為 hashing function 幫我們把 key 給計算好回傳出它的索引號，所以 hashtable 才能那麼快地知道要檢索該值的位置。
總結
下面這個表格是總結 hashtables 跟 arrays 的 memory 和 performance 特徵：
以效能的觀點來看，hashtable 完全大勝，hash function 可確保為相同的 key 回傳相同位置，所以存入、查詢、刪除的時間複雜度都只花了常數的時間。
Arrays 沒辦法有這樣的效能，如果知道我們要取的 item 索引位置，則可以立即的取得 value，但幾乎都是不會知道索引位置，因此都會用任何方式來掃描陣列，所以這就逐漸的耗掉了很多時間在這個地方上面。
當然不是所有事情都是要與效能有關，有時候我們可能要對陣列裡的每一個 item 做些處理，這個時候 hashtables 就沒辦法做到了。
這裡有篇關於什麼情境用 hashtables 不優的討論串也可以看看。
參考資料：
