[心得] 圖解演算法 Hash Search使用優勢與時機
【圖解演算法教學】
還在用古老的二元搜尋法?是時候跟上「Hash Search」 的車尾燈了!
封面圖:https://imgur.com/8GfYiTO
在我們還沒學資料結構前,通常都用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
推
11/27 02:52,
3年前
, 1F
11/27 02:52, 1F
推
11/27 08:00,
3年前
, 2F
11/27 08:00, 2F
推
11/27 10:45,
3年前
, 3F
11/27 10:45, 3F
→
11/27 10:45,
3年前
, 4F
11/27 10:45, 4F
→
11/27 13:01,
3年前
, 5F
11/27 13:01, 5F
→
11/27 13:01,
3年前
, 6F
11/27 13:01, 6F
推
11/27 13:43,
3年前
, 7F
11/27 13:43, 7F
推
11/27 15:25,
3年前
, 8F
11/27 15:25, 8F
→
11/27 15:25,
3年前
, 9F
11/27 15:25, 9F
推
11/27 16:18,
3年前
, 10F
11/27 16:18, 10F
→
11/28 01:36,
3年前
, 11F
11/28 01:36, 11F
※ 編輯: uopsdod (101.10.103.34 臺灣), 11/28/2020 20:49:01
噓
11/28 23:12,
3年前
, 12F
11/28 23:12, 12F