哈希表_总结
Last renew: June 3, 2022 pm
哈希表(Hash Table)
什么是哈希表
哈希表是根据关键码的值而直接进行访问的数据结构。
简单来讲，数组就是一种哈希表。哈希表中关键码就是数组的索引下标，通过下标直接访问数组中的元素。
哈希表一般用于解决什么问题？
用来快速判断一个元素是否出现在集合里。O(1)就可以做到，无需遍历。但需要额外空间。
常见的三种哈希结构
当我们想用哈希法解决问题的时候，一般会选择如下三种关系结构。
- 数组
- set 集合
- map 映射
set只能储存一种值，但map可以储存一个<key, value>的键值对
哈希表经典题目
数组作为哈希表
242， 383
一些应用场景就是为数组量身定做的，比如要求只有小写字母。
虽然这两道题用Map也可以解决，但map消耗空间更大。
Set作为哈希表
349, 202
当数组大小没有被限制的时候，就无法使用数组做哈希表了。
主要原因有如下两点：
- 数组的大小受限，受到系统栈空间的限制
- 如果数组空间足够大，但哈希值比较少，比较分散，跨度非常大，使用数组会造成空间的极大浪费。
Map作为哈希表
1, 454, 18, 15
使用数组和哈希set也有自身的局限。
- 数组的大小受限值，如果元素很少，而哈希值太大会造成内存空间的浪费。
- Set是一个集合，里面放的元素只能是一个key。而两数之和不仅要判断y是否存在，还要记录y的下标并返回，所以无法用set。
map是一种<key, value>的结构，本题可以用key保存数值，并用value来保存数值所在的下标。
但面对三数之和，四数之和的时候，虽然哈希表依旧可以解决，但非常麻烦，代码效率很低。
所以在18， 15两道题中推荐使用双指针。