看板 Soft_Job
標題
[心得] 圖解演算法 Hash Search使用優勢與時機
作者 uopsdod
時間 Thu Nov 26 20:10:06 2020
人氣 推:6 噓:1 留言:12
分享給朋友
【圖解演算法教學】 還在用古老的二元搜尋法?是時候跟上「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://www.ptt.cc/bbs/Soft_Job/M.1606392612.A.369.html ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/26/2020 20:10:31
qq3615: binary search應該可以保證最壞log(n)? 11/27 02:52
jobintan: 推個先,hash感覺像是用index找array的感覺。 11/27 08:00
b0920075: 他的二元樹是線性時間應該是指二元樹退化成鏈表的情況 11/27 10:45
b0920075: 吧,畢竟他也沒說是平衡二元樹 11/27 10:45
zo6596001: 很多語言都有內建這個,常見的就是dictionary或是c++ 11/27 13:01
zo6596001: 的unordered_map 11/27 13:01
ucrxzero: 請問怎麼實作universal hash 11/27 13:43
ericerix: Binary search先排序,但排序過程最快nlogn,會優於 11/27 15:25
ericerix: linear嗎?除非之後還要找其他值才會快一些吧? 11/27 15:25
annheilong: 我覺得也可以提供「加入」的時間複雜度 11/27 16:18
leo08210917: 樓樓上 這邊純講搜尋吧 11/28 01:36
※ 編輯: uopsdod (101.10.103.34 臺灣), 11/28/2020 20:49:01
gsrr: 無聊 11/28 23:12
分享給朋友
政治八卦 男女情感 投資理財 生活其他 返回Soft_Job看板

全看板熱門文章

Soft_Job 的熱門文章

分享給朋友
政治八卦 男女情感 投資理財 生活其他 返回Soft_Job看板