目录
- 一、哈希介绍
- 1.1 哈希概念
- 1.2 哈希冲突解决
- 1.2.1 闭散列
- 1.2.2 开散列
- 二、哈希桶
- 2.1 实现哈希桶
- 2.1.1 构造节点和声明成员变量
- 2.1.2 构造与析构
- 2.1.3 仿函数
- 2.1.4 查找
- 2.1.5 插入
- 2.1.6 删除
- 2.2 kv模型哈希桶源代码
- 三、改造哈希桶
- 3.1 begin+end
- 3.2 迭代器
- 3.2.1 前置++
- 3.3 改造后哈希桶与迭代器源代码
- 四、模拟实现unordered_set
- 五、模拟实现unordered_map
一、哈希介绍
1.1 哈希概念
顺序结构中（数组）查找一个元素需要遍历整个数组，时间复杂度为O(N)；树形结构中（二叉搜索树）查找一个元素，时间复杂度最多为树的高度次logN。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
主要有3种操作：
- 插入——根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 查找——根据要搜索的元素的关键码，用函数计算出存储位置，取该位置的元素关键码进行比较，如果相等，查找成功
- 删除——根据待删除元素的关键码计算出该元素的存储位置，如果改元素存在，则进行删除
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
如果在上面的例子中插入元素44会怎样？44%10也是4，与原来元素4的位置冲突了。那么这个新插入的44应该如何放置呢？
1.2 哈希冲突解决
首先要知道哈希冲突的原因——哈希函数设计不够合理
哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
下面介绍两种常见的哈希函数：
- 闭散列
- 开散列
1.2.1 闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去，这里的下一个可能也有元素，所以可能继续重复前面的操作，直到遇到空位置。
线性探测：
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
44%4=4，与元素4的位置冲突，到它的下一个位置，位置5也有元素，继续下一个，直到位置8没有存储元素，就把44存储到位置8中。
1.2.2 开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
开散列中每个桶中放的都是发生哈希冲突的元素。
二、哈希桶
2.1 实现哈希桶
2.1.1 构造节点和声明成员变量
哈希表的每个位置是一个桶，这个桶的结构是单链表，单链表由每个节点组成。节点有数据域和指针域，指针域是用来连接下一个节点的，数据域存放的是节点的值。节点的数据域有两种：k模型和kv模型。这里实现哈希桶的是数据域是kv模型。
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
成员变量有存放的数据个数和哈希表的每个位置，即每个桶，用头指针进行连接，所以哈希表的每个位置是单链表的头指针。
vector<Node*> _table;//哈希表的每个位置-桶-单链表
size_t _n = 0;//存储的元素个数
2.1.2 构造与析构
1️⃣构造
刚开始给哈希表一定的空间大小，每个位置初始化为空指针。
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
2️⃣析构
哈希表的结构是STL库中的vector，当程序结束时，vector会自动调用它的析构来清理哈希表，但是表中的每个位置是单链表，单链表的每个节点是动态开辟出来的，vector的析构不能清理它们。所以要自己写析构函数来清理这些节点。
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
2.1.3 仿函数
哈希函数的计算公式：hash(key) = key % capacity，capacity就是表的空间大小，key必须是整数，但是key值是不确定的，有可能是整形、浮点型或者是字符串，所以要对key值作一些处理，使其变成整数才能进行取模操作。
1️⃣key不是字符串
返回值都转化成无符号整数
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
2️⃣key是字符串
因为传过来的参数固定就是字符串(string类型)，不像前面，可能是int、double等，所以这里可以直接特化处理。定义一个临时变量为无符号整数作为返回值，遍历每个字符加到临时变量里，每个字符会自动转换成ASCII码值，然后再乘上权值131（在《The C Programming Language》书中有解释），保证不会出现year和raey相同的场景。
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
在后面的操作中使用到哈希函数：hash(key) = key % capacity，都要通过调用仿函数来实现。
2.1.4 查找
查找一个元素是否存在，首先要计算出该元素的位置。假设该元素存在，但是它在某个位置的桶中，通过遍历单链表找到该元素，然后返回它在链表中的节点位置。不存在，返回nullptr
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到当前位置头节点
while (cur)
{
if (cur->_kv.first == key)//找到了
{
return cur;
}
cur = cur->_next;
}
//cur为空，不存在这个数据
return nullptr;
}
2.1.5 插入
- 插入新的元素，不能有重复的，所以先对要插入的值进行查找，如果找到了，说明是重复元素，不能插入，返回失败。
- 插入新的数据不是重复元素，计算该元素在哈希表的映射位置，创建一个新节点，用头插法插入。
- 如果要插入数据前，哈希表的元素个数与哈希表的空间大小相等，就要扩容。创建一个新的哈希表，扩容的大小可以给原来的两倍，初始化为空。遍历旧表，将旧表的节点移动到新表中。注意，移动的过程中节点在旧表中的位置与新表可能是不对应的，所以还要用哈希函数得到节点在新表的位置，然后插入的话还是头插法。旧表中的每个位置即每个桶移动完成，，就将旧表的该位置置空。最后全部转移完，把旧表和新表进行交换，后面使用的就是新表了。
bool Insert(const pair<K,V>& kv)
{
//重复元素不能插入
if (Find(kv.first))
{
return false;
}
Hash hs;
//扩容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空间
//将旧表的节点移到新表中，再交换
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(_table[i]->_kv.first) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入数据
size_t hashi = hs(kv.first) % _table.size();//表中的位置
Node* newNode = new Node(kv);//新节点
//头插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
2.1.6 删除
删除某个元素，首先得查找该元素是否存在。如果不存在返回false；存在，通过哈希函数计算该元素的位置（是哪个桶的），得到该位置的头指针（第一个节点），然后遍历单链表，找到后删除。
遍历的过程中要注意两种可能：
- 要删除的节点是第一个节点
- 要删除的节点是中间某个节点或者最后一个节点
bool Erase(const K& key)
{
Hash hs;
Node* ret = Find(key);
if (ret)
{
size_t hashi = hs(ret->_kv.first) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到该位置的头节点
Node* prev = nullptr;//前面的节点连接
while (cur)
{
if (cur->_kv.first == key)
{
if (prev)//第一个节点不是要删除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具体节点删除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，删除失败
{
return false;
}
}
2.2 kv模型哈希桶源代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//仿函数
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
//节点
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
template<class K, class V, class Hash = HashFind<K>>
class HashTable
{
typedef HashNode<K,V> Node;
public:
//构造
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
//析构
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
//查找
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到当前位置头节点
while (cur)
{
if (cur->_kv.first == key)//找到了
{
return cur;
}
cur = cur->_next;
}
//cur为空，不存在这个数据
return nullptr;
}
//插入
bool Insert(const pair<K,V>& kv)
{
//重复元素不能插入
if (Find(kv.first))
{
return false;
}
Hash hs;
//扩容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空间
//将旧表的节点移到新表中，再交换
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(_table[i]->_kv.first) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入数据
size_t hashi = hs(kv.first) % _table.size();//表中的位置
Node* newNode = new Node(kv);//新节点
//头插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
//删除
bool Erase(const K& key)
{
Hash hs;
Node* ret = Find(key);
if (ret)
{
size_t hashi = hs(ret->_kv.first) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到该位置的头节点
Node* prev = nullptr;//前面的节点连接
while (cur)
{
if (cur->_kv.first == key)
{
if (prev)//第一个节点不是要删除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具体节点删除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，删除失败
{
return false;
}
}
private:
vector<Node*> _table;
size_t _n = 0;
};
三、改造哈希桶
前面的哈希桶的数据类型是固定的kv模型，为了后面方便模拟实现unordered_set和unordered_map，将数据类型改成T，这个T可以是key，也可以是kv。到底是哪个取决于使用的是unordered_set还是unordered_map，用的是unordered_set，模板就用unordered_set的仿函数，另一个同理。
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
Find的返回值修改为迭代器，Insert的返回值修改为pair< iterator, bool>
3.1 begin+end
1️⃣begin
遍历哈希表，一旦遇到有节点的位置，返回该位置的迭代器。迭代器需要传两个参数，该位置的头指针和当前哈希表（与后面实现迭代器类中的成员变量对应）
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
}
2️⃣end
返回的是最后一个节点的下一个位置，单链表的最后一个节点的下一个是空指针，所以返回迭代器，参数传的是空指针和当前哈希表。
iterator end()
{
return iterator(nullptr, this);
}
3.2 迭代器
虽然哈希表的结构用的是vector，但是每个位置是单链表，++操作不能像数组一样就行，所以要对每个节点的迭代器进行封装，方便++找到下一个节点。
注意：每个位置的桶是单链表，所以没有前置- -
模板参数有KeyOfT和Hash是因为前置++需要数据类型的仿函数和转换为无符号整数的仿函数，这里先说明一下。迭代器的成员有节点应该就可以了，为什么还要哈希表类变量？因为等会前置++的代码中要通过哈希函数计算节点数据的位置，哈希函数要有哈希表的空间大小，没有哈希表类成员，怎么得到哈希表的空间大小。
其他的与之前一样，不作重复叙述了
template<class K, class T, class KeyOfT, class Hash>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> Ht;
typedef HashIterator< K, T, KeyOfT, Hash> Self;
Node* _node;
Ht* _ht;
HashIterator(Node* node, Ht* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
//....
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
3.2.1 前置++
分为两种情况：
- 当前节点的下一个节点不为空
- 当前节点的下一个节点为空
1️⃣情况一：
直接到下一个节点即可。
2️⃣情况二：
下一个节点为空，先计算当前节点在哈希表的位置（具体哪个桶），然后在该位置往后开始找，只要遇到有节点的位置，下一个节点就是它；如果后面都没有节点，下一个节点就是空。
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (_ht->_table.size() == hashi)
{
_node = nullptr;
}
}
return *this;
}
3.3 改造后哈希桶与迭代器源代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//仿函数
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
//节点
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
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 KeyOfT, class Hash>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> Ht;
typedef HashIterator< K, T, KeyOfT, Hash> Self;
Node* _node;
Ht* _ht;
HashIterator(Node* node, Ht* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (_ht->_table.size() == hashi)
{
_node = nullptr;
}
}
return *this;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
template<class K, class T, class KeyOfT, class Hash>
friend struct HashIterator;
typedef HashNode<T> Node;
public:
typedef HashIterator <K, T, KeyOfT, Hash> iterator;
//迭代器
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
//构造
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
//析构
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
//查找
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到当前位置头节点
while (cur)
{
if (kot(cur->_data) == key)//找到了
{
return iterator(cur, this);
}
cur = cur->_next;
}
//cur为空，不存在这个数据
return end();
}
//插入
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
//重复元素不能插入
iterator pos = Find(kot(data));
if (pos != end())
{
return make_pair(pos, false);
}
Hash hs;
//扩容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空间
//将旧表的节点移到新表中，再交换
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(kot(_table[i]->_data)) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入数据
size_t hashi = hs(kot(data)) % _table.size();//表中的位置
Node* newNode = new Node(data);//新节点
//头插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return make_pair(iterator(newNode, this), true);
}
//删除
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
iterator ret = Find(key);
if (ret != end())
{
size_t hashi = hs(kot(ret._node->_data)) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到该位置的头节点
Node* prev = nullptr;//前面的节点连接
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev)//第一个节点不是要删除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具体节点删除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，删除失败
{
return false;
}
}
private:
vector<Node*> _table;
size_t _n = 0;
};
四、模拟实现unordered_set
unordered_set是k模型，它的仿函数就返回key。模板参数有key和Hash，Hash是用来转换key变成无符号整数的。其他接口调用哈希桶的即可。
#include "HashTable.h"
namespace yss
{
template <class K, class Hash = HashFind<K>>
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKeyOfT, HashFind<K>>::iterator iterator;
//迭代器
iterator begin()
{
return _ht.begin();
}
iterator end()
{
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:
HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}
typename的作用是把HashTable<K, const K, SetKeyOfT, HashFind< K >>::iterator当做一个类型，而不是变量。typedef就是重命名。
五、模拟实现unordered_map
unordered_map是kv模型，仿函数传的是kv中的key。除了查找、插入、删除外，还有operator[]，可以进行统计元素等操作
#include "HashTable.h"
namespace yss
{
template <class K, class V, class Hash = HashFind<K>>
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFind<K>>::iterator iterator;
//迭代器
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
//插入
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);
}
//operator[]
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
