哈希(hash),是一种理论思想，与各种各样的树一样，其是一种数据组织的方式。依据我的理解，哈希的本质就是映射，将一组数据根据某种规则（哈希函数）映射到一个有序可查的表中。这个表里存放size_t（unsigned int）类型的数据，用于直接访问。因此，哈希表的增删查改的时间效率为O(1)，效率很高。但是其也有缺点，就是其得出的结果不会有序，因此哈希的本意为散列，就是散乱的数列。
概念
上面已经提到，哈希的本质是将数据转换为size_t类型的数据来存放，具体来说比如一题经典的例题：我们有一句string，然后想要找到第二次出现的字符，我们就可以将a~z映射到0~26,放入一个26大小的int类型数组，每当出现一个字母，我们就进行一次对应数组的++. 当第一个为2大小的数组单元出现时，这个单元对应的字符急速出现了第一个第二次的字符。这就是最简单的哈希思想：直接定址法。但是，在实际应用中，我们往往很难做到这种方法，因为这种方法只适合数据聚集的场景，当数据比如是{1,9,2,22,5555555}这样十分分散的数据时，就十分浪费内存。并且还有一种情况，两个不同的Key可能会映射到同一个位置，导致哈希冲突。
我们假设，目前哈希表中已经存放了N个数据，然后表的大小为M，那么此时这个表的负载因子就是（N/M）。负载因子用于定义这个哈希表的一些状况。当负载因子小的时候，表示这张表利用效率低，哈希冲突概率低。当负载因子大，甚至逼近于1时，表示这张表利用效率高，哈希冲突概率高，该表需要扩容。因此，找到一个合适的平衡点是很重要的。
除留余数法
一个好的哈希函数，可以尽量的让数据平均的落在哈希表中的每个位置。但是实操起来非常苦难，哈希冲突在所难免，只能说尽量。我们接下来说一个非常经典的哈希函数:除留余数法。
除留余数法，顾名思义，就是找余数。比如现在我进来了一个key大小的size_t类型数据，我要为他在M大小的哈希表中找一个位置，那么其公式为:h(key) = key % M.当我们使用这个方法的时候，重点便为M值的选取。一般来说，我们不会选择2的幂和10的幂作为M值，因为很容易发生哈希冲突。如果选择的是2的幂，那就是2进制的后幂次位，10就是10进制的后幂次位。那么一般我们选择什么作为M呢？我们选择质数，在c++sgi版本中，便是如此。他们使用了一个大小趋近于2倍的质数集。在我们以下的哈希表模拟实现中，为了方便，我并不会严格按照这个要求。
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
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
};其他方法不作介绍，包括乘法散列法和全域散列法等等，其本质也都是为了减少哈希冲突，提高哈希效率。
处理哈希冲突
开放定址法
开放定址法的思想由直接定址法延伸而来，本质还是在同一张表里面找坑蹲。当自己本来的坑被别人蹲了以后，就去找别人的坑蹲，其中有两种找坑的方法比较出名，线性探测法和二次探测法。线性探测法是直接到下一个坑去找位置，直到找到了个空的坑。二次探测法是跳跃找坑法，按二次方的速度进行左右横跳，直到找到一个空坑。下面是线性探测的模拟实现，这个初始空间只开10个其实不严谨，但是只是模拟实现就这样吧。
namespace open_address
{
enum State//利用三个状态确定当前节点的状态，使用枚举值，枚举能保证state只能在这三个里面
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;//使用kv来存储数据
State _state = EMPTY;
};
template<class K, class V, class Hash = HashFunc<K>>//Hash是用来提取数据的，将数据转换为size_t类型
class HashTable
{
public:
HashTable()
{
_tables.resize(10);//先开10个，不够再开
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//如果哈希表里面已经有了，那就直接return
return false;
K key = kv.first;//记录key的数据
if (_n * 10 / _tables.size() > 7)//如果目前的数据量已经占到哈希表的70%以上，扩容
{
HashTable<K, V,Hash > new_t;//构建一个哈希表
new_t._tables.resize(2 * _tables.size());//直接扩两倍
size_t i = 0;
while (i != _tables.size())//直接将数据插入_tables中，然后i++,当i = tables的大小时嗲表扩容结束了
{
if (_tables[i]._state == EXIST)
{
new_t.Insert(_tables[i]._kv);
}
i++;
}
_tables.swap(new_t._tables);//直接运行vector的swap函数，
}
Hash hash;//定义仿函数
size_t hash0 = hash(key) % _tables.size();//获得哈希值
size_t hashi = hash0;//获取哈希位置变化值
size_t i = 1;
while (_tables[hashi]._state != EMPTY)//如果当前节点状态不是empty,表示不能插入
{
hashi = (hash0 + i) % _tables.size();//运行哈希函数
i++;
}
_tables[hashi]._kv = kv;//当找到空节点了，
_tables[hashi]._state = EXIST;//将当前节点状态改为存在
_n++;//数量++
return true;
}
HashData<K, V>* Find(const K& key)
{
Hash hash;
size_t hash0 = hash(key) % _tables.size();
size_t hashi = hash0;
int i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
hashi = (hash0 + i) % _tables.size();
i++;
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* hd = Find(key);
if (hd == nullptr)
return false;
hd->_state = DELETE;
_n--;
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0; // 表中存储数据个数
};
}链定址法
链定址法就能比较好的解决哈希冲突严重的问题。链定址法的本质就是把相关数据以链表的形式挂载在对应哈希值的下面，变成哈希桶。因此，在这种情况下负载因子是可以大于1的，但是依然不推荐负载因子大于1，因为会导致某个哈希桶挂载的数据太多，导致遍历依旧效率低。
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
// K 为 T 中key的类型
// T 可能是键值对，也可能是K
// KeyOfT: 从T中提取key
// Hash将key转化为整形，因为哈市函数使用除留余数法
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);//先简单把哈希表大小定为10
}
// 哈希桶的销毁
~HashTable()
{
// 依次把每个桶释放
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];//
while (cur)
{
Node* next = cur->_next;
delete cur;//注意，我们的数据空间都new出来的，所以要delete删除。
cur = next;
}
_tables[i] = nullptr;
}
}
// 插入值为data的元素，如果data存在则不插入
bool Insert(const T& data)
{
if (Find(KeyOfT(data)))//先确定不存在相同的数据。如果已经有了，直接return
return false;
if (_n / _tables.size() >= 1)//保证负载因子小于1，大于1就扩容
{
vector<Node*> new_tables;//先弄一个新哈希表的table
new_tables.resize(2 * _tables.size());//把他的表大小扩为2倍，
for (int i = 0;i < _tables.size();i++)//接着通过遍历方式的去找每个哈希值
{
Node* cur = _tables[i];//
while (cur)//把每个哈希值下带的数据全部头插到new_tables那边去
{
Node* next = cur->_next;
size_t hashi = Hash(KeyOfT(cur->_data)) % new_tables.size();
cur->_next = new_tables[hashi];
new_tables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;//将原表对应哈希值的地方置空
}
_tables.swap(new_tables);//交换，让new_tables变为_tables
}
size_t hash0 = Hash(KeyOfT(data)) % _tables.size();//保存插入数据对应的哈希值。
Node* cur = _tables[hash0];//将目标哈希地址设为cur
Node* new_node = new Node(data);//创造新的插入节点
new_node->_next = _tables[hash0];//头插数据
_tables[hash0] = new_node;
++_n;//存在节点数量++
return true;
}
// 在哈希桶中查找值为key的元素，存在返回true否则返回false
bool Find(const K& key)
{
size_t hash0 = Hash(key) % _tables.size();//直接遍历即可
Node* cur = _tables[hash0];
while (cur)
{
if (KeyOfT(cur->_data) == key)
return true;
cur = cur->_next;
}
return false;
}
// 哈希桶中删除key的元素，删除成功返回true，否则返回false
bool Erase(const K& key)
{
if ( !Find( key ) )//先确定有没有数据
{
return false;
}
size_t hash0 = Hash(key) % _tables.size();
Node* cur = _tables[hash0];
Node* parent = _tables[hash0];//定义一个parent用来链接父子节点。
while (cur)//遍历找数据
{
if (KeyOfT(cur->_data) == key)
{
break;
}
parent = cur;
cur = cur->_next;
}
if (cur == parent)
{
_tables[hash0] = cur->_next;
}
else
{
parent->_next = cur->_next;
}
delete cur;
cur = nullptr;
return true;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};
}unorder_map和unorder_set的实现
这两个数据结构的底层都是哈希表，更确切的说是哈希桶。因此，实现unorder_map和unorder_set的重点其实是实现可泛化的哈希桶。在实现中，有几个比较指的注意的地方：1.类的声明嵌套。当出现A类中使用了B类，但是B类也使用A类，那么就可以进行前置声明，让编译器先对对参数，然后去下面找定义。2.模版友元。有的时候我们的数据是private的，但是其他类需要调用这个数据，按照以前学的那就是设置为友元类。对于模版类也可以这样进行设置。3.按照常理，set和map中的key是不能修改的。因此我们使用const进行修饰。map需要修饰pair中的key,而set直接修饰key即可。当然，当改了以后，需要在所有相关定义或者重定义的位置进行更改，比如typedef.
#pragma once
#include<vector>
enum State
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
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
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
namespace open_address
{
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
:_tables(__stl_next_prime(0))
, _n(0)
{}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
// 负载因子 >= 0.7扩容
if (_n * 10 / _tables.size() >= 7)
{
//vector<HashData<K, V>> newtables(_tables.size()*2);
//for (auto& data : _tables)
//{
// // 旧表的数据映射到新表
// if (data._state == EXIST)
// {
// size_t hash0 = data._kv.first % newtables.size();
// // ...
// }
//}
//_tables.swap(newtables);
HashTable<K, V, Hash> newht;
//newht._tables.resize(_tables.size() * 2);
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (auto& data : _tables)
{
// 旧表的数据映射到新表
if (data._state == EXIST)
{
newht.Insert(data._kv);
}
}
_tables.swap(newht._tables);
}
Hash hash;
size_t hash0 = hash(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state == EXIST)
{
// 线性探测
hashi = (hash0 + i) % _tables.size();
++i;
/*hashi = (hash0 + (i*i*flag)) % _tables.size();
if (hashi < _tables.size())
hashi += _tables.size();
if (flag == 1)
{
flag = -1;
}
else
{
++i;
flag = 1;
}*/
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key)
{
Hash hash;
size_t hash0 = hash(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
// 线性探测
hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
return true;
}
else
{
return false;
}
}
private:
vector<HashData<K, V>> _tables;
size_t _n; // 记录数据个数
};
}
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
HTIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
// 16:46
Self& operator++()
{
if (_node->_next)
{
// 当前桶还有数据，走到当前桶下一个节点
_node = _node->_next;
}
else
{
// 当前桶走完了，找下一个不为空的桶
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];
if (_node)
break;
else
++hashi;
}
// 所有桶都走完了，end()给的空标识的_node
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(0))
, _n(0)
{}
// 拷贝构造和赋值重载也需要
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return { it, false};
Hash hash;
// 负载因子 == 1时扩容
if (_n == _tables.size())
{
/*HashTable<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
newht.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newht._tables);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTable);
}
size_t hashi = hash(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), false };
}
Iterator Find(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}
cur = cur->_next;
}
return End();
}
bool Erase(const K& key)
{
KeyOfT kot;
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
// 头结点
_tables[hashi] = cur->_next;
}
else
{
// 中间节点
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};
}
#pragma once
#include"HashTable.h"
// MyUnorderedMap.h
namespace bit
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
void test_map1()
{
unordered_map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "字符串", "string" });
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 不能修改first，可以修改second
//it->first += 'x';
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}#pragma once
#include"HashTable.h"
namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
void print(const unordered_set<int>& s)
{
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end())
{
//*it = 1;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
void test_set1()
{
int a[] = { 3,11,86,7,88,82,1,881,5,6,7,6 };
unordered_set<int> s;
for (auto e : a)
{
s.insert(e);
}
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
//*it = 1;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
print(s);
}
}