STL之哈希
STL之哈希
- unordered_set/map&哈希之介绍
- unordered系列
- 哈希
- 哈希表的模拟实现
- unordered_set&/map的模拟实现
- 哈希的应用
- 位图（bitmap/bitset）
- 布隆过滤器（Bloom Filter）
- 海量数据处理
unordered_set/map&哈希之介绍
unordered系列
在C++11中增加了unordered_set和unordered_map，它们接口用法和set/map类似，但是在查找上远优于后者。
从名字上就可以看出，unordered系列的单向迭代器遍历是无序的，而set/map的双向迭代器遍历有序。和底层实现有关。
提供set和unordered_set的增删查改性能比较代码见下图：
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
v.push_back(rand());//无序+大量重复
//v.push_back(rand()+i);//无序+少量重复
//v.push_back(i);//有序
}
size_t begin1 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
size_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
size_t begin3 = clock();
for (auto e : v)
{
s.find(e);
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << endl;
size_t begin4 = clock();
for (auto e : v)
{
us.find(e);
}
size_t end4 = clock();
cout << "unordered_set find:" << end4 - begin4 << endl << endl;
cout <<"插入数据个数："<< s.size() << endl;
cout <<"插入数据个数：" << us.size() << endl << endl;;
size_t begin5 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << endl;
size_t begin6 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
可以发现，unordered系列的find的性能一骑绝尘，find1百万个数据也不足1ms。其他部分二者相差不大。总体推荐unordered系列。
哈希
哈希，又叫散列，是一种映射思想，类比数学的函数关系，将key和value建立映射。
哈希表的实现方法很多，常见的有：
- 直接定址法
将值直接存放在key映射的地址处。比如1放在下标1处。 - 除留余数法
如果key值大于哈希表，就模上表长。
但是都会存在哈希冲突，即不同的值映射到同一个位置。解决方法有：闭散列/开放定址法，包括线性探测（一个一个挨着往后找空位置映射）和二次探测（按平方数往后找空位置）等等。但弊端是治标不治本，依然空间资源紧张；开散列/开链法，在冲突位置挂单链表/红黑树（似桶，也称哈希桶HashBucket），也是库中采用的方法。
哈希表的模拟实现
闭散列实现代码：
namespace OpenAddress
{
enum State
{
EMPTY,
EXIST,
DELETE,
};
template<class K, class V>
struct HashData
{
pair<K, V>_kv;
State _state = EMPTY;
};
template<class K, class V>
class HashTable
{
public:
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))return false;
//负载因子超过0.7就扩容
if (_tables.size() == 0 || 10 * _n / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
/*_tables.resize(newsize);*/
HashTable<K, V>newht;
newht._tables.resize(newsize);
for (auto& h : _tables)
{
if (h._state == EXIST)
newht.Insert(h._kv);
}
_tables.swap(newht._tables);
}
size_t hashi = kv.first % _tables.size();//模的是size，因为size到capacity的空间[]不可访问
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state == EXIST)
{
index = hashi + i;
index %= _tables.size();
++i;
}
_tables[index]._kv = kv;
_tables[index]._state = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)return nullptr;
size_t hashi = key % _tables.size();
size_t index = hashi;
size_t i = 1;
//while (_tables[index]._state != EMPTY)
while (_tables[index]._state != EXIST || _tables[index]._kv.first != key)
{
index = hashi + i;
index %= _tables.size();
++i;
if (index == hashi)
return nullptr;
}
return &_tables[index];
}
bool Erase(const K& key)
{
HashData<K, V>* data = Find(key);
if (!data)return false;
data->_state = DELETE;
--_n;
return true;
}
private:
vector<HashData<K, V>>_tables;
size_t _n = 0;//
};
int main()
{
HashTable<int, int>ht;
int a[] = { 3,33,2,13,5,12,1002 };
for (auto& x : a)
{
ht.Insert(make_pair(x, x));
}
ht.Insert(make_pair(15, 15));
for (auto& x : a)
{
cout << ht.Find(x)->_kv.second << endl;
}
}
}
开散列实现代码见下文：
unordered_set&/map的模拟实现
namespace HashBucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next = nullptr;
T _data;
HashNode(const T& data) :_data(data) {}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashInt<K>>
struct __HashIterator
{
typedef HashNode<T>Node;
typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash>Self;
typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash>normal_iterator;
__HashIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* ht = nullptr)
:_node(node), _ht(ht)
{}
__HashIterator(const normal_iterator& it)
:_node(it._node), _ht(it._ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
size_t index = hashi;
while (++index < _ht->_tables.size() && !_ht->_tables[index])
{
_node = _ht->_tables[index];
}
if (index == _ht->_tables.size())
_node = nullptr;
else
_node = _ht->_tables[index];
}
return*this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _ht;
};
template<class K>
struct HashInt
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashInt<string>
{
size_t operator()(const string& str)
{
// BKDR
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
public:
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HashIterator;
typedef HashNode<T> Node;
typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash>iterator;
typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash>const_iterator;
public:
iterator begin()
{
Node* cur = nullptr;
for (auto& x : _tables)
{
if (cur = x)
break;
}
return iterator(cur, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const
{
Node* cur = nullptr;
for (auto& x : _tables)
{
if (cur = x)
break;
}
return const_iterator(cur, this);
}
const_iterator end()const
{
return const_iterator(nullptr, this);
}
pair<iterator, bool> Insert(const T& data)
{
Node* node;
if (node = Find(KeyOfT()(data)))
return make_pair(iterator(node), false);
if (_n == _tables.size())
{
//size_t sz = _tables.size() == 0 ? 10 : 2 * _n;
size_t sz = GetNextPrime(_tables.size());
vector<Node*>newtables(sz, nullptr);
for (auto& x : _tables)
{
while (x)
{
Node* next = x->_next;
size_t hashi = Hash()(KeyOfT()(x->_data)) % newtables.size();
x->_next = newtables[hashi];
newtables[hashi] = x;
x = next;
}
}
_tables.swap(newtables);
}
size_t hashi = Hash()(KeyOfT()(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode), true);
}
Node* Find(const K& key)
{
if (_tables.size() == 0)return nullptr;
size_t hashi = Hash()(key) % _tables.size();//key在hash后要能取模
Node* cur = _tables[hashi];
while (cur)
{
if (KeyOfT()(cur->_data) == key)return cur;//key要支持==比较
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
if (_tables.size() == 0)return false;
size_t hashi = Hash()(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (KeyOfT()(cur->_data) == key)
{
if (!prev)_tables[hashi] = cur->_next;
else prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
size_t MaxBucketSize()
{
size_t max = 0;
for (size_t i = 0; i < _tables.size(); i++)
{
auto cur = _tables[i];
size_t size = 0;
while (cur)
{
++size;
cur = cur->_next;
}
printf("[%d]->%d\n", i, size);
if (size > max)
{
max = size;
}
}
return max;
}
private:
size_t GetNextPrime(size_t prime)
{//接近2倍的素数
static const int PRIMECOUNT = 28;
static const unsigned long primeList[PRIMECOUNT] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
vector<Node*>_tables;
size_t _n = 0;
};
template<class K, class Hash = HashInt<K>>//库中还提供了支持key的==比较的仿函数模板参数，这里省略
class unordered_set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
private:
HashTable<K, K, SetKeyOfT, Hash>_ht;
};
template<class K, class V, class Hash = HashInt<K>>
class unordered_map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
return insert(make_pair(key, V())).first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash>_ht;
};
}
//int main()
//{
// /*HashBucket::HashTable<int, int>ht;
// int a[] = { 3,33,2,13,5,12,1002 };
// for (auto& x : a)
// {
// ht.Insert(make_pair(x, x));
// }
// ht.Erase(12);
// ht.Erase(3);
// ht.Erase(12);*/
// //size_t N = 100000;
// //HashBucket::HashTable<int, int>ht;
// //srand(time(0));
// //for (size_t i = 0; i < N; i++)
// //{
// // size_t x = rand() + i;
// // ht.Insert(make_pair(x, x));
// //}
// //cout << ht.MaxBucketSize();
// HashBucket::unordered_set<int>s;
// s.insert(1);
// s.insert(2);
// s.insert(3);
// HashBucket::unordered_map<int, int>m;
// m.insert(make_pair(1, 1));
// m.insert(make_pair(2, 2));
// m.insert(make_pair(3, 3));
// for (auto& x : s)
// {
// //x = 1;
// cout << x << " ";
// }
// cout << "--------------------------";
// for (auto& x : m)
// {
// cout << x.second << " ";
// cout << m[x.first] << " ";
// }
// cout << endl;
//}
注：一个类型要做unordered的key，得支持能转换成取模的仿函数和==比较；而要做map/set的key，得支持能>/<比较。
如何解决哈希表下单个桶的长度过长问题？1.控制负载因子，比如负载因子较小时就扩容，减少哈希冲突。2.改为挂红黑树，比如记录桶长，定义联合体。
哈希的应用
位图（bitmap/bitset）
一种通过bit置0/1表示在与不在或者统计次数的，极为节省空间的数据结构。通常用来处理大型文件的统计问题，比如1个TB的数据，无法直接全部加载到内存。注意，1个GB=1024 * 1024 *1024Byte，约=10亿字节。比如，对于100亿个int数据，正常需要400亿Byte即40GB大小空间，而位图只需开100亿个bit位，约=1.25GB大小即可。位图也可以改造成开两个设置更多bit位来记录出现的次数，或者开多个位图来比较分析多组海量数据。总之，位图上限高。
template<size_t N>//要开N个bit位
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
//cout << _bits.size() << endl;
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);//记住，左移是往高位移
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
vector<char>_bits;
};
template<size_t N>
class twobitsets//统计只出现一次的数据
{
public:
void set(size_t x)
{
if (!_bs1.test(x))
{
_bs1.set(x);
}
else if (!_bs2.test(x))
{
_bs2.set(x);
}
else//bs1和bs2都有，出现两次及以上
{
return;
}
}
bool test(size_t x)
{
if (_bs1.test(x) && _bs2.test(x))//两次及以上
{
return false;
}
else if (_bs1.test(x) || _bs2.test(x))//1次
{
return true;
}
}
void Print()
{
for (size_t i = 0; i < N; i++)
{
if (test(i))
cout << i << " ";
}
cout << endl;
}
private:
bitset<N>_bs1;
bitset<N>_bs2;
};
位图实现本身就应用了哈希思想，将数据映射在相应地址上，所以查找效率是常数级。可见，位图的优点有速度快，节省空间。但缺点明显，只能映射整型，诸如浮点数和string不能存储映射。只有通过哈希函数才能将它们转为能映射的值，所以有了下面的布隆过滤器。
布隆过滤器（Bloom Filter）
布隆过滤器通过多个哈希函数将数据（string，浮点数也行）映射到位图中。但是哈希冲突怎么办？位图中可不能挂链表指针啊！布隆过滤器巧妙的地方就在于用多个哈希函数将同一个值映射到多个位置来缓解哈希冲突，降低误判率。比如x映射到位置1，2，3；y映射到3，4，5；z映射到0，1，2。那么判断x是否存在，只要1，2，3中任何一个位置没有置1那么x一定不在；而就算1，2，3都被置1，也可能是y和z存在的原因。所以，布隆过滤器判断出来的不存在是准确的，存在是有可能误判的。由此也能看出布隆过滤器不支持删除/reset，因为可能悄悄地误删了其他值，比如删了y和z，x等于是跟着被删了。
关于哈希函数个数，太多了的话需要开的空间就多，太少了的话哈希冲突就严重，我的实现中就给3个。哈希函数可以去网上搜。网上也有人研究出哈希函数个数和布隆过滤器的长度以及数据个数的最佳关系，可以自行搜索。
template<size_t N, class K, class Hash1, class Hash2, class Hash3>
class BloomFilter
{
public:
void set(size_t x)
{
_bs.set(x);
}
bool test(const K& key)
{
size_t hash1 = Hash1()(key) % N;
size_t hash2 = Hash2()(key) % N;
size_t hash3 = Hash3()(key) % N;
if (!_bs.test(hash1) || !_bs.test(hash2) || !_bs.test(hash2))
{
return false;//只要有一个不在就不在
}
return true;//在
}
private:
bitset<N>_bs;
};
通过布隆的特性可以看出它的应用场景，多是在判断在不在而且可以容忍误判的场景，比如昵称注册，将昵称映射到布隆里。至于手机号注册呢，稍微改造一下即可，比如通过布隆过滤器排除掉一定没被注册过的手机号，而对于布隆认为的可能注册过的去数据库（通常是磁盘上的文件）里确认再判定是否注册过，这样减少了与磁盘的IO，提高了效率。
所以，布隆过滤器的优点是快与省空间，因为用的是位图。缺点是存在误判。
海量数据处理
位图部分提到，想要分析处理存在磁盘文件中的海量数据，直接全部加载到内存是很困难的，通常需要借助位图这种工具和拆分的思想来处理。
位图
问：给100亿个乱序不重复int数据，如何快速判断一个是是否在它们里？
答：将数据读取映射到位图中即可。
问：100亿个int，找出只出现一次的数据？
答：映射到位图部分中twobitsets里，两个位图中一个为1，一个为0即为只出现一次的数据。
问：两个文件各存100亿int，只有1GB内存，怎么找交集？
答：其中一个文件读到位图里，再读另一个文件判断在不在，在就是交集，最后还需要去重。法2，分别存到2个位图中，遍历，两个位图都在的就是交集。
哈希切分
问：两个文件，各存100亿个字符串，假设平均50Byte，总计5000亿Byte，约500G，但只有1G内存，怎么找交集？
答：哈希切分。两大文件各开出1000个小文件，通过一个哈希函数将大文件中的数据分别映射到对应的小文件中，即算出i=HashFunc(str)%1000;进入下标为i的小文件，下标相同的小文件找交集即可，因为相同的值一定被同一个哈希函数映射到同一个小文件里。
但是可能存在某个小文件有大量重复数据，或者大量不同数据导致小文件过大，无法加载进内存。先将文件数据全插进set里，如果插入成功，说明大量重复，就利用set找交集即可；如果插入失败，抛出bad_alloc异常表示内存不够，说明大量不同，那就换哈希函数再去切分该小文件即可。
问：100G的文件存字符串，1G内存，怎么找出现次数最多的字符串？top K个呢？
答：哈希切分。500份小文件，一个哈希函数映射到对应小文件中，使用map统计次数即可。如果抛内存异常，换哈希函数再切分。读取完一个，就clear再下一个。至于top K，开小堆存pair，每读一个，就遍历map更新堆即可。
哈希篇完结，stl差不多也就完结了，差个C++11就over了。小小的庆祝一波吧🥰~~~