哈希，茫茫人海，我一眼看到了你

哈希是学习数据结构，编写代码，处理各种内存溢出问题跳不过去的一道坎。

这篇文章介绍通过极客时间深入理解哈希及哈希应用的过程。

实战









通过搜索可以看到《程序员的数学基础课》、《数据结构与算法之美》、《分布书协议与算法实战》、《检索技术20讲》、《Nginx核心知识100讲》和《左耳听风》都提到了哈希。看起来这确实是一项很有价值都技术。这里以《程序员的数学基础课》、《数据结构与算法之美》、《Nginx核心知识100讲》和《左耳听风》为例说明在极客时间里你可以深入到什么程度来了解这项技术。

程序员的数学基础课

先从《程序员的数学基础课》的 “余数，原来取余操作本身就是个哈希函数” 来实际了解一下 Hash 。在这篇文章里，黄老师通过星期来说明余数总是在一个固定的范围内，并引出同余定理。进而引导出这个特性就是编程语言中 Hash 能够做到的事情。









在这节课里，通过余数这个小知识点，我们就能找到很多的应用场景，比如我前面介绍的散列函数、加密算法，当然，也还有我们没有介绍到的，比如循环冗余校验等等。



好像不太深入，再来看看这个专栏里的“缓存系统：如何通过哈希表和队列实现高效访问？”

在这篇文章里，黄老师介绍了如何使用哈希表和队列实现高效缓存系统。理解下面两张图是关键。







数据结构之美

这个专栏有五篇专栏谈哈希。



哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。但是，要想设计一个优秀的哈希算法并不容易，根据我的经验，我总结了需要满足的几点要求：

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；

• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；

• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。



应用一：安全加密说到哈希算法的应用，最先想到的应该就是安全加密。

最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。

除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。



应用二：唯一标识我先来举一个例子。

如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢？



应用三：数据校验

电驴这样的 BT 下载软件你肯定用过吧？我们知道，BT 下载的原理是基于 P2P 协议的。我们从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。



应用四：散列函数前面讲了很多哈希算法的应用，实际上，散列函数也是哈希算法的一种应用。



应用五：负载均衡我们知道，负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？

我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。



应用六：数据分片

如何统计“搜索关键词”出现的次数？

我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。

如何快速判断图片是否在图库中？



应用七：分布式存储



通过这个专栏，我们可以了解到散列表也就是哈希表，可以深入的看到哈希算法的七大应用。



通过以上介绍，对哈希对应用是不是又更深入了一层。

左耳听风

关于 Merkle Root 前面说到过，可以简单地将 Merkle Root 理解为交易的 hash 值。这里，我们具体说一下，比特币的 Merkle Root 是怎么计算出来的。首先，我们知道，比特币的每一笔交易会有三个字段，一个是转出方，一个是转入方，还有一个是金额。那么，我们会对每个交易的这三个字段求 hash，然后把交易的 hash 做两两合并，再求其 hash，直到算出最后一个 hash 值，这就是我们的 Merkle Root。我画了一个图展示一下这个过程。



上面的示意图中有四笔交易，A 和 B 的 hash 成了 Hash-AB， C 和 D 的 hash 成了 Hash-CD，然后再做 Hash-AB + Hash-CD 的 hash，得到了 Hash-ABCD，这就是 Merkle Root。整个过程就像一个二叉树一样。下图是一个区块链的示意图，来自比特币的白皮书。





通过皓哥的介绍，你可以深入理解比特币中最重要的交易信息是通过 Hash 的方法解决的。



Nginx 核心知识 100 讲



通过上面的三段视频，你可以了解到 Nginx 是如何使用 Hash 的，还可以深入了解 Nginx 的 Hash 模块的使用方法。



总结

通过以上课程，可以从基础的余数概念关联到哈希，可以了解到哈希算法的七大应用，并且深入理解比特币是如何利用哈希算法的，还可以了解到服务效率超高的 Nginx 服务器是如何通过哈希算法来实现的。如果你想了解更多的哈希在分布式和检索技术中的应用可以订阅《分布书协议与算法实战》、《检索技术20讲》。

课程推荐