[stackoverflow]哈希表是如何工作的？

原地址：

Lane

正文：

这是一个对于外行的解释.

让我们假设你不仅想要用书填满图书馆,还想当你需要就很容易的找到他们.

所以,你觉得如果一个人想要读一本书,需要知道这书的确切书名去寻找,应该可以找到书.一个人有书名+图书管理员的帮助,应该很快很容易的找到书.

所以,你要如何做呢？哦,显然你可以持有一些列表来存你把书放哪了,但是这时就有个问题,你要想在图书馆里找书,就得查列表.假定,这列表又简单又好查,但是你并不想查一本书就把整个列表从头到尾按顺序查一遍.

你想要一个这样的东西,只要给个书名,就回复一个正确的地点,然后你漫步到书架旁拿书即可.

但怎么才能达到这样的效果？当你填书到图书馆时得做点预处理工作.

不能像刚刚那样从头到尾填书,你得设计一个巧妙的办法,你拿出书的书名,通过一个小程序跑出书架号和位置号,来存该书.

这个神奇的程序的用处,就是过会再有人来读这本书,你就通过这个程序和书名,得到书架名和位置名,这两就是你最早放书的地方.

这个程序呢,就被叫做哈希算法或者哈希计算,是种带参数的算法,跑出一组数.

简单说呢,就是把字母、符号什么的换成数字,然后算个结果.实际情况,比这个复杂些,不过也就是这个意思.

这个程序的重点呢,就是你每次输入同样的书名或者什么东西,每次输出的结果都是一个结果,无论你输了多少次,过了多久.

好了,这就是哈希表工作的基础流程.

对于内行而言,

首先,存在一个数的尺寸.通常哈希算法的结果是在一些大数的范围里,一定要远远大于你在表中存的个数.举个例子,我们要存100万的书,那么输出结果可以是0到一个比100万大的多的数即可.

我们做什么呢？用计算模型,我们找的数比范围的最大值大,就再一次从0开始找.

就是算法的范围是0-20,存的数就7个,我们找17,我们得一轮找7个,再来一轮,再找0,1,2,3,最后是3.

当然,计算模型不都是这样,需要更多的设计和考虑.17除7余3.

你就知道书在位置3了.

这就导致了新的问题, 冲突.书填满了图书馆.算出的书会算出以前就使用过的,你想放书的时候,发现这个书架和位置都已经放书了.

存在非常多的解决冲突的办法,换个算法,或者找附近的,找将来要放的地方.不过靠谱的办法还是在一开始就设计更好的方法避免冲突.

最后,其实很多时候,你都可能想要放更多的书在图书馆的承受范围之外.你需要建个更大的图书馆.你可能还能用原来的书架和位置,也可能得重新来一遍,来存新的改变的书架和位置.

，未经一番寒彻骨，焉得梅花扑鼻香