写点什么

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

用户头像
dongge
关注
发布于: 2020 年 04 月 29 日
哈希,茫茫人海,我一眼看到了你

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

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

实战









通过搜索可以看到《程序员的数学基础课》、《数据结构与算法之美》、《分布书协议与算法实战》、《检索技术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讲》。

课程推荐





发布于: 2020 年 04 月 29 日阅读数: 101
用户头像

dongge

关注

还未添加个人签名 2017.10.19 加入

还未添加个人简介

评论

发布
暂无评论
哈希,茫茫人海,我一眼看到了你