假设我们需要写个饭店需要的点单的微信小程序，我们首先需要一个菜单，列出菜品和单价。如果使用数组来存放这些数据。
menue= [["french fries",0.75], ["hamburger",2.5], ["hot dog",1.5], ["cola",0.6]]
这个数组需要包含好几个子数组，每个数组又有两个元素——菜品和单价。
如果数组是有序的，那么搜索特定的菜品单价采用第一节中所讲的二分查找，需要O(log N)步。
如果数组是无序的 ，只能遍历整体，则需要O(N)步。
有没有更快更好的查找办法呢？
有，事实上我们可以好很多，下面我们就开始学习一种新的数据结构——哈希表，它可以在O(1) 时间内查找数据。这正是它最强大的特性：快速读取。
大多数编程语言中都有这种数据结构，不过在不同的编程语言中的名字可能不同。Hash、Map、Hash Map、Dictionary和Associate Array指的都是哈希表。
为便于理解，下面采用Ruby中的哈希表实现小程序的菜单。
menu = {"french fries" => 0.75,"hamburger" => 2.5,"hot dog" => 1.5,"cola" => 0.6}
对于C/C++来说要使用自带的哈希表，则需要学习STL ，目前我还没有学习到所以这里先不做介绍。 值得注意的是，由于哈希容器直到 C++ 11 才被正式纳入 C++ 标准程序库，而在此之前，“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本，不过该版本只能在某些支持 C++ 11 及以上的编译器下使用（如 VS），有些编译器（如 gcc/g++的4.7版本之前）是不支持的。
哈希表由一组成对的数组成。每对数的一个元素称作键，第二个元素称作值。例如：字符串"cola"就是一个键，而0.6是其对应的值，它们组合在一起构成了键值对。
在Ruby中可以使用以下语句来查找一个键的值。
menu["french fries"]
该语句会返回值0.75。因为通常只需要1步，所以在哈希表中查找值的平均复杂度是O(1)。
- 哈希函数
你还记得你小时候用来加密信息的密码吗？
以下面这个字母和数字的简单映射为例。
A=1 B=2 C=3 D=4 E=5 以此类推...
使用这个密码：
ACE变成了135，CAB变成了312，DAB变成了412，而BAD变成了214。
哈希表的关键就在于它的哈希函数。我理解为对键编码运算的函数，把字母转换成数字的过程称为哈希，用来把字母转换成特定数字的密码就是哈希函数。
除此之外，有很多种哈希函数，例如先把字母转换成对应数字后再求和也是一种哈希函数，这样BAD变成了2+1+4=7；计算对应数字的积也是一种哈希函数，该函数会把BAD转换成8；此外还有除留余数法和平方中值法等。
一个哈希函数的好不好，取决于以下三点：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有n个地址时，其值域必须在 0 到 b-1 之间。
- 哈希函数计算出来的地址能均匀分布在整个空间中。
- 哈希函数应该比较简单。
事实上，有效的哈希函数只需要满足一个条件：对同样字符串使用哈希函数得到的值应该永远相同。
- 哈希表O(1)时间的查找
假设你开发了一件产品，它是一个同义词典，可不是老旧的词典应用，而是快速同义词Quickasaurus。用户在过时的同义词典应用中查找单词时，会找到所有可能的同义词，而Quickasaurus只会返回一个结果。
因为每个单词都有一个关联的同义词，所以这正是哈希表出场的好机会，毕竟哈希表就是一组成对的元素。
用哈希表表示同义词典 thesaurus = {}
添加第一条同义词：thesaurus["bad"] = "evil"
用代码表示的话，哈希表就变成了这样:{"bad" => "evil"}
想要知道如何查找，那么先弄清楚哈希表是如何存储数据的呢？
答案是：和数组类似，哈希表实质上把数据存在一连串的格子中，每个格子都对应一个数。
下面来展示数据经过哈希并存储的过程:
先计算机会对键使用哈希函数，使用我们的“乘法加密哈希”。
BAD=2×1×4=8
因为键"BAD"的哈希值是8，所以计算机会把其对应的值"evil"存到第8格中。
接下来，添加另一个键值对：thesaurus["cab"] = "taxi"
计算机仍会先计算键的哈希值:CAB=3×1×2=6
因为结果是6，所以计算机会把值"taxi"存到第6格中。
再添加一个键值对：thesaurus["ace"] = "star"
因为ACE的哈希值为15（ACE=1×3×5=15），所以"star"被放到了第15格中。
用代码表示，哈希表就变成了下面这样。
{"bad" => "evil" , "cab" => "taxi" , "ace" => "star"}
在哈希表的查找中，我们只需要使用键来寻找它关联的值。
假设我们要查找"bad"，则用非常简短的代码就可以完成：thesaurus["bad"]
计算机只需要执行简单的两步：
- 计算查找的键的哈希值：BAD=2×1×4=8。
- 因为结果是8，使用计算机会检查第8个格子并返回其中的值————"evil"。
这样看来，哈希表的键就像数组中的下标，经过某些规则后键可以转换成哈希值然后计算机就去查找到值所在的索引。那么查找时间不正是O(1)吗？这就是哈希表的神速！
值得注意的是，哈希表只能单向查找，即只能通过键来找值，值不能决定键的位置。同时值可以重复，键不能重复。
- 解决哈希冲突
哈希表很强大，但也不是没有缺点。
细心的同学可能已经发现了上面乘法哈希编码的不严谨处：
如果加入thesaurus["dab"] = "pat"
首先计算机会把键哈希，DAB=4×1×2=8
然后计算机会试图把"pat"放到第8个格子中去，却发现第8个格子已经被邪恶的"evil"占据了！
向已经有内容的格子添加数据就会发生冲突。
处理哈希冲突有两种方法：闭散列和开散列。
闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到表中“下一个” 空位中去 。
那如何寻找下一个空位？
这里有线性探测法和二次探测法。具体这里不做详细，有兴趣的同学可以自行深入了解。
开散列：又名拉链法，先用哈希函数计算每个数据的散列地址，把具有相同地址的元素归于同一个集合之中，把该集合处理为一个链表，链表的头节点存储于哈希表之中。
这是一种经典的解决方案，发送冲突时，格子存储的不再是单一的值，而是存储一个数组的引用或链表的头。
如下图所示，查找的时候也是线性查找，遍历每个子数组。
假设所有数据都位于同一个格子，那么哈希表和数组就毫无区别了，所以哈希表查找在最坏情况下的复杂度是O(N)。让哈希表尽可能没有冲突非常重要，只有这样，查找才能在O(1)而不是O(N)时间内完成。
- 伟大的平衡法案
从上面你可以看到冲突越少，哈希表的效率越高，但是假设我们要存储5个元素，那么拥有1000个格子的哈希表几乎不用担心冲突问题。
避免冲突固然重要，但这需要在冲突和内存占用之间取得平衡。
用1000个格子仅仅存5个数据，这得多大的内存浪费啊！
为此，计算机科学家提出了如下准则：每增加7个元素，哈希表就应该增加10个格子。
数据与格子的比值称为负载因子。上述准则可以用该术语表述为：理想的负载因子是0.7（7个元素/10个格子）
好在大多数语言以及实现了哈希表，它决定了哈希表的大小、使用的哈希函数以及扩容的时机，我们无须担心这些细节，不过理解哈希表的原理能够让我们体会到哈希表维持O(1)级别性能的可贵之处。现在知道为什么我这一章这么懒了吧，我们只要会运用自如就很不错啦。