什么是哈希表

哈希表（Hash table）也叫散列表，它是一种可以根据关键字直接进行访问的数据结构。哈希表通过某种关系把关键字映射到表中一个位置，这样存储位置与关键字之间有一个对应的关系f，使得每个关键字key对应一个存储位置f(key)。这样在查找时，根据给定的关键字key，通过f(key)这一对应关系可快速确定包含key的记录在存储空间中的位置。

​ 这个映射的函数f叫作散列函数，又称为哈希函数，按这个思想存储记录的连续空间称为散列表或哈希表。关键字对应的存储地址称为散列地址或哈希地址。

哈希表在存储时，以数据中每个元素的关键字key为自变量，通过哈希函数f(key)计算出函数数值，以该函数值作为一块连续存储空间的索引，将该元素存储到函数值指引的单元中。

例如，在建立花名册时以学生姓名为关键字，使得根据姓名来存储查找相应记录，可以把a-z这26个字母从1-26进行编号，字母表如表1所示。

表1 字母表

在存储学生姓名时，提取各姓名的首字母，将首字母相加得出的和作为姓名存储的地址值，例如李辰，两个字的首字母为lc，则相加为12+3=15，将李辰存储在15的位置，如表2所示。

表2 哈希表

​ 表2就是哈希表，每一条记录的存储地址都是通过哈希函数计算出来的，然后将记录存储到计算结果对应的地址中。而在查找时，根据姓名这个关键字计算出其存储地址，直接就找到关键字的存储地址，因此哈希算法既是一种存储方法也是一种查找方法。

​ 哈希表存储的是键值对，其查找的时间复杂度与元素数量无关，在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的，因此，哈希表查找的时间复杂度为O（1）。哈希表的这种数据结构使得它可以提供快速的查找、插入和删除操作，无论哈希表中有多少数据，查找、插入和删除的时间复杂度都是O(1)，运算速度非常快，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(n)的时间级。哈希表不仅速度快，编程实现也相对容易。

​ 当然有这么多优点，它也会有一些缺点，它的存储是基于数组的，数组创建后难于扩展，当基本被填满时，性能将会大幅下降，所以程序员必须清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程），而且它无法提供有序的遍历，不能进行某一范围的查找。

​ 除此之外，哈希表还有一个冲突问题，在理想情况下，每一个关键字通过哈希函数计算出来的地址都是不一样的，可现实中，时常会碰到两个关键字key1!=key2，但是却有f(key1)=f(key2)，这种现象称为冲突（collision），并把key1和key2称为这个哈希函数的同义词(synonym)。例如，当往表8-2中插入关键字“吴邪”，其首字母缩写为wy，相应的哈希计算出的结果为46，应该插入46的位置，但这个地址已有记录，这就非常糟糕，它会造成数据查找错误。在哈希存储中，冲突是很难避免的，除非设计的哈希函数是线性函数。哈希函数选的比较差则发生冲突的可能性就大，至于有了冲突如何处理，我们将在后面小节进行讲解。