哈希表理论基础

哈希表Hash Table又称散列表。哈希表是根据关键码的值直接进行访问的数据结构。而数组其实就是一张哈希表，哈希表可以根据key的值(数组的索引下标)，直接访问key对应的value(数组中的元素)。

哈希表的应用场景：用于快速判断集合中是否包含某个元素。

哈希函数：将要用哈希表存储的值直接映射为该数据在哈希表上的位置索引，之后即可通过查询索引下标快速判断要查询的值是否在哈希表中。具体的做法是：将要存储的值通过hashcode转化为数值，并根据该数值将要存储的数据映射到哈希表的对应位置上。若得到的数值大于哈希表的大小，则对其进行取余操作，之后即可将每个数据映射在哈希表上的唯一位置。但是可能存在多个数据被映射到哈希表中的同一个位置的情况，这种情况被称为哈希碰撞。

哈希碰撞：哈希碰撞的解决方案包括：拉链法和线性探测法。

①拉链法：若多个元素都被映射到了哈希表中某个相同的索引位置，则可以通过链表的方式将多个元素连接在该位置上。之后即可通过索引找到需要的元素。注意：拉链法要选择适当的哈希表大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

②线性探测法：必须保证表长大于数据个数，从而利用哈希表中的空位来解决碰撞问题。

常见的三种哈希结构：数组、set和map。

在C++中，set提供的数据结构包括：std::set、std::multiset、std::unordered_set。std::unordered_set的底层实现为哈希表，其中存储的数据是无序的，且不可存储重复数据。而前两种存储结构是基于红黑树实现的，所以其中的数据是有序的。注意：multiset中可以存储重复数据。

在C++中，map提供的数据结构包括：std::map、std::multimap、std::unordered_map。std::unordered_map的底层实现为哈希表，其中存储的数据是无序的，且不可存储重复数据。而前两种存储结构是基于红黑树实现的，所以其中的数据是有序的。注意：multimap中可以存储重复数据。

基于红黑树实现的数据结构只能进行删除和增加操作，而不可进行key值得修改，改动key值会导致整棵树的错乱。

在解决哈希问题时，优先使用std::unordered_set，因为其查询和增删效率是最优的。若要求集合有序则使用std::set。若既要求有序，还要求存储重复元素，则可以使用std::multiset。

map结构是key-value格式的数据，map对key的值有限制，但是对value的值没有限制，因为key的存储是基于红黑树实现的。

解题笔记

1.两数之和：这道题如果使用暴力破解，直接两个循环遍历数组即可，但是这样做效率比较低。而哈希表专用于判断一个元素是否曾经出现过，或者一个集合里是否有某个元素的场景。通过哈希表，仅用一次循环即可得到最终解。哈希表用于存储我们遍历过的元素，将元素值作为键，元素在数组中的下标作为值存储到hashmap中。每当遍历到一个新元素时，去查找target-该元素的值是否已经在hashmap中，即可快速查找。

242.有效的字母异位词：这道题只需要判断组成两个单词的字母出现的次数是不是相同的。所以只需要关心每个字母的出现次数即可，而不用关心出现的具体是哪个字母。所以可以用数组保存每个字母的出现次数。进行对比即可。

349.两个数组的交集：使用hashSet即可找到两个数组的交集，获取两个数组中的共有元素(这些元素是不重复的，例如a数组中有两个2，b数组中也有两个2，最终的结果中只有一个2)。

202.快乐数：这道题和哈希表的关系在于，需要用哈希表记录所有出现过的不为1的数字，如果出现重复，则表明这个数不是快乐数，因为如果新得到的数字已经存在于哈希表中，则表明根据检查快乐数的规则，经过几次检查，这个数字还会重复出现。所以这个数肯定不是快乐数。简单题。