找到一个数据——哈希表

beginning

让我们幻想一下这样的一个场景：某一天，你成为了一个公司的档案管理人员。你的工作很简单：当其他员工来带着一份档案来找你的时候，准确无误的找到完全一样的档案。
但要注意，这些档案毫无规律可言，而且，相当的长。

遍历

这份工作听起来很简单，不是吗？毕竟，只是想完成它的话，大不了你可以一个个的进行比对，直到找到一样的那份。
更专业一些地说：遍历一遍。
但这家公司越做越大，你要处理的档案也越来越多。终于，它超出了你的能力范围。你不想被开除，那必须解决这个问题。或许，分类是个好办法。但别忘了一个条件：

这些档案毫无规律可言，而且，相当的长

也就是说，几乎没有一个“好”的分类规则，使得分出的类别少，又能做到每一类中档案的数量相差不多，且差别巨大。除非，我们能强行给创造出“规律”。

映射

要想做到这一点，我们要进入数学的世界，了解一下“映射”。

两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。
其中，b称为元素a在映射f下的象，记作：b=f(a)。a称为b关于映射f的原象。
集合A中所有元素的象的集合称为映射f的值域，记作f(A)。
或者说，设A,B是两个非空的集合，如果按某一个确定的对应关系f，使对于集合A中的任意一个元素x，在集合B中都有唯一的元素y与之对应，那么就称对应f：A→B为从集合A到集合B的一个映射。

这是映射的定义。为了达到“准确无误”这一要求，它冗长且晦涩。但还好，我们只需要有一个感性的认知就行了。
粗略地说，“映射”就是在几个东西间建立起的对应关系。
例如，我们假定1代表苹果，2代表鸡蛋，我们就对苹果和鸡蛋进行了映射。

hash

那看起来，我们要创造出“规律”，只需要对那些档案进行映射就行了。但我们还需要确定怎样进行映射。毕竟，如果没有一个通用的规则，那我们相当于什么都没做。
而这个“规则”，就叫做“哈希算法”。
哈希算法只有一条定义：将一个不定长输入转换成一个定长输出。
需要注意的是，这里的定义相当的广泛。举个最极端的例子：乘以0
任意数字乘以0，结果都是0。完美符合了哈希算法的定义。
我们完全可以说，将一个数乘以0，这是一个“哈希算法”。但它并不好。
一个棒棒的哈希算法还应该要有：抗强碰撞性。
也就是说，两个不同输入获得相同输出的可能性应该极小。

进制哈希

那现在，让我们来设计一个哈希算法吧。
我们先来定义一个运算——模除。简单来说，就是将两个数相除，取余。记作：a%b=c
显然，他有一个性质：0<=c<=b.
这是一个绝佳的映射方法。
那，我们先将每个字符转换成对应的数字。
但我们并不能直接将它们相加再取模。只要两个字符串加数相同或相差模数的x倍，那结果将完全相同。
但或许，我们可以一个一个来。
从第一位开始，我们将它取模，然后想办法将结果和下一位合并。、
这样，只要我们能把握好合并的过程，那就可以让这个哈希变得还不错。