作者uopsdod (pcman)
看板Soft_Job
标题[心得] 图解演算法 Hash Search使用优势与时机
时间Thu Nov 26 20:10:06 2020
【图解演算法教学】
还在用古老的二元搜寻法？是时候跟上「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://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1606392612.A.369.html
※ 编辑: uopsdod (101.10.110.156 台湾), 11/26/2020 20:10:31
1F：推 qq3615: binary search应该可以保证最坏log(n)? 11/27 02:52
2F：推 jobintan: 推个先，hash感觉像是用index找array的感觉。 11/27 08:00
3F：推 b0920075: 他的二元树是线性时间应该是指二元树退化成链表的情况 11/27 10:45
4F：→ b0920075: 吧，毕竟他也没说是平衡二元树 11/27 10:45
5F：→ zo6596001: 很多语言都有内建这个，常见的就是dictionary或是c++ 11/27 13:01
6F：→ zo6596001: 的unordered_map 11/27 13:01
7F：推 ucrxzero: 请问怎麽实作universal hash 11/27 13:43
8F：推 ericerix: Binary search先排序，但排序过程最快nlogn，会优於 11/27 15:25
9F：→ ericerix: linear吗?除非之後还要找其他值才会快一些吧? 11/27 15:25
10F：推 annheilong: 我觉得也可以提供「加入」的时间复杂度 11/27 16:18
11F：→ leo08210917: 楼楼上 这边纯讲搜寻吧 11/28 01:36
※ 编辑: uopsdod (101.10.103.34 台湾), 11/28/2020 20:49:01
12F：嘘 gsrr: 无聊 11/28 23:12
13F：嘘 ruthertw: 看看苛妓版,对比这里几乎暖男,我还以为我来到心灵鸡汤版 02/23 13:30