哈希表基础知识

哈希表

哈希表就是根据关键码的值而进行访问的数据结构

数组就是一张哈希表

哈希表能解决的问题就是快速判断一个元素是否出现在集合里。

举例：

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在学校里了。

通过hashCode将名字转化为数值。
然后通过hashFunction哈希函数，将哈希函数映射到哈希表上了。

哈希碰撞

拉链法

线性探测法

C++中的哈希结构

C++中，set和map分别提供以下三种数据结构，std::set,std::multiset,std::unordered_set
详情见：代码随想录