作者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/cn.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