哈希表
哈希表（Hashtable），是存储键值（KeyValue）对数据的一种数据结构。
例如，我们可以将人的名字作为键，性别作为值来存储。通过把键映射到表中的一个位置来访问数据，以提高查找速度。而这个映射关系就是哈希函数。
哈希函数
因为哈希表的数据映射关系以哈希函数为体现，为了避免小伙伴对哈希函数不够了解，此处先介绍哈希函数。
哈希函数可以把给定的数据转换成固定长度的无规律数值，可以把它想象成一台处理器，如下图所示：
输入的数据经过加工后，会输出对应的“哈希值”。哈希值多用十六进制表示（十六进制数范围是，数字0~9和字母a~f）。而计算机中则使用0和1表示的二进制来管理这些数据，实际上，哈希函数就是计算机内部进行的某种运算。
哈希函数的五个基本特征：
不管输入数据大或小，输出的哈希值数据长度固定不变如果输入的数据相同，那么输出的哈希值也必定相同输入相似的数据并不会导致输出的哈希值也相似即使输入的数据完全不同，输出的哈希值也有可能相同，这种情况叫做“哈希冲突”哈希函数的输入、输出不可逆，即无法反向推算出原数据哈希表结构
如果将键值对数据存储在固定大小的数组中，那么当需要查找某个数据时，我们只能从头开始遍历，我相信你已经很熟悉了，这就是“线性查找”。数据量越多，线性查找耗费的时间就越长，从耗时来看，此处使用数组来存储数据并不理想。
但使用哈希表就可以解决这个问题，首先，仍然使用具有5个存储空间的数组来存储数据。现在，尝试将Sue的键值对数据存入数组，使用哈希函数（Hash）计算Sue的哈希值，得到的结果为，将哈希值对5取模（mod），求得余数1。因此，我们将Sue数据存储在数组1号空间中。
重复前面的操作，Tom键的哈希值为，mod5后结果为4，将Tom数据存储到4号空间中。
Bat键的哈希值为，mod5后余数为4，按照前述操作来看，我们应当将其存入4号空间中，但4号空间已经存储了Tom的数据，这种存储位置重复的情况叫做“冲突”。遇到此种情况，可使用链表结构在已有的数据后面继续存储数据，关于链表的内容可见“链表”篇。
继续存储Amy数据，Amy键的哈希值为，mod5后的余数为0，将其存储在0号空间中。
Tan键的哈希值为，mod5后的余数为1。本应将其存储在数组1号空间中，但1号空间已有Sue的数据，故而使用链表，在Sue后面继续存储Tan的数据。
Rob数据同上，其哈希值为，mod5后的余数为1，因“冲突”，使用链表结构，继续存储在Tan数据的后面。
像这样存储完数据，哈希表也就制作完成了。
查询哈希表的数据也很简单，先计算出目标数据键的哈希值，然后对其进行mod运算，得到余数即是数组对应的空间索引。如果这个数据正好存储在数组空间上，那当然是皆大欢喜，如果不在，就需要对单链表进行线性查找了。
说明
哈希表中，可以通过哈希函数（Hash）快速获取数组中的目标数据。如果出现“冲突”，可以使用单链表在已有数据的后面插入新数据来解决冲突，这个方法被称为“链地址法”。这样不管数据量是多少，都可以灵活处理。
当然，除了链地址法以外还有其他解决冲突的方法，使用较为广泛的是“开放地址法”。此方法是指冲突发生时，循环计算下一个后补地址，直到有满足条件的为止。
数组空间越小，哈希表冲突的概率就越大，对单链表的线性查找频率就越高。反过来，如果数组空间过大，又会出现很多闲置的存储空间，因此，设定合适的数组空间非常重要！