Hash 算法

数据结构和算法是相辅相成的，基础的其实就那么些：时间复杂度的概念，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 取出对应的锁，和上面红包的例子本质上是同一种思想。即内容与位置之间的快速映射关系。

via:MrPeak