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