用名牌直接找到，哈希

名牌定下格子号

前面我们学过，值
按格子号一个个排着。
要找就得一个个格子地扫。
可要是看着值本身，
就能定出它的格子号呢?
就像用名字的字母定格子。
我们摆一个小计算，
喂进一个值，给出一个格子号。
这个计算叫哈希函数。

点一个值。计算定出它的格子号，它就落进那个格子。

每个值都立刻有了格子。
不用纠结放哪儿。
计算把位置告诉你。
同一个值再放进来，
算出来还是同一个格子。
所以格子不会乱跑。
那么找的时候，
是不是也用同一个计算就行?

一算就直奔那个格子

找的时候，秘诀一样。
把要找的值喂进同一个计算，
得出格子号，
直接奔那个格子。
不用一个个格子地扫。
放进去用的计算
和找用的计算是一样的，
所以放的格子和找的格子正好对上。
所以一步就到。

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

没扫，一下就到了。
不管是一百个格子还是一万个，
费的功夫差不多。
算一次、跳一次，就完事。
这就是哈希快的原因。
不过有一件事让人在意。
两个不同的值，
要是算出来一样，会怎样?

两个奔向同一个格子

计算总是指出一个格子，
可值不同，格子不一定不同。
两个不同的值，
可能凑巧算出一样的结果。
那它俩就奔向同一个格子。
两个要挤进一个格子。
这样为同一个格子撞上，
叫做冲突。
冲突少见，但确实会发生。

依次点两个值。它们算出来一样，都奔同一个格子，撞上了。

两个为同一个格子撞上了。
一个格子通常只放一个，
两个同时来就成了问题。
可也不能因此放弃哈希。
冲突偶尔才一次，
其余照样一步就快。
所以只在冲突时，
稍微单独处理一下就行。
来看看怎么处理?

冲突单独处理

解冲突主要有两条路。
一是把两个塞进一个格子。
格子里放个小包，
把撞上的值并排放进去。
二是挪到相邻的格子。
原来的格子满了，
就找个空着的相邻格子放进去。
不管哪种，都不丢值，
以后还能再找到。

选一种处理办法点一下。塞进一个格子，或挪到相邻格子，把冲突解开。

冲突干净地解开了。
不管是塞一起还是挪到邻格，
值都安稳地落了位。
找的时候照同样的规矩，
撞过的值也能好好找到。
冲突偶尔有，处理又简单，
所以哈希照样又快又靠得住。
现在来把整件事理一理。

来理一理

归成一句话，是这样。
看着值，用计算定出格子号。
放的时候放那个格子，
找的时候同一个计算到那个格子。
所以不用扫，一步就到。
偶尔有别的值奔同一个格子，
冲突来了就单独处理。
塞一起，或挪到相邻格子。
用计算一下找到，这就是哈希。

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

现在你知道了用计算
一下找到值的聪明办法。
一个个扫格子的憋闷，
靠一次计算就痛快地解开了。
让放和找都变快的
这种本事，就是处理数据的力量。
下回又能用什么办法
把值存得更好、找得更好呢?
咱们接着一起看下去。