闲聊 Hash 算法 - MrPeak杂货铺 - 程序猿·D·安宇雨 DeepMind

闲聊 Hash 算法 - MrPeak杂货铺

安宇雨 - 随手采集
2019-04-12 18:48:27
随手采集
0000-未整理-等待研究

最近读了一篇好文：【微信高并发资金交易系统设计方案——百亿红包背后的技术支撑】，其中关于高并发性能问题的解决方案中，有应用 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 （长按二维码）