力扣 哈希表刷题回顾

avatar
作者
猴君
阅读量: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就是元素出现的次数

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!