哈希表理论基础

哈希表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中，即可快速查找。