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