哈希表

三种哈希结构：

• 数组
• set（集合）
• map（映射）

不同之处：

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。
• map是一种<key, value>的结构，可以用key保存数值，用value在保存数值所在的下标。

数组作为哈希表：

在242.有效的字母异位词 中，数组就是简单的哈希表，但是数组的大小是受限的！

这道题目包含小写字母，那么使用数组来做哈希最合适不过。

在383.赎金信中同样要求只有小写字母，那么就给了浓浓的暗示，用数组！

当然用map也可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

set作为哈希表：

在349. 两个数组的交集中用数组就不行了，需要用set。

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

关于set，C++ 给提供了如下三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

本题并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

在202.快乐数中，使用了unordered_set来判断一个数是否重复出现过。

map作为哈希表：

在1.两数之和中用到了map（入坑第一题）。

C++提供如下三种map：

• std::map
• std::multimap
• std::unordered_map

1.两数之和中并不需要key有序，选择std::unordered_map 效率更高！

总结：

map是万能的，不过该用数组的时候用数组，该用set的时候用set，效率更高。