哈希表

数据结构之一 ：哈希表（或称散列表）
哈希表是数组支持按照下标随机访问数据的特性（数组的一种扩展）
哈希表存储以键值形式
为什么使用哈希表？
当查找是线性查找的时候，从头开始查询直到找到要查找的值，但是如果数据太多，还耗时，所以可用哈希表存储

eg:

问题 ：想查找Alyy的性别，如何查找？

一、先线性查找

屏幕快照 2020-03-05 下午6.26.37.png

所以使用哈希表解决这个问题，这次准备5个箱子的数组来存储数据

二、哈希表

把Joe存储进去没使用哈希函数计算Joe的哈希值，比如得到结果是4928 ，将哈希值除以数组的长度，求余，这个叫mod运算

屏幕快照 2020-03-05 下午5.50.34.png

因此将数据存储进数组的3号箱子，重复前面操作存进数组

遇到这钟情况，可使用链表在已有数据的后面继续存储新的数据（链表法）

总结：

哈希冲突
在哈希表中，我们可以利用哈希函数快捷访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储，这样不管数据多少，可以灵活应对。

如果数组空间太小，使用哈希表时候容易发生冲突，线性查找的使用频率也会高；反之，如果数组空间太大，会出现空箱子，造成内存浪费，因此设定合适的空间非常重要

在存储数据过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据解决冲突，这种方法成为链表法（或是链地址法）