哈希表（散列表），O(n)的时间复杂度存储数据，通过哈希函数映射位置，实现O(1)的时间复杂度进行插入、查找、删除等操作。
unordered_set，判断元素是否在集合中
unordered_map，统计频率，记录内容如果元素有穷，出现范围不大，可以用一个固定的数组存储和统计元素。统计一个字符串中所有小写字母的出现次数，可以用大小为26的数组统计，对应的哈希函数为$ch-‘a’$
哈希表包括可以映射到的哈希地址范围，对于映射到同一地址的值，有不同的组织方式。
-
哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。
-
冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：
- 链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中。
- 开放地址法：当发现哈希值 hhh 处产生冲突时，根据某种策略，从 hhh 出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 h+1,h+2,h+3,…h+1,h+2,h+3,\ldotsh+1,h+2,h+3,… 这些整数对应的位置。
- 再哈希法：当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。
-
扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突。
哈希集合
705. 设计哈希集合 - 力扣（LeetCode）
class MyHashSet {
private:
vector<list<int>> data;
static const int base=769;
static int hash(int key){
return key%base;
}
public:
MyHashSet():data(base) {
}
void add(int key) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if(*it==key)
return;
}
data[h].emplace_back(key);
}
void remove(int key) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if(*it==key){
data[h].erase(it);
return;
}
}
}
bool contains(int key) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if(*it==key){
return true;
}
}
return false;
}
};
|
哈希表
706. 设计哈希映射 - 力扣（LeetCode）
class MyHashMap {
vector<list<pair<int,int>>> data;
static const int base=769;
static int hash(int key){
return key%base;
}
public:
MyHashMap():data(base) {
}
void put(int key, int value) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if((*it).first==key){
(*it).second=value;
return;
}
}
data[h].emplace_back(key,value);
}
int get(int key) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if((*it).first==key){
return (*it).second;
}
}
return -1;
}
void remove(int key) {
int h=hash(key);
for(auto it=data[h].begin();it!=data[h].end();++it){
if((*it).first==key){
data[h].erase(it);
return;
}
}
}
};
|
多重集合(multiset)
参考
面经手册 · 第3篇《HashMap核心知识，扰动函数、负载因子、扩容链表拆分深度学习(+实践验证)》 (qq.com)