unordered_map与unordered_set
功能：
功能基本一样
1. unorder_xxx遍历不按照key进行排序 ,命名体现了
2. unorder_xxx只有单向迭代器，没有提供反向迭代器
3. unorder_xxx综合效率略胜map和set
unordered对于无序的数据效率很高
set底层使用对于顺序插入的数据效率就会很高
demo.cc
void test_set()
{
//set是排序+去重
//unordered_set：只能实现去重,没有实现排序
unordered_set<int> us;
us.insert(1);
us.insert(3);
us.insert(4);
us.insert(1);
us.insert(7);
us.insert(6);
us.insert(2);
auto it=us.begin();
while(it!=us.end())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
//这个就不用去重,
unordered_multiset<int> s;
s.insert(12);
s.insert(12);
s.insert(12);
auto dt=us.begin();
while(dt!=s.end())
{
cout<<*dt<<" ";
dt++;
}
}
哈希
哈希本质
哈希/散列
本质上就是映射，找到一个值进行映射，把数据映射到对应的地方
使用示例
计数排序：
1.统计每个数字出现次数，范围很集中，可以使用，但是对于随机的一堆整数，就按照范围来开空间，很分散，最好不要这样，
哈希函数
除留余数法
10 122 31 400
%10把对应的数放到它余数对应的位置
开10个空间，分配到不同的地方
哈希冲突：
不同的数用哈希放到了同一个地方,不能保证每个值都开辟一个空间
但是我想要映射到一个相对固定的地方去
我们最常用的方法就是将
如何解决哈希冲突
- 闭散列
闭散列：开放定址法，当发生hash冲突的时候，如果哈希表未被装满，说明在哈希表中必然还有空的位置，那么就把key存放到下一个“空位置”中去
* 线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
* 二次探测
>我们下一次探测到其平方的位置上，这样就不会让数据太集中
- 开散列/哈希桶/拉链法
6 26 36 46，
把尾数为6的都挂起来,放到同一个桶里面，这样就不会出现争抢位置，现在我们出现的争抢就内部解决，不会互相影响了，从根源上更好的去管理这个东西
表长度100
控制负载因子，能够极大的控制住效率–负载因子到了就扩容,
但一个桶的长度超过一定的值之后，就把他转化成一个红黑树,这样效率就很高了
//极端场景下
struct Date
{
forward_list<T> _list;
set<T> _list;
size_t len
};
len 大于一定值的时候，就把forward_list 里面的数据插入到set里面，再把单链表里面的数据给删除掉
极端场景
- 存50个值，40个值冲突，挂在同一个桶上
- 存储了10000个值，平均每个桶的长度100，阶段场景山有些桶可能有上千个值
哈希函数
- 除留余数法:我们将每个数和其对应vector长度进行取余，当达到负载因子就要进行重新扩容，重新映射
- 平方取中法
假如关键字1234，就把它平方=1522356，取中间3位，223，
如果它不够3位，就继续对他进行平方，直到取出3位位置，也存在哈希冲突
不常用
闭散列
使用线性探测；冲突的时候，就往后进行探测，直到到达空位置，
enum Status //状态标记
{
EXISTS,
EMPTY,
DELETE
};
template <class K, class V>
struct HashData
{
pair<K, V> _kv;//里面的每一个元素都是一个pair
Status _status = EMPTY;//一开始的节点都设置为空
};
template <class K>
struct Hash//哈希函数，将其转化成为一个可以进行取余的数，仿函数
{
size_t operator()(const K &key)
{
return key; //返回一个无符号数,负数的话，也变成一个正数
}
};
//如果是key是string走的就是这个特化版本
//模板的特化，上面有一个基础的类模板
template <>
struct Hash<string> //把这个参数直接确定,因为string用的很经常
{
size_t operator()(const string &s)
{
size_t val = 0;
for (auto e : s)
{
val *= 131;
val += e;
}
return val;
}
};
//这个hash表即可给map也可给set
//找一个值，遇到空才停，遇到删除还要继续找
//出现的问题
// 1.删除一个值，这个值应该设置成多少
// 2.删除完毕之后，后面冲突的值怎么办,现在，把一个值删除之后，就要把他的状态标记成删除，不清理数据
template <class K, class V, class HashFunc = Hash<K>>//这个可以支持int和string两种，其他的要我们自己来写仿函数
class HashTable
{
private:
vector<HashData<K, V>> _table; //我们数据不是都是按顺序的存储
size_t _n = 0; //有效数据的个数，直接在这里给一个缺省参数
public:
/*
散列表的载荷因子a=表中元素的个数/散列表的长度,a越大，冲突的概率就越大，a越小，冲突的概率就越小，如果超过了一定值，就要扩容
*/
HashData<K, V> *Find(const K &key)
{
if (_table.size() == 0)
{
return nullptr; //没找到
}
HashFunc hc;//仿函数,实现哈希函数
size_t start = hc(key) % _table.size(); //模上它的vector的元素大小,如果模上它的容量的话，可能回超出size的范围，无法访问_table[i],只能访问size以内的
size_t i = 0;
size_t index = start;
while (_table[index]._status != EMPTY) //在这里死循环了
{
//数据存在，就继续往下探测
if (_table[index]._kv.first == key && _table[index]._status == EXISTS)
{
return &_table[index];//存在且等于，就直接返回对于的数组的地址回去
}
i++;
index = start + i * i; //这个是依次探测,二次探测
//如果到最后还有数据的话，那就要绕回来
index %= _table.size();
}
return nullptr;
}
bool Erase(const K &key)
{
HashData<K, V> *ret = Find(key);
if (ret == nullptr)
{
//找不到要删除的值
return false;
}
else
{
//找到了那个值
ret->_status = DELETE;//我们不需要进行手动删除，直接把它的状态设置为删除即可
_n--;
return true;
}
}
bool Insert(const pair<K, V>& kv)
{
HashData<K, V> *ret = Find(kv.first);
if (ret != nullptr)
{
return false; //有一个重复的值
}
if (_table.size() == 0 || _n * 10 / _table.size() >= 7)
{
//越小，冲突的概率就越低，效率越高，但是空间浪费越高
//繁殖，冲突的概率越高，效率越低，浪费越小
//载荷因子大于0.7就要进行扩容
size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;//table的大小变小了，假如说一开始还没有给这个table进行赋值，这个就没有大小，所以写一个对0进行操作
// vector<HashData<K,V>> newtable;
// newtable.resize(newsize);//扩完容，就会把没有元素的地方初始化成0
// //扩容完，要重新改变值的位置，原来冲突的可能不冲突了，不冲突的可能就冲突了，建立新的映射关系
// //遍历原表，把原表的数据重新映射到新表
HashTable<K, V, HashFunc> newHT;//这里用一个新对象，调用自己
newHT._table.resize(newsize);
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._status == EXISTS)
{
//数据存在,就往我们新的ht里面插入
// newHT._table.insert(_table[i]._kv);
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table); //把两个进行交换即可，这样就可以把我们想要的table给转换过来了
}
HashFunc hc;
size_t start = hc(kv.first) % _table.size(); //模上它的vector的元素大小,如果模上它的容量的话，可能回超出size的范围，无法访问_table[i],只能访问size以内的
size_t i = 0;
size_t index = start; //探测旁边
//现在我们可以用探测i平方
/*
vector<int> v;
v.reserve(10);
for(int i=0;i<10;i++)
{cin>>v[i]}//这样是不行的，因为[]必须要保证这个地址上是有数据的
*/
//如果这个位置没数据，就直接放进去，如果有数据，就要开始线性探测
//空或者删除都可以放
//线性探测的大逻辑,很容易拥堵在一起，尤其是相连的一块，你占我，我占你
//二次探测
while (_table[index]._status == EXISTS)
{
//数据存在，就继续往下探测
i++;
index = start + i * i; //这个是依次探测
//如果到最后还有数据的话，那就要绕回来
index %= _table.size();
}
//一定是在一个可以放数据的地方
_table[index]._kv = kv;
_table[index]._status = EXISTS; //插入设置存在
_n++;
//找空位置的代价会很大
return true;
}
};
散列表（哈希桶）
将vector里面的数据结构换成单链表
把冲突的数据都串在一起
template <class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V> *_next; //我们用一个单链表,我们自己弄的
HashNode(const pair<K, V> &kv)
: _kv(kv), _next(nullptr)
{
}
};
template <class K>
struct Hash
{
size_t operator()(const K &key)
{
return key; //负数也给他转化成非负数
}
};
template <class K, class V, class HashFunc = Hash<K>>
class HashTable
{
typedef HashNode<K, V> Node;
private:
vector<Node *> _table; //链表里面的元素挂起来,指针数组
size_t _n = 0; //有效数据，计算负载因子
public:
Node *Find(const K &key)
{
if (_table.empty())
{
return nullptr;
}
HashFunc hc;
size_t index = hc(key) % _table.size();
if (_table[index] == nullptr)
{
//没找到
return nullptr;
}
else
{
//在它对应的链表下面找，看看能不能找的到
Node *cur = _table[index]; //_table[index]就是对应链表的头节点
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
}
bool Erase(const K &key)
{
if (_table.empty())
{
return false;
}
//找到了，就把它给删除掉
HashFunc hc;
size_t index = hc(key) % _table.size();
Node *cur = _table[index];
Node *prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if(prev==nullptr)
{
//头删除
_table[index]=cur->_next;
}
else
prev->_next = cur->_next;
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
bool Insert(const pair<K, V> &kv)
{
Node *ret = Find(kv.first);
if (ret)
{
return false;
}
HashFunc hc;
if (_n == _table.size()) //这里我们可以让负载因子变得大一点,负载因子=1的时候扩容`
{
size_t newcp = _table.size() == 0 ? 10 : _table.size() * 2;
//这里就自己来挪动，使用和闭散列一样的方法，不好，因为会一直要new节点，
vector<Node *> newTable;
newTable.resize(newcp); //扩容后要进行重新映射
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
//有数据
Node *cur = _table[i];
while (cur)
{
//把这个数据弄下来，直接
Node *next = cur->_next;
size_t index = hc(cur->_kv.first) % newTable.size();
//然后进行头插
cur->_next = newTable[index];
newTable[index] = cur;
cur = next;
}
}
_table[i] = nullptr; //弄完了就把对应的数据给清空即可
}
// newcp里面的数据都是我们想要的
_table.swap(newTable);
}
size_t index = hc(kv.first) % _table.size();
//没有数据
Node *newnode = new Node(kv); //新的头节点
newnode->_next = _table[index];
_table[index] = newnode; //
//用头插法把数据插进去，因为重新映射代价比较大
_table[index] = newnode;
_n++;
return true;
}
};