哈希表-JZTXT

一般哈希表都是用来快速判断一个元素是否出现集合里
哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希表其实就是一个数组，如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置，从而产生哈希碰撞。
哈希碰撞
比如，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞
一般哈希碰撞有两种解决方法，拉链法和线性探测法。
拉链法：
刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了
线性探测法：
使用线性探测法，一定要保证tableSize大于dataSize，需要依靠哈希表中的空位来解决碰撞问题。
如：在冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize 。
常见的三种哈希结构
数组，set，map
set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：