什么是哈希

名牌定下格子号

上一课里，要找排好的值，得一个个扫过去，或者用排好序的索引。可要是能看着值本身定出格子号呢？就像用名字的字母来定格子那样。
也就是事先定好一个小小的计算，放进一个值，就得出一个格子号。这个计算叫作哈希函数。第一课里见过的字典，往里面看，也是用这种方法运转的。

点一个值。计算定出格子号，值一下子就放进那个格子。

每个值的格子都一下子定好了。不用琢磨放在哪里，因为计算会告诉你位置。
同一个值再放一次，计算的结果总是同一个格子，所以位置不会忽东忽西。那么，找的时候也用同一个计算，不就行了吗？

一算就直奔那个格子

找的时候，秘诀也一样。把要找的值放进同一个计算，求出格子号，然后直奔那个格子就行。不用一个个格子扫过去。
放的时候用的计算和找的时候用的计算一样，所以放进去的格子和要找的格子正好对上。于是一步就到。

点一个要找的值。同一个计算得出格子号，不用扫，直接跳到那个格子。

不用扫就直接到了。格子有一百个也好，一万个也好，花的工夫都差不多，因为算一次、跳一次就完事了。
这就是哈希快的原因。排好序的索引还要看二十来次，哈希一般一次就完成。不过，有一点让人放不下：两个不同的值算出的结果一样，会怎么样？

两个值奔向同一个格子

计算总会给同一个值同一个格子，可值不同，格子却不一定不同。因为格子的数量是固定的，值却可能多得多。
所以，两个不同的值有时会碰巧得到同一个格子，两个都想挤进一个格子。像这样为了同一个格子撞在一起，叫作冲突。

依次点两个值。算出的结果一样，两个都奔向同一个格子，撞上了。

两个值为了同一个格子撞上了。一个格子通常只放一个值，两个同时到就成了问题。
可这不是放弃哈希的理由。计算选得好，冲突就很少，其余的照样一步就快速完成。所以，只要在发生冲突时另外处理一下就行。来看看怎么处理。

冲突另外处理

解决冲突主要有两种办法。一种是在一个格子里把几个值放在一起：每个格子放一个小列表，撞在一起的值并排放进去。
另一种是挪到相邻的格子：原来的格子被占了，就找下一个空格子放进去。不管哪种办法，值都不会丢，以后还能再找到。

选一种处理办法点一下。把两个值放进同一个格子，或者挪到相邻的格子，解开冲突。

冲突干净利落地解开了。不管是放在一起还是挪到隔壁，值都安全地找到了位置。
找的时候照同样的规则，撞上的值也能顺利找到。只是格子快满时冲突会变多，所以在快满之前就要增加格子、重新安排。冲突只是偶尔发生，处理起来也简单，所以哈希依然又快又可靠。

小结

用一句话概括：哈希看着值，用计算定出格子号。放的时候放进那个格子，找的时候用同一个计算直奔那个格子。所以不用扫，一步就到。
偶尔不同的值奔向同一个格子，发生冲突时就另外处理：放在同一个格子里，或者挪到相邻的格子。靠计算直接找到，这就是哈希。

依次点要点回顾一下。（用计算定格子 → 用同一个计算一下找到 → 同格冲突 → 冲突单独处理）

现在你知道怎么靠计算直接找到值了。一个个扫格子的憋闷，靠一次计算就解开了。
不过哈希也有做不到的事。格子和值的大小毫无关系地散开着，所以没法按范围找，比如从 A 到 C 的全部，也没法按顺序排列。下一课会认识一种既能保持顺序、又能快速查找的容器：树。