闲聊 Hash 算法

最近读了一篇好文:【微信高并发资金交易系统设计方案——百亿红包背后的技术支撑】,其中关于高并发性能问题的解决方案中,有应用 hash 算法的思想。想起公众号后台里断断续续有读者提起算法方面的问题,觉得可以写篇文章聊聊算法中的 hash 算法。顺道科普下算法与数据结构的重要性。

开讲前,先跑题闲聊下程序员的技术功底。我常说每个程序员都有自己独特的技术视野和知识盲区,不同程序员之间很难因为某些知识点储备不一样而分个高低好坏。但我们工作当中,又能明显感觉不同团队成员之间的技术水平存在差异,到底差在哪呢?很多人调侃批量生产的培训程序员,那这些人和四年的大学本科之间又有多少距离?仅仅是时间吗?

差在基本功,基本功有很多项,数据结构与算法就是其中之一。虽然是基本功,却是最难储备和最易忽视的。行业越浮躁,变化越快,开发平台越便捷,高级 API 越多,基本功的重要性就越容易被忽视。即使能意识到基础薄弱,肯下定决心腾出几个月时间恶补基本功不是件容易的事,尤其是参加工作后,琐事繁多,一时热血下定的决心能坚持一周都属不易。后台偶尔有人问及程序员如何进阶的问题,以我这些年所经验,回过头来夯实下基础,对大部分人都会有奇效。

数据结构与算法的学习难度经常被夸大,不少人甚至谈算法色变,尤其无法忍受在面试当中问及算法问题。其实多点儿耐心,多投入些时间,学习算法并不难。至少学习基础的算法并不难,理解算法和去 leetcode 刷题是两回事,刷题所涉及的算法多需要技巧,基础的算法知识和其他计算机知识一样,不需要特别「聪明」的大脑,大多数人都能学会。Peak 君没刷过题,但对算法方面的知识也比较有自信。

数据结构和算法是相辅相成的,基础的其实就那么些:时间复杂度的概念,List,Array,Stack,Queue,Tree 等。Graph 实际应用中较少遇到,可以不做深入了解,但 BFS,DFS,Dijkstra 还是应该知道。基础的算法需要能达到手写的程度,比如排序至少能写出两种时间复杂度为 N*logN 的算法。理解这些比去 leetcode 刷题重要,学习难度也并不高。学习这些的意义在于掌握解决问题的基础思路,形成计算机思维,比如 divide and conque,recursive 等常规思想。

再回到本文重点 hash 算法。关于 hash 算法的实现原理和关键概念,网络上已有不少好文加以介绍。本文不做原理层面的解释,只谈应用。对实现感兴趣的可以搜索关键字:hash,load factor,扩容,hash 冲突解决等。

Objective C 中对于 hash 的应用主要封装在两个数据类当中:NSDictionary 和 NSSet。这点大家都知道,hash 算法能以空间换时间,在 NSDictionary 和 NSSet 中,判断一个元素是否存在只需要 O(1) 的时间复杂度。这一特点也使得在一些需要快速存取元素的场景,比如 Cache 设计,也能看到 NSDictionary 的身影。当然 hash 的应用远不止如此,做的应用越多,解决问题越深入,碰到 hash 算法的概率也会更高。

「The Algorithm Design Manual」一书中提到,雅虎的 Chief Scientist ,Udi Manber 曾说过,在 yahoo 所应用的算法中,最重要的三个是:hash,hash 和 hash。其重要性不言而喻。书中还举了一个很有趣的应用例子,请听题:

一场拍卖会中,物品是价高者得,如果每个人只有一次出价机会,同时提交自己的价格后,最后一起公布,出价最高则胜出。这种形式存在作弊的可能,如果有出价者能 hack 进后台,然后将自己的价格改为最高价 + 1,则能以最低的代价获得胜利。如何杜绝这种作弊呢?

三分钟思考时间,一,二,三。

参与者都提交自身出价的 hash 值就可以了,即使有人能黑进后台也无法得知明文价格,等到公布之时,再对比原出价与 hash 值是否对应即可。是不是很巧妙?

看到这,可能有朋友想到了 MD5,SHA。是的,上面的做法,和我们在 server 端存储密码的 MD5 值而非明文,是同一种思想,殊途同归。hash 算法包含有多种解决问题的思路,这里可以归纳为【通过 hash,生成不可逆的信息摘要】。

书里还有关于 hash 应用的其他有趣的场景(比如论文内容抄袭检测),都值得一读。

回到微信红包的例子,后台工程师为了防止抢红包时,用户的流量都涌进同个服务器,在同个 DB 上读写而导致的性能下降,采用了通过 hash 算法来分流的策略。每个红包创建的时候分配一个 ID,通过算法将 ID 映射到不同的逻辑服务器,一气呵成的解决方案。这里体现的是 hash 算法的另一种思想:【hash 能以 O(1)的复杂度将内容映射到位置】。这种应用 hash 的思路非常常见,还有不少例子。

去年写过一篇多线程文章【正确使用多线程同步锁@synchronized()】,当时阅读 OC 源码的时候也看到了 hash 的身影。@synchronized(token) 中的 token 通过 hash 算法存储到了一份手动维护的 cache 中,cache 的 key 使用的是 token 的内存地址。@synchronized 使用多了之后,如何快速的通过 token 取出对应的锁,对多线程的性能至关重要。hash 算法恰能以 O(1)的时间复杂度,以 token 为 key 取出对应的锁,和上面红包的例子本质上是同一种思想。即内容与位置之间的快速映射关系。

我还见到过很多例子,多多少少都有 hash 算法的影子。大家说 hash 算法是不是很重要?数据结构与算法是不是要学?不懂算法,有时候看别人代码就真如「过眼云烟」了,观其形而不知其意。别人赏雪,心中所念是:「都城十日雪,庭户皓已盈」,你只能一句「我靠!好美!」以抒胸臆,岂不煞风景?

之前有几位读者在后台留言,求算法书推荐。算法方面的好书有不少,不过大多是英文的,除去一些专业术语外,多是一些简单的词汇,阅读难度不算大,维坚持二字。推荐一本现今还留有印象的:《编程珠玑》,英文名《Programming Pearls》,不是大部头,建议啃英文原版。

最近有些忙了,不过至少还是会坚持一周一到两篇,和大家分享些技术心得和职场感悟。坚持做一件事不容易,写公众号这事,怎么都得挺住。写年终总结时,就多了件可以吹嘘的事 :)

欢迎关注公众号:MrPeakTech


Hosted by Coding Pages