01、哈希表

之前给大家介绍了链表，栈和队列今天我们来说一种新的数据结构散列（哈希）表，散列是应用非常广泛的数据结构，在我们的刷题过程中，散列表的出场率特别高。

所以我们快来一起把散列表的内些事给整明白吧。文章框架如下

说散列表之前，我们先设想以下场景。

厨子穿越回了古代，凭借从现代学习的做饭手艺，开了一个菜馆，正值开业初期，店里生意十分火爆.

但是顾客结账时就犯难了，每当结账的时候，老板娘总是按照菜单一个一个找价格（遍历查找），每次都要找半天，所以结账的地方总是排起长队，顾客们表示用户体验不咋滴。

厨子一想这不是办法啊，让顾客老是等着，太影响客户体验啦。所以厨子就先把菜单按照首字母排序（二分查找），然后查找的时候根据首字母查找，这样结账的时候就能大大提高检索效率啦！但是呢？

工作日顾客不多，老板娘完全应付的过来，但是每逢节假日，还是会排起长队。

那么有没有什么更好的办法呢？对呀！我们把所有的价格都背下来不就可以了吗？每个菜的价格我们都了如指掌，结账的时候我们只需简单相加即可。

所以厨子和老板娘加班加点的进行背诵。

下次再结账的时候一说吃了什么菜，我们立马就知道价格啦。自此以后收银台再也没有出现过长队啦，袁记菜馆开着开着一不小心就成了天下第一饭店了。

下面我们来看一下袁记菜馆老板娘进化史。

上面的后期结账的过程则模拟了我们的散列表查找，那么在计算机中是如何使用进行查找的呢？

散列表查找步骤

散列表-------最有用的基本数据结构之一。

是根据关键码的值儿直接进行访问的数据结构，散列表的实现常常叫做散列（hasing）。

散列是一种用于以常数平均时间执行插入、删除和查找的技术，下面我们来看一下散列过程。

我们的整个散列过程主要分为两步

（1）通过散列函数计算记录的散列地址，并按此散列地址存储该记录。就好比麻辣鱼我们就让它在川菜区，糖醋鱼，我们就让它在鲁菜区。

但是我们需要注意的是，无论什么记录我们都需要用同一个散列函数计算地址，再存储。

（2) 当我们查找时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。因为我们存和取得时候用的都是一个散列函数，因此结果肯定相同。

刚才我们在散列过程中提到了散列函数，那么散列函数是什么呢？

我们假设某个函数为 f，使得

存储位置 = f (关键字)

输入：关键字 输出：存储位置(散列地址)

那样我们就能通过查找关键字不需要比较就可获得需要的记录的存储位置。这种存储技术被称为散列技术。散列技术是在通过记录的存储位置和它的关键字之间建立一个确定的对应关系 f ,使得每个关键字 key 都对应一个存储位置 f(key)。见下图

这里的 f 就是我们所说的散列函数（哈希）函数。我们利用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间就是我们本文的主人公------散列(哈希)表

上图为我们描述了用散列函数将关键字映射到散列表，但是大家有没有考虑到这种情况，那就是将关键字映射到同一个槽中的情况，即 f(k4) = f(k3) 时。

这种情况我们将其称之为冲突，k3 和 k4则被称之为散列函数 f 的同义词，如果产生这种情况，则会让我们查找错误。幸运的是我们能找到有效的方法解决冲突。

首先我们可以对哈希函数下手，我们可以精心设计哈希函数，让其尽可能少的产生冲突，所以我们创建哈希函数时应遵循以下规则

（1）必须是一致的，假设你输入辣子鸡丁时得到的是在看，那么每次输入辣子鸡丁时，得到的也必须为在看。如果不是这样，散列表将毫无用处。

（2）计算简单，假设我们设计了一个算法，可以保证所有关键字都不会冲突，但是这个算法计算复杂，会耗费很多时间，这样的话就大大降低了查找效率，反而得不偿失。所以咱们散列函数的计算时间不应该超过其他查找技术与关键字的比较时间，不然的话我们干嘛不使用其他查找技术呢?

（3）散列地址分布均匀我们刚才说了冲突的带来的问题，所以我们最好的办法就是让散列地址尽量均匀分布在存储空间中，这样即保证空间的有效利用，又减少了处理冲突而消耗的时间。

现在我们已经对散列表，散列函数等知识有所了解啦，那么我们来看几种常用的散列函数构造规则。这些方法的共同点为都是将原来的数字按某种规律变成了另一个数字。