哈希的故事

如何在一个集合中快速找到你想要的那个元素？

为了便于理解，我决定用如下场景来类比这个问题。一个班级，任意两个同学的姓名都不相同，你第一次来到这里，手上有一个名字，并且也知道这个同学的所有信息，如何尽你所能最快地找到这个同学？假定同学不能主动向你传达信息，只能由你去查阅每个人的资料。

第一个方案在脑海中闪现：依次去查阅同学的名字，直到找到为止！哈哈，看运气了，也许第一次就找到了，也许第50次才找到…. 如果一万个陌生人都来做这件事的话，平均每个人要找25.5次。作为一个先驱者，你思考着，怎样为后人造福呢？

根据某项特征，给他们排个序吧，尽可能要保证不同学生的特征值不同，不然根据我手上这个特征值找到好几个同学，还得再依次比较。选什么好呢，姓氏在百家姓中的序号？生日吧，比姓氏更能满足要求！1月1日出生的同学是101，2月19日的是219，10月9日的是1009….（想到那个著名的题目，一个班50个学生，任意两名同学生日都不同的概率是多少？与直觉相违背的，结果竟然很小..）于是，本文的主角–哈希（Hash，这只是一个名称，叫成“特征值”，也行）登场了，我们有了一个很重要的逻辑命题：

Object->Hash

（从Object能推出Hash，or，O蕴含H，但是H不一定蕴含O）[注 1]
然后，你把同学们拉到操场上，按照生日值从小到大，从左往右排成一列（生日相同[注2]的若干名同学，用绳子连成一条线，从第一个同学开始，能依次到达这条线的每一个同学；第一个同学在队列中占一个位置。对每组生日相同的同学都这样做）[注3]完成之后，队列中有43名同学。该怎么找呢？你想到了著名的二分法：首先拿队列中间（22nd）同学的生日值，和你手上的值比较，若手上的值更大，那么要找的同学肯定在右边半个队列里了，于是比较33rd同学的值；若手上的值更小，就对左边半个队列继续此过程。任何一次查找都有可能命中你手上的值，包括第一次查找。如是，最多找6次就命中了。命中后，若同学背后没有绳子，恭喜，再比较下名字就可以了（如果名字不对，噢，那这个班没有这名同学）！若有，沿着绳子一个一个比较姓名，直至名字吻合或绳子末端的同学为止。Work finished！

反思一下，班级同学的生日分布，直接决定了上述方法的效率。最极端的情况，50名同学生日都在同一天，上述方法退化为你一开始的最朴素的方法。于是你知道了，哈希函数（即上文O->H的过程）的终极目标是：让H蕴含O。既然此目标几乎无法达成，那么我们就要尽可能让H表达出O的特征。这里用生日去表达学生，还是比较理想的。

满意之余，你并没有停止思考：我可以由下标立刻定位队列那个位置的元素，下标是整数，哈希值也是整数… 灵光乍现了！刚才根据下标进行二分搜索，那为什么不直接把哈希值作为下标呢！于是你按照下面所述重新组织同学们[注4]：
你开辟了操场上很大一块空间，把同学们放到各自特征值对应的位置上（若特征值一样，还是用绳子处理）；你发现前面一百多个位置都留空了，当排到10月份出生的同学时，操场的空间不够用了… 原来这个操场最多只能容纳一千个位置，看来凡事都是有两面性的啊[注5]。怎么办呢，这个方案不能就这样放弃啊..你想到了前面浪费的一百多个位置.. 有了！把特征值按照一千取余数，比如1021放在21号位置，1230放在230号位置.. 这样一来，就不能保证一个绳子连着的同学哈希值都一样了，但仍然是一个不错的方案，因为由你手上的哈希值，可以一次就定位到某个同学or一条绳子连着的若干个同学！

再一次，满意之余，你思考着，能不能通过优化哈希函数，使得所需的空间更少呢.. 学号！哈哈哈，这甚至实现了H蕴含O的终极目标！只需50个位置，并且能一次性命中，而且因为满足了H->O，命中后连名字都不用比较了..

也许聪明的你一开始就想到了学号( ´▽` ) 这里为了讲述哈希的方方面面，用以上的方式展开了。其实实际应用中，是很难能有完美的哈希函数的！

注

这也解释了为什么在Java中，当o1.equals(o2)返回true时，它俩的哈希函数必须返回相同的int值：因为“一个同学有两个生日”这种事，是很荒谬的。
这种情况被称为“哈希冲突”。
在计算机底层，任何数据结构在存储的方式上，只有“离散的”和“连续的”两种。链表、树等结构，是离散的，每个节点存储它自己的数据，以及其他节点所在的地址；数组是连续的，由下标可以直接命中那个位置的数据。这里，队列是数组，每条线是一个链表。
程序=数据结构+算法。这里，程序的输入是全班同学、你手上的同学的信息，输出是那个同学本人。把同学排列组织成那样，是你为这个问题使用的数据结构，之后搜索的过程就是你的算法。你使用的结构，从一定程度上决定了你的算法。
这就是计算机领域中著名的“空间换时间”。这里，相比上一个方案，你消耗了更多存储空间，使搜索时花费的时间更少。