Python教程网
--左手Python,右手AI!

数据结构 | 你不得不了解的哈希算法 !

本文原创首发于公众号:小詹学Python

今天来聊一聊数据结构中的哈希表!

⒈哈希是什么 ?

问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?

当然是按姓名搜索呀 !(假装你有小詹电话号码~)言归正传 ,那你能想到这和哈希表有异曲同工之妙嘛 ?

哈希表简单说可以理解成一个映射关系 ,类似 python 语法中字典的键值对 。根据键(Key)而直接访问在内存存储位置的数据结构。

将任意长度的二进制值串映射为固定长度的二进制值串 ,这个映射的规则就是哈希算法 。原始数据映射得到的二进制值串就是哈希值 。

回到通讯录的例子 ,是不是可以类比 ? 电话号码是原始数据 ,根据哈希算法(这就是你自定义的规则)存储为通讯录备注 。严格来讲二者是有区别的 ,只是为了便于理解 ,若举例不当 ,杠精读者轻喷 。

一个优秀的哈希算法主要有以下几点特征 :
单方向推导 ,不能从哈希值反向推导出原始数据 ,或者说很困难 。
对输入敏感 ,原始数据的微小变化会导致哈希值的大差异 。
散列冲突小 ,不同原始数据得到相同哈希值的概率小 。其实最好是避免 ,但是诸如 MD5 这种也难以彻底避免 ,所以只说尽可能小 。
执行效率高 ,即使是较长的文本 ,也能快速计算出哈希值 。

⒉哈希算法有何用 ?

一般而言 ,算法或产品的使用往往取决于特征 。所以根据上文的特征不难想到一些应用如下 。

安全加密

因为优秀的哈希算法具有单方向推导和散列冲突小两个特征 ,这就决定了用来进行安全加密具有很好的应用 。

相信你一定听过 MD5(MD5 Message-Digest Algorithm ) 和 SHA(Secure Hash Algorithm)吧 ,这就是两个常用于安全加密的哈希算法 。

数据结构

其实还有很多应用与安全加密类似 ,比如数据校验之类的 ,都是利用单向性和冲突小特性 ,就不赘述了 。

其实哈希算法在数据结构中用于查找是一个非常不错的方法 ,可以快速定位查找到想要查找的数据信息 。这一用法在刷 LeetCode 题的时候遇到的非常多 !

⒊哈希算法刷题

K数之和

Leetcode第一题就是两数之和 ,后边又有三数之和 、四数之和 ,其实 K 数之和原理类似 。

以两数之和为例 ,除了简单暴力的遍历方法 ,哈希算法能够极大的提高解题效率 !具体参照第一题推文的第二种解法 :

LeetCode | No.001 两数之和

LeetCode | No.015 三数之和

模式匹配

模式匹配问题比较经典 。最简单的举例 :数字串「 1 2 1 2 」应该对应英文「 one two one two 」。

现在如果给定一个模式(数字串)和一个输入(英文),要你写代码实现判断是否模式匹配 ,你该怎么做呢 ?

其实这就可以考虑使用哈希算法实现了 ,python 中的字典有个键值对 ,其实有些类似 ,这里小詹给出思路 ,不分享代码 。(原文是留言区作答,答对有奖,点击这里跳转原文)

思路如下

  • 首先对输入的英文串分割 ,可以用 input.split(‘ ‘) 方法 。
  • 建立哈希表存储数据 ,这里友情提醒下可以建立多个哟 。
  • 从给定模式逐一循环判断 。单次判断逻辑如下列出 。
  • 首先判断当前位置的模式(pattern)是否初次出现 ,如果不是第一次出现 ,则说明有一个哈希值与之相对应 ,判断 input 对应位置是否与该哈希值一致 ,如果不一致则直接返回 false ,肯定不匹配 。
  • 如果当前模式是第一次出现 ,先不急着直接加入哈希表 ,还需要判断对应位置的 input 英文单词是否是其他模式的哈希值 ,如果是说明之前已经和别的模式匹配了 ,不能反复匹配 ,返回 false 。
  • 如果当前位置的模式是第一次出现且对应的 input 也没有和别的模式匹配过 ,则二者作为一个键值对存入哈希表 。
  • 如果直到循环结束没有返回 false 说明完全匹配 ,返回 true 。

祝你写出完美的代码噢 !增加这个环节主要是考虑到这个刷题系列烧脑 ,参加互动的人不多 ,当然小詹写的不够好也是一方面 。总之 ,希望通过这个有奖互动增加大家参与度 !

最后,本文首发于公众号:小詹学Python。欢迎扫码关注!

赞(5)
未经允许不得转载:Python教程网 » 数据结构 | 你不得不了解的哈希算法 !
分享到: 更多 (0)

评论 111

  1. #1

    These contaminants are usually found in the vapors generated by
    the interaction between the beam and the target also called the plume.
    generic viagra online (saleviabuy.com) how to get viagra

    匿名4个月前 (10-30)回复
  2. #2

    We were all in shock sine she had no symptoms of sickness but she laid down went to the bathroom in place and a good amount
    of blood came out of her butt and she died in a mater of minutes.
    what does a generic viagra pill look like
    what is the generic for viagra

    匿名4个月前 (11-05)回复
  3. #3

    viagraonline viagra buy what ingredients inside viagra

    匿名4个月前 (11-16)回复
  4. #4

    viagra seus efeitos colaterais viagra wo bekomme ich es her czym jest viagra

    匿名4个月前 (11-17)回复
  5. #5

    viagra herbal supplements viagra substancia ativa viagra plagiat

    匿名4个月前 (11-18)回复
  6. #6

    quien debe recetar viagra buybuyviamen.com contraindicaciones del consumo de viagra

    匿名4个月前 (11-19)回复
  7. #7

    women viagra for sale wowviaprice.com prices for viagra

    匿名3个月前 (11-19)回复
  8. #8

    viagra discounr https://paradiseviagira.com/ viagra triangle te

    匿名3个月前 (11-19)回复
  9. #9

    Men viagra https://lightvigra.com female viagra uk pharmacy

    匿名3个月前 (11-21)回复
  10. #10

    viagra sales buy viagra medicine online india can you buy viagra over the counter in europe

    匿名3个月前 (11-21)回复
  11. #11

    Can you buy viagra in australia https://miraclevigra.com/ viagra over the counter uk

    匿名3个月前 (11-21)回复
  12. #12

    Viagra discounts hopeviagrin.com
    viagra from mexico to usa

    匿名3个月前 (11-21)回复
  13. #13

    viagra sold at stores viagra cega viagra uk lloyds

    匿名3个月前 (11-25)回复
  14. #14

    how to get viagra without a prescription generic viagra online for sale where can i get over the counter viagra

    匿名3个月前 (11-25)回复
  15. #15

    viagra tablet 25 mg buy viagra with paypal australia viagra professional pfizer

    匿名3个月前 (11-26)回复
  16. #16

    generic viagra coming soon response time of viagra robber viagra salon

    匿名3个月前 (11-27)回复
  17. #17

    viagra 100 mg tablet price how to get generic viagra online can i buy viagra

    匿名3个月前 (11-27)回复
  18. #18

    law essay writing service help with college homework assignments essay written in apa

    匿名3个月前 (11-29)回复
  19. #19

    essay 3rd grade essay writing scaffold writing a conclusion for a research paper

    匿名3个月前 (11-29)回复
  20. #20

    i should do my homework physical science homework helper essay grabber

    匿名3个月前 (12-01)回复
  21. #21

    helping the poor essay writing a case study paper thesis help

    匿名3个月前 (12-01)回复
  22. #22

    Buy an essay cheap https://buyessayhelpbtg.com
    buy essays online for college

    匿名3个月前 (12-01)回复
  23. #23

    hire someone to do my homework essay writing on my mother essay vikings

    匿名3个月前 (12-02)回复
  24. #24

    writing a medical research paper writing biography college scholarship essays

    匿名3个月前 (12-02)回复
  25. #25

    essay buying do my excel project research proposal dissertation

    匿名3个月前 (12-02)回复
  26. #26

    recommendation for research paper best college paper writing service college entry essays

    匿名3个月前 (12-03)回复
  27. #27

    wholesale viagra cialis cialis black cialis mastercard

    匿名3个月前 (12-09)回复
  28. #28

    buy cialis via pay pal cialis windsor canada cialis nz online

    匿名3个月前 (12-10)回复
  29. #29

    cialis and alcohol symptoms cialis eu buy generic cialis online

    匿名3个月前 (12-10)回复
  30. #30

    200 mg cialis cialis soft tabs canadian pharmacy grapefruit cialis

    匿名3个月前 (12-12)回复
  31. #31

    xanax with viagra i need viagra viagra generic cost

    匿名3个月前 (12-12)回复
  32. #32

    viagra time to work viagra price per pill viagra online gr

    匿名3个月前 (12-13)回复
  33. #33

    viagra on line where to get viagra in melbourne buy viagra insurance

    匿名3个月前 (12-13)回复
  34. #34

    viagra pharmacy paypal viagra uk advice generic viagra

    匿名3个月前 (12-14)回复
  35. #35

    online viagra in united states viagra prices viagra purchase online usa

    匿名3个月前 (12-14)回复
  36. #36

    I’m extremely impressed with your writing skills as well as with the layout on your weblog.

    Is this a paid theme or did you modify it yourself?

    Either way keep up the excellent quality writing, it’s rare to see a great
    blog like this one these days.

    my page … gale

    匿名3个月前 (12-15)回复
  37. #37

    Thank you for the good writeup. It in fact was a enjoyment account it.
    Glance complicated to far brought agreeable from you! By the way, how can we keep up a
    correspondence?

    Have a look at my website; sex1t

    匿名3个月前 (12-15)回复
  38. #38

    Excellent way of explaining, and nice article to take facts regarding my presentation subject matter,
    which i am going to deliver in school.

    Here is my site: desi

    匿名3个月前 (12-15)回复
  39. #39

    Excellent blog here! Additionally your web site
    a lot up fast! What host are you the usage of? Can I am getting
    your affiliate link on your host? I want my web site loaded up as quickly as yours lol

    my web page sil

    匿名3个月前 (12-15)回复
  40. #40

    After I originally commented I seem to have clicked the -Notify me when new comments are added-
    checkbox and now whenever a comment is added I get 4 emails with the exact same
    comment. Perhaps there is a means you are able to remove
    me from that service? Thanks a lot!

    my web page: se

    匿名3个月前 (12-15)回复
  41. #41

    I’m not sure why but this blog is loading incredibly slow for me.
    Is anyone else having this problem or is it a issue on my end?
    I’ll check back later and see if the problem still exists.

    Also visit my web blog … in

    匿名3个月前 (12-15)回复
  42. #42

    Hi there! I just wanted to ask if you ever have any issues with hackers?

    My last blog (wordpress) was hacked and I ended up losing
    several weeks of hard work due to no backup. Do you have any solutions
    to protect against hackers?

    Here is my web-site: sex1team1teat1ted1teecer2gerlsstudentssexcom1teem

    匿名3个月前 (12-15)回复
  43. #43

    My brother suggested I might like this blog. He used to be totally right.
    This put up truly made my day. You cann’t believe just
    how a lot time I had spent for this info! Thanks!

    My web page … sex1staimsx1stb1stblad1stbrowser1stclasstube1stcom1stde1stdp1stim1stime1stime

    匿名3个月前 (12-15)回复
  44. #44

    Thanks for the good writeup. It actually was
    once a amusement account it. Glance advanced to far added agreeable from you!
    By the way, how can we communicate?

    Also visit my web blog :: video16

    匿名3个月前 (12-16)回复
  45. #45

    That is very interesting, You are a very professional blogger.
    I’ve joined your feed and stay up for in quest of extra of
    your excellent post. Also, I’ve shared your web site in my social networks

    my page; seeeex18

    匿名3个月前 (12-16)回复
  46. #46

    Hey There. I discovered your weblog using msn. This is a very well
    written article. I’ll be sure to bookmark it and come back to learn extra of
    your useful information. Thanks for the post. I will definitely comeback.

    Here is my website sal

    匿名3个月前 (12-16)回复
  47. #47

    I like the valuable information you provide in your articles.
    I’ll bookmark your weblog and test again right here regularly.
    I am relatively sure I’ll learn many new stuff right here!
    Good luck for the next!

    Review my website … or

    匿名3个月前 (12-16)回复
  48. #48

    I am regular reader, how are you everybody?
    This piece of writing posted at this website is genuinely fastidious.

    Also visit my webpage :: seal

    匿名3个月前 (12-16)回复
  49. #49

    I believe this is one of the such a lot vital information for me.
    And i’m satisfied studying your article. However wanna commentary on some common things, The website taste is great,
    the articles is in point of fact excellent : D. Just right task, cheers

    Here is my blog post; sex1staimsx1stb1stblad1stbrowser1stclasstube1stcom1stde1stdp1stim1stime1stime

    匿名3个月前 (12-16)回复
  50. #50

    Yesterday, while I was at work, my cousin stole my iphone
    and tested to see if it can survive a 25 foot drop,
    just so she can be a youtube sensation. My apple ipad is now destroyed and she has 83 views.
    I know this is entirely off topic but I had to
    share it with someone!

    Here is my web page: jabrjsti

    匿名3个月前 (12-16)回复
  51. #51

    First off I would like to say excellent blog!
    I had a quick question that I’d like to ask if
    you do not mind. I was curious to know how you center yourself
    and clear your mind prior to writing. I have had a tough time clearing my thoughts in getting my ideas out there.
    I do take pleasure in writing but it just seems like the first 10 to 15 minutes are generally wasted just trying to figure out how to begin. Any recommendations or tips?
    Thanks!

    Take a look at my blog bf

    匿名3个月前 (12-16)回复
  52. #52

    My partner and I stumbled over here by a different web address and thought I
    may as well check things out. I like what I see so now i
    am following you. Look forward to checking out your web page
    for a second time.

    Have a look at my blog student

    匿名3个月前 (12-16)回复
  53. #53

    Terrific post but I was wondering if you could write a litte more on this topic?
    I’d be very grateful if you could elaborate a little bit further.
    Many thanks!

    my web-site new1st

    匿名3个月前 (12-16)回复
  54. #54

    Thank you a bunch for sharing this with all people you actually recognise what you are talking about!
    Bookmarked. Kindly additionally discuss with my web site
    =). We can have a hyperlink exchange contract between us

    My web blog hd16

    匿名3个月前 (12-16)回复
  55. #55

    You should take part in a contest for one of the highest quality blogs
    on the internet. I’m going to recommend this website!

    My webpage :: peck18

    匿名3个月前 (12-16)回复
  56. #56

    viagra pasteque generique du viagra viagra avec ordonnance en ligne
    reconnaitre un homme qui prend du viagra

    匿名3个月前 (12-16)回复
  57. #57

    Интересные факты: гидра онион

    匿名3个月前 (12-17)回复
  58. #58

    viagra buy online viagra online paypal paiement price of viagra in india

    匿名3个月前 (12-17)回复
  59. #59

    viagra commande viagra 50 produits naturels pour remplacer le viagra
    ou peut on acheter du viagra sans ordonnance

    匿名3个月前 (12-17)回复
  60. #60

    mutuelle cialis prix du cialis en pharmacie en france comment acheter du cialis en belgique
    cialis 10mg ou 20mg

    匿名3个月前 (12-18)回复
  61. #61

    cialis copie cialis pas cher disponibilite du cialis generique en pharmacie
    comment utiliser cialis 10mg

    匿名2个月前 (12-19)回复
  62. #62

    prednisone taper dosage buy prednisone online canine lymphoma life expectancy prednisone
    how quickly does prednisone work for sinus infection

    匿名2个月前 (12-19)回复
  63. #63

    levitra price comparison levitra online viagra cialis or levitra reviews
    levitra side effects list

    匿名2个月前 (12-20)回复
  64. #64

    This is the right web site for anybody who hopes to find out
    about this topic. You know a whole lot its almost hard
    to argue with you (not that I actually would want to…HaHa).
    You certainly put a brand new spin on a subject that has
    been written about for ages. Excellent stuff, just
    wonderful!

    Look at my blog sex videos – spicytitties.com

    匿名2个月前 (12-22)回复
  65. #65

    Hello there, I found your web site by the use of
    Google at the same time as looking for a related
    matter, your web site got here up, it appears to be like good.

    I have bookmarked it in my google bookmarks.
    Hi there, simply changed into alert to your weblog via Google, and found that it
    is truly informative. I’m gonna watch out for brussels.
    I’ll appreciate should you proceed this in future.
    Numerous folks will probably be benefited from your writing.
    Cheers!

    My web site – sex videos – http://omapornsex.com

    匿名2个月前 (12-24)回复
  66. #66

    viagra laboratoire prix viagra vente de viagra en ligne
    quand faut il prendre le viagra

    匿名2个月前 (12-25)回复
  67. #67

    cialis prise acheter cialis generique en france cialis est il vraiment efficace
    pharmacie qui vend du cialis sans ordonnance en france

    匿名2个月前 (12-27)回复
  68. #68

    levitra or cialis levitra viagra vs cialis vs levitra price
    which is cheaper levitra or vigra

    匿名2个月前 (01-01)回复
  69. #69

    global pharmacy canada pharmacy near me best drugstore face moisturizer

    匿名2个月前 (01-09)回复
  70. #70

    24 hour pharmacy near me erectile best drugstore eye cream

    匿名2个月前 (01-10)回复
  71. #71

    ed pills that work quickly http://pharmacy-onlineasxs.com/ pharmacy today

    匿名2个月前 (01-11)回复
  72. #72

    best online pharmacy best drugstore moisturizer express scripts pharmacy

    匿名2个月前 (01-12)回复
  73. #73

    médicament viagra effet secondaire du viagra prix du viagra en pharmacie
    ou acheter du viagra homme

    匿名1个月前 (01-18)回复
  74. #74

    cialis levitra buy levitra best results with levitra
    what is the purpose of the drug levitra

    匿名1个月前 (01-20)回复
  75. #75

    cialis tarif prix du cialis en pharmacie ou commander cialis en ligne
    comment acheter cialis en ligne

    匿名1个月前 (01-23)回复
  76. #76

    mdma viagra viagra kaufen holland viagra wirkung wie lange
    wie hilft viagra

    匿名1个月前 (01-26)回复
  77. #77

    visual analysis essay essay reader william and mary supplement essay
    how to write a book title in an essay mla

    匿名1个月前 (01-28)回复
  78. #78

    This is a really good tip especially to those new to the blogosphere.
    Simple but very precise information… Appreciate your sharing this one.
    A must read article!

    Also visit my blog post :: cheap flights

    匿名1个月前 (01-31)回复
  79. #79

    I’m not sure why but this site is loading incredibly slow for
    me. Is anyone else having this problem or is it a problem on my end?

    I’ll check back later on and see if the problem still
    exists.

    Also visit my web page … cheap flights

    匿名1个月前 (02-01)回复
  80. #80

    WOW just what I was looking for. Came here by searching for cheap flights

    匿名1个月前 (02-01)回复
  81. #81

    These are actually enormous ideas in on the topic
    of blogging. You have touched some good things here. Any way keep up wrinting.

    My page … cheap flights

    匿名4周前 (02-02)回复
  82. #82

    Do you have a spam problem on this website; I also am a blogger,
    and I was wondering your situation; many of us have created some nice procedures and
    we are looking to swap techniques with others, why not shoot me an email if interested.

    Here is my web page cheap flights (tinyurl.com)

    匿名4周前 (02-02)回复
  83. #83

    Hi there! I could have sworn I’ve visited this web site before but after browsing through many of the posts I
    realized it’s new to me. Regardless, I’m definitely happy I discovered it
    and I’ll be bookmarking it and checking back often!

    Here is my blog post: cheap flights (tinyurl.com)

    匿名4周前 (02-03)回复
  84. #84

    prescription drugs prices online pharmacy without prescription sildenafil citrate

    匿名4周前 (02-05)回复
  85. #85

    motion sickness online pharmacy busted herbals

    匿名4周前 (02-05)回复
  86. #86

    viagra 25mg vs 50mg viagra without a prescripton viagra aderal

    匿名4周前 (02-06)回复
  87. #87

    diuretics men’s health mental illness

    匿名4周前 (02-06)回复
  88. #88

    pharmacies in canada brand cialis canadian pharmacies shipping to usa

    匿名4周前 (02-06)回复
  89. #89

    trust pharmacy canada viagra substitute online best 10 online canadian pharmacies

    匿名4周前 (02-07)回复
  90. #90

    canada medication pharmacy canadian pharmacies Brand Levitra

    匿名3周前 (02-08)回复
  91. #91

    cialis online cheap pfizer viagra online effects of viagra on men
    how to get generic viagra

    匿名3周前 (02-10)回复
  92. #92

    viagra overnight delivery viagra rapid tabs viagra online generic

    匿名3周前 (02-11)回复
  93. #93

    buy female viagra viagra dapoxetine canada viagra side effect or addiction

    匿名3周前 (02-11)回复
  94. #94

    bijwerkingen cialis koop cialis cialis patent
    wat kost sildenafil sandoz 100 mg

    匿名3周前 (02-11)回复
  95. #95

    Hello there, just became alert to your blog through Google,
    and found that it’s truly informative. I’m gonna watch out
    for brussels. I will be grateful if you continue this in future.

    A lot of people will be benefited from your writing. Cheers!

    Feel free to surf to my web blog: cheap flights (http://tinyurl.com/yy2xfsou)

    匿名3周前 (02-12)回复
  96. #96

    car title for cash loan md online payday loans in tampa fl payday loans in rapid city south dakota

    匿名3周前 (02-12)回复
  97. #97

    echte viagra kopen viagra kopen apotheek viagra kopen zonder recept ideal
    viagra wat kost dat

    匿名3周前 (02-13)回复
  98. #98

    payday loans ambassador caffery cash advance manteca ca cash advance from bmo mastercard

    匿名3周前 (02-13)回复
  99. #99

    teller assisted cash advance fast cash loans 100 approval money loan broker

    匿名3周前 (02-13)回复
  100. #100

    cialis infertility cialis why the bathtubs generic cialis trial

    匿名3周前 (02-14)回复
  101. #101

    cialis para mujeres en venezuela free cialis voucher priser pГҐ viagra och cialis

    匿名2周前 (02-16)回复
  102. #102

    canada drugs cialis cialis what is the generic name for cialis
    when is cialis going to be generic

    匿名2周前 (02-18)回复
  103. #103

    Very good written paragraph

    free robux

    匿名2周前 (02-18)回复
  104. #104

    viagra online canada buy viagra does viagra make you hornier
    what is the maximum dose of viagra

    匿名2周前 (02-19)回复
  105. #105

    best essay writing service for teachers executive resume writing service

    匿名1周前 (02-23)回复
  106. #106

    if7ac l94rc 5b3n

    匿名6天前回复
  107. #107

    help me write a 5 paragraph essay can you help me with my essay ese

    匿名4天前回复
  108. #108

    where to buy generic viagra marley generics viagra reviews buy generic viagra

    匿名4天前回复
  109. #109

    mu32n 2qtga w8g1

    匿名4天前回复
  110. #110

    ethics in human rights essay ideas ethics and business essay

    匿名3天前回复
  111. #111

    business school essay sample how to write an essay for business ethics

    匿名2天前回复