[心得] 圖解演算法 Hash Search有這麼快？

[uopsdod (pcman)]

【圖解演算法教學】

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

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

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

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

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

影片章節含有：

00:00 開頭
00:02 Linear Search
00:58 Binary Search
02:38 Hash Search
04:38 結尾

[更新2020.11.25]
感謝版友們提供的建議，的確有地方我可以改進，這邊直接幫大家整理出重要內容：

Linear Search : BigO(n)
Binary Search : BigO(n) ~ BigO(log(n))
Hash Seach    : 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/Tech_Job/M.1606205251.A.88E.html
推 yuci: 空間換時間，跟我們肝換錢一樣
噓 louisnight: std都寫好寫滿了
→ ckvir: 講的沒有很深，建議看 wiki
推 leo0519: unordered_map :
推 Dukkha: 感謝分享  做的很好懂 很棒
推 GGFACE: 讚 訂閱 分享
噓 zebracoco: 搜尋了id,相似東西一直重複po,洗文章?
推 nikolas: 奇怪 有人願意分享 不想看也不必要噓吧 是生活很不順嗎?
→ yolasiku: 想來這騙流量膩 可惜我一次都沒點進去過
推 cytochrome: 即使洗流量也無所謂，這種東西可以作為科普的入門阿，
→ cytochrome: 如果什麼東西都說一次就會了，老師存在的價值就沒那麼
→ cytochrome: 重要
推 MrBigTree: 上面真的一堆自覺很懂就不想複習的人呢
推 Dukkha: 科普的東西很好啊 多讓台灣人瞭解科普知識是好事。 點一
→ Dukkha: 次人家也賺不到0.1元
噓 zebracoco: 有人家裡不順就說人不順，家裡有人掛了嗎？
→ DrTech: 如果要傳遞知識，為什麼不把內容直接放在這篇文章，最後再
→ DrTech: 補充連結，達到傳遞與導流雙重目的。而是這篇只作為導流，
→ DrTech: 不順便放知識呢。建議原PO思考一下，達到目的有時有更好的
→ DrTech: 方法。不要只學那些低級的導流方法。
→ DrTech: 另外binary search與hash適用時機不同，標題過度誇張，講
→ DrTech: 的好像binary search很落後一樣，也讓人有不專業，或只為
→ DrTech: 了賺錢的觀感。建議以後也可更聰明的表達，讓自己更專業。
→ DrTech: 總覺得這些教學文用意良好，只是被一些低級的媒體影響了傳
→ DrTech: 遞知識的方式，蠻可惜的。
→ DrTech: 最後讀者的定位也很重要，想清楚這些內容誰看，自己與讀者
→ DrTech: 的價值會最大化呢。這時候內容的品質，以及引流的channel
→ DrTech: 會更精準，少了很多負面觀感。
→ DrTech: 期待更好的內容，真的。
推 labbat: 有辦法用正反器兜出來
推 Dukkha:  有時候做影片比較好懂 文字沒這麼好懂 這種艱澀知識類的
→ Dukkha:  根本賺不到錢 真的沒必要這麼嚴苛  台灣網紅一堆垃圾影
→ Dukkha: 片都幾百萬點閱 不是對台灣更糟嗎
→ loadingN: 樓上說奶台是垃圾？？？？
推 Dukkha: ........ 有個彈鋼琴沒露臉的居然1200萬點閱...
※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:10
※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:52
※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:05:56
→ DrTech: 感謝原PO,的站內信回覆，真的是有心吧事情做得更好的人，
→ DrTech: 謝謝
推 ken771209: 推
推 RedDracula: 噓的有什麼問題？不想看就滾
推 jcaosola: 下這個標題大概不知道codeforces有很多題目
→ jcaosola: 用hashmap會 timeout 用treemap反而可以AC
推 stosto: 這個去軟體版比較合適吧
噓 jpopaholic: 很簡單啊，因為這版叫tech job版，不是soft job 也不
→ jpopaholic: 是 student 版
→ jpopaholic: 發錯位置當然要噓
推 yamakazi: map: 紅黑樹（二元搜尋樹的一種特例
→ yamakazi: unordered_map: hash,使用上不需要知道次序的建議選第二
→ yamakazi: 種
→ yamakazi: 第一種比較快但佔空間
→ bitcch: 說真的 講的太淺 大概是給高中生認識計概的程度
噓 j0958322080: 衝流量啊嘻嘻
噓 zebracoco: 板主不處理這種和本板無關的文，到時候就一堆商業心得
→ zebracoco: 分享廣告文洗板
噓 zebracoco: 你要創業那就po在創業板，po在這是在欠噓？
推 arthas11: 難得看到教學型文章，給推
推 new122851: 這裡是半導體板
推 RestInPips: 推