[心得] 圖解演算法 Hash Search使用優勢與時機

[uopsdod (pcman)]

【圖解演算法教學】

還在用古老的二元搜尋法？是時候跟上「Hash Search」 的車尾燈了！

封面圖：https://imgur.com/8GfYiTO

架構圖：https://imgur.com/SbC5IKY

在我們還沒學資料結構前，通常都用Linear Search找東西。
之後，我們學了二元樹，開始利用二元搜尋法，大幅提升搜尋效能。
然而，在演算法的世界中：
還有比Binary Search還快的東西，即是這次要介紹的「Hash Search」！

影片連結：https://bit.ly/2Uv2sBf



考量有人習慣文章閱讀，這邊也直接幫大家整理出重要內容：

Linear Search : BigO(n)
Binary Search : BigO(n) ~ BigO(log(n))
Hash Search    : BigO(n) ~ BigO(1)

可以看到，在最佳狀況下，Hash Search的效率是最快的，一步到位。
而之所以可以做到這樣的效能，是因為Hash Seach是by Index的搜尋方式。

比如說將 29 這個數字 經過hash之後：

9 = hash(29)

就能拿到 index 9 ，我們只要去查 array[9] == 29 是否正確，就能拿到結果。

當然，現實上沒這麼理想，會遇到「碰撞」，也就是不同來源數字hash到同一個index
這部分將在後續實作中介紹，這次主要是幫大家抓到使用「Hash Search」的誘因。

最後補充，Binary Search由於會先將資料排序，所以更適合用在「範圍搜尋」。

以上內容為影片重點萃取，有需要可以進一步參考影片完整介紹，
希望能多少幫到初學與需要複習的人！



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.110.156 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1606392612.A.369.html
※ 編輯: uopsdod (101.10.110.156 臺灣), 11/26/2020 20:10:31
推 qq3615: binary search應該可以保證最壞log(n)?
推 jobintan: 推個先，hash感覺像是用index找array的感覺。
推 b0920075: 他的二元樹是線性時間應該是指二元樹退化成鏈表的情況
→ b0920075: 吧，畢竟他也沒說是平衡二元樹
→ zo6596001: 很多語言都有內建這個，常見的就是dictionary或是c++
→ zo6596001: 的unordered_map
推 ucrxzero: 請問怎麼實作universal hash
推 ericerix: Binary search先排序，但排序過程最快nlogn，會優於
→ ericerix: linear嗎?除非之後還要找其他值才會快一些吧?
推 annheilong: 我覺得也可以提供「加入」的時間複雜度
→ leo08210917: 樓樓上 這邊純講搜尋吧
※ 編輯: uopsdod (101.10.103.34 臺灣), 11/28/2020 20:49:01
噓 gsrr: 無聊
噓 ruthertw: 看看苛妓版,對比這裡幾乎暖男,我還以為我來到心靈雞湯版