专栏首页小詹同学LeetCode | 你不得不了解的哈希算法 !

LeetCode | 你不得不了解的哈希算法 !

⒈哈希是什么 ?

问大家一个问题 。如果手机上存储了 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 中的字典有个键值对 ,其实有些类似 ,这里小詹给出思路 ,不分享代码 。按照思路用 python 写出可行代码的同学欢迎在留言区回复 ,将在前 3 个亲测有效的代码中选取一个最优的送上实体书一本(下次送书活动预留一个名额)欢迎动脑 ,中奖概率三分之一

思路如下 :

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

祝你写出完美的代码噢 !增加这个环节主要是考虑到这个刷题系列烧脑 ,参加互动的人不多 ,当然小詹写的不够好也是一方面 。

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python爬虫实例之——小说下载

    这是小詹关于爬虫的第②篇文章! 第一篇关于爬虫中介绍了一些基本的术语和简单的操作,这里不重复叙述了,直接放链接,不记得的自己在文章末尾点击前期链接补补~ 本篇开...

    小小詹同学
  • 刷新纪录 | 74.7 秒训练完 ImageNet!2048 GPU 暴力出奇迹

    在过去两年中,深度学习的速度加速了 30 倍。但是人们还是对 “快速执行机器学习算法” 有着强烈的需求。

    小小詹同学
  • 关于程序员的那些事~

    小小詹同学
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈
  • 哈希算法的设计要点及应用场景

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇主要介绍了哈希算法相关的内容,包括什么是哈希算法、哈...

    syy
  • 浅谈哈希表

    哈希表是一种根据哈希键去寻找哈希值的数据映射结构。通过该结构找到哈希键映射的位置,再根据映射的位置去寻找存放哈希值的地方。

    小蜜蜂
  • AI综述专栏| 大数据近似最近邻搜索哈希方法综述(上)(附PDF下载)

    在科学研究中,从方法论上来讲,都应先见森林,再见树木。当前,人工智能科技迅猛发展,万木争荣,更应系统梳理脉络。为此,我们特别精选国内外优秀的综述论文,开辟“综述...

    马上科普尚尚
  • 朝花夕拾-哈希表(hashTable)

    所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

    皮皮熊
  • 图像检索:基于内容的图像检索技术(四)

    基于树结构的最近邻搜索方法和基于哈希的最近邻搜索方法在理论计算机科学、机器学习以及计算机视觉中是一个很活跃的领域,这些方法通过将特征空间划分成很多小的单元,以此...

    用户3578099
  • 哈希表的理论知识

    哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单...

    晚上没宵夜

扫码关注云+社区

领取腾讯云代金券