阅读量:0
哈希表理论总结
什么时候用哈希表，快速判断一个元素是否出现在集合中是，用哈希这种空间换时间的方法。
哈希函数与哈希碰撞
哈希函数是指将key映射到对应的哈希表上
哈希碰撞是指映射的过程中容易出现多对一的情况，用什么方法解决拉链法和线性探测法
哈希表主要有
数组、set 、map三种
数组适用于给定数量的元素，并且数量不多，查找起来很方便，占用空间小
set 分为三种 set， unordered_set, muti_set
set 与muti_set底层都是红黑树，并且key有序，muti_set特殊在key可以重复，他们的查找和删除时间复杂度都是O(Log(n))
而unordered_set 底层是哈希表，key无序，key不可以重复，查找删除时间复杂度为O(1)
map也分三种，map ,unordered_map,muti_map
map是有key 与value的，key都不可以修改
map与muti_map 底层是红黑树，key有序，muti_map的key可以重复，查找删除效率为O(log(n))
unordered_map 底层哈希表，key无序，key不可以重复，时间复杂度为O(1)
map使用时
增加元素用map.insert(pair<类型，类型>{key,value})
key对应的value 变化，例如map[key]++
查找元素，if( map.find(key) != map.end() )等于true即为找到了
刷题时，
注意，定义unordered_map<类型1，类型2> set1； 类型1对应key的类型，类型2对应value的类型
key就是要查找的元素，value就是元素出现的次数
