本文原创首发于公众号：小詹学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。欢迎扫码关注！