前言

• 哈希表是通过关键码的值而进行直接访问的数据结构
• 数组也是一张hash表，只不过数组的关键码就是他的下标，或者说是索引

• hash表最强大就在于它可以快速判断一个元素是否在一个集合里面，时间复杂度$O(1)$
• hash方法&hash函数

在密码学里，哈希函数是指对一串消息做计算，根据one-way-function得到一个消息摘要，确保原消息的真实性

将一个数据列表映射倒hash表上，就涉及了hash function,即哈希函数

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

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

很显然有个问题，哈希碰撞

 避免hash碰撞的方法

• • 拉链法
    • 发生冲突的位置搞一个链表，有冲突的元素放在链表里

• • • 拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
  • 线性探测法
    • 保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
    • 当出现碰撞时候后来的元素插到碰撞位置后面的空闲位置

• hash表常用的几种数据结构
  • array 数组
  • set 集合
  • map 映射
• C++中set及其底层实现

 std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

1. 所以当我们要使用集合来解决hash问题时，优先使用unorderwd_set 
2. 如果集合要是有序的，就使用set
3. 如果集合不仅要是有序的，还要有重复元素，就使用multiset

• C++中map及其底层实现

 std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的

 map 是一个key - value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

• 为什么都说set和map是哈希法使用的数据结构？

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

• hash_set hash_map与unordered_set，unordered_map有什么关系？

unordered_set，unordered_map是C++标准库中的数据结构，而hash_set hash_map是民间高手自发造的车轮子，其实是一个东西，既然标准都有了，还是用标准里面的东西吧！

• 哈希法也是牺牲了空间换取了时间，因为要使用额外的数组，set或者是map来存放数据，才能实现快速的查找
• 当要判断一个元素是否在集合里，就可以考虑hash表

有效的字母异位词