LeetCode笔记-哈希表

哈希表

本篇为个人笔记，内容或有错误。
图片部分源于代码随想录，侵删。

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。
一般哈希表都是用来快速判断一个元素是否出现在集合里。

两个元素同时映射到哈希表中同一位置，这一现象叫做哈希碰撞，如下例：

一般处理方法有两种，拉链法和线性探测法。

其实拉链法就是要选择合适的哈希表大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间

使用线性探测法，一定要保证tablesize大于datasize，需要依靠哈希表中的空位来解决碰撞问题。

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

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

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

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