目录
前言
Part1. 哈希函数
Part2. 插入操作
Part3. 查找操作
Part4. 删除操作
Part5. unordered_map和unordered_set的封装
Part6. 链式哈希表的封装实现
结语
前言
上篇文章：【知识讲解】 哈希表的介绍与实现-CSDN博客
在上篇文章我们讲述了哈希表的开放寻址法，也谈到了他的一些缺点，今天我们来讲一讲链式哈希表的实现，他相比较于开放寻址法有着许多的优势，我们来看看吧。
let's go!!!!!!!!
Part1. 哈希函数
由于除留余数法要用到模运算，其只适用于无符号整形类型（因为负号模后为负数），但是我们在实际运用时，会用到string还有自己设计的一些类型，所以我们需要一个函数让各种类型转化为无符号整型，我们来看代码：
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>//其他无法直接转化为无符号整型的用特化来转化为无符号整型
struct Hash<std::string>
{
size_t operator()(const std::string& key)
{
size_t hash0 = 0;
for (int i = 0; i < key.size(); i++)
{
hash0 = hash0 * 131 + key[i];//乘以131来使得分散
}
return hash0;
}
};
用码道免费领 1 个月 Token
cpp
运行
Part2. 插入操作
对于链式哈希表我们怎么进行插入呢？我们来看：
我们根据x的key计算出来他在数组中的映射下标，再使用头插这样就做到了O（1）的时间复杂度，关键在于扩容，按道理来说这个是用链表不会超过容量，但是当每个节点下面挂的链表节点更多，在查询时花费时间就会多，所以当负载因子大于一时，我们就要扩容，让数组更多，自然下面挂的链表的节点就会少，增加查询的效率。我们来看扩容：
bool insert(const std::pair<K, V> kv)
{
if (find(kv.first) != nullptr)
{
return false;
}
if (_n >=_tables.size())//扩容
{
std::vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));//新的数组 用素数表扩容
for (int i = 0; i < _tables.size(); i++)
{
Node* tem= _tables[i];
while (tem != nullptr)/
{
Node* nextp = tem->_next;
size_t hash0 = HashFunc()(tem->_kv.first) % newtable.size();//计算出每一个节点在新数组的映射位置
tem->_next = newtable[hash0];//用头插插入
newtable[hash0] = tem;
tem = nextp;
}
_tables[i] = nullptr;
}
_tables.swap(newtable);//交换
}
size_t hash0 = HashFunc()(kv.first) % _tables.size();//插入
Node* newnode = new Node(kv);
newnode->_next = _tables[hash0];
_tables[hash0] = newnode;
++_n;
return true;
}
用码道免费领 1 个月 Token
cpp
运行
Part3. 查找操作
查找就比较简单了，我们来看：
Node* find(const K& key)
{
size_t hash0 = HashFunc()(key)% _tables.size();
Node* tem = _tables[hash0];//开始在对应的地方查找
while (tem != nullptr)
{
if (tem->_kv.first == key)
{
return tem;
}
tem = tem->_next;
}
return nullptr;
}
用码道免费领 1 个月 Token
cpp
运行
Part4. 删除操作
删除的操作就和链表的删除相似，就是删除链表的头节点和中间节点这两个情况，我们来看：
bool erase(const K& key)
{
size_t hash0 = HashFunc()(key) % _tables.size();
Node* tem = _tables[hash0];
Node* prev = nullptr;
while (tem != nullptr)
{
if (tem->_kv.first == key)
{
if (prev == nullptr)//分为头节点和中间节点的两个情况
{
_tables[hash0] = tem->_next;
}
else
{
prev->_next = tem->_next;
}
delete tem;
_n--;
return true;
}
else
{
prev = tem;
tem = tem->_next;
}
}
return false;
}
用码道免费领 1 个月 Token
cpp
运行
Part5. unordered_map和unordered_set的封装
上面我们完成了链式哈希表的实现，接下来我们就可以使用这个来完成对于unordered_map和unordered_set的封装。我们来看：
这个的封装关键在于迭代器的实现，这迭代器的实现与map和set的迭代器实现相似。我们来都看看吧。我们以unordered_map来举例。
template<class K,class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const std::pair<const K,V>& key)//萃取器 萃取出元素方便后续的使用
{
return key.first;
}
};
public:
typedef typename HashTable< K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;//封装迭代器
typedef typename HashTable< K, std::pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator end()
{
return _ht.end();
}
iterator begin()
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
std::pair<iterator, bool> insert(const std::pair<const K,V>& key)
{
return _ht.insert(key);
}
iterator find(const K& key)
{
return _ht.find(key);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = insert({ key,V() });//unordered_map特有的[] 当这个key不存在时 就自动插入
return ret.first->second;
}
void printf_all_node()const
{
const_iterator it = begin();
while (it != end())
{
std::cout << it->first << " ";
++it;
}
std::cout << std::endl;
}
private:
HashTable< K, std::pair<const K,V>, MapKeyOfT> _ht;//成员
};
用码道免费领 1 个月 Token
cpp
运行
Part6. 链式哈希表的封装实现
我们来看代码：
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct Hash<std::string>
{
size_t operator()(const std::string& key)
{
size_t hash0 = 0;
for (int i = 0; i < key.size(); i++)
{
hash0 = hash0 * 131 + key[i];
}
return hash0;
}
};
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
template<class K, class Ref, class Ptr, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashIterator;
template<class K, class T, class KeyOfT,class HashFunc = Hash<K>>
class HashTable
{
typedef HashNode<T> Node;
public:
typedef HashIterator<K, T&, T*, T, KeyOfT, HashFunc> iterator;
typedef HashIterator<K, const T&, const T*, T, KeyOfT, HashFunc> const_iterator;
HashTable()
:_tables(__stl_next_prime(0))
, _n(0)
{
}
~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
while (_tables[i] != nullptr)
{
erase(KeyOfT()(_tables[i]->_data)); //析构函数 复用代码
}
}
}
HashTable(const HashTable<K,T, HashFunc>& hash)
{
for (int i = 0; i < hash._tables.size(); i++)
{
Node* cur = hash._tables[i];
while (cur != nullptr)
{
this->insert(cur->_kv);//复用代码
cur = cur->_next;
}
}
}
HashTable<K, T, HashFunc>& operator=(HashTable<K, T, HashFunc> hash)
{
swap(hash);
return *this;
}
iterator end()
{
return iterator(nullptr, this);
}
iterator begin()
{
if (_n == 0)
{
return end();
}
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i] != nullptr)
{
return iterator(_tables[i],this);
}
}
return end();
}
const_iterator end()const
{
return const_iterator(nullptr, this);
}
const_iterator begin()const
{
if (_n == 0)
{
return end();
}
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i] != nullptr)
{
return const_iterator(_tables[i], this);
}
}
return end();
}
void swap(HashTable<K,T, HashFunc>& hash)
{
std::swap(_tables, hash._tables);
std::swap(_n, hash._n);
}
std::pair<iterator, bool> insert(const T& kv)
{
if (find(KeyOfT()(kv)) != end())
{
return { find(KeyOfT()(kv)),false };
}
if (_n >= _tables.size())
{
std::vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));
for (int i = 0; i < _tables.size(); i++)
{
Node* tem = _tables[i];
while (tem != nullptr)
{
Node* nextp = tem->_next;
size_t hash0 = HashFunc()(KeyOfT()(tem->_data)) % _tables.size();
tem->_next = newtable[hash0];
_tables[hash0] = tem;
tem = nextp;
}
_tables[i] = nullptr;;
}
_tables.swap(newtable);
}
size_t hash0 = HashFunc()(KeyOfT()(kv)) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hash0];
_tables[hash0] = newnode;
++_n;
return { iterator(newnode,this),true };
}
iterator find(const K& key)
{
size_t hash0 = HashFunc()(key) % _tables.size();
Node* tem = _tables[hash0];
while (tem != nullptr)
{
if (KeyOfT()(tem->_data) == key)
{
return iterator(tem,this);
}
tem = tem->_next;
}
return end();
}
bool erase(const K& key)
{
size_t hash0 = HashFunc()(key) % _tables.size();
Node* tem = _tables[hash0];
Node* prev = nullptr;
while (tem != nullptr)
{
if (KeyOfT()(tem->_data) == key)
{
if (prev == nullptr)
{
_tables[hash0] = tem->_next;
}
else
{
prev->_next = tem->_next;
}
delete tem;
_n--;
return true;
}
else
{
prev = tem;
tem = tem->_next;
}
}
return false;
}
size_t size()const
{
return _tables.size();
}
Node* head_node(size_t i)const//由于private修饰我们多加接口来用于迭代器的使用
{
return _tables[i];
}
private:
inline unsigned long __stl_next_prime(unsigned long n)
{
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 = std::lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
std::vector<Node*> _tables;
size_t _n = 0;
};
template<class K,class Ref,class Ptr ,class T, class KeyOfT, class HashFunc>
class HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, HashFunc> HT;
typedef HashIterator<K, Ref, Ptr, T, KeyOfT, HashFunc> Self;
public:
HashIterator(Node* node, const HT* ht)//这里需要加上const上面在const_iterator时 会传过来const修饰的this 如果不加上const 权限缩小报错 因此我们需要加上const 权限平级
:_node(node)
,_ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Self& operator++()//++的实现 要是到了一条链的终点 则跳转到下一个下标的链表开头
{
Node* old = _node;
_node = _node->_next;
if (_node == nullptr)
{
size_t hash0 = HashFunc()(KeyOfT()(old->_data)) % _ht->size();
hash0++;
while (hash0 < _ht->size())
{
if (_ht->head_node(hash0) != nullptr)
{
_node = _ht->head_node(hash0);
break;
}
hash0++;
}
}
return *this;
}
private:
Node* _node;
const HT* _ht;
};
用码道免费领 1 个月 Token
cpp
运行
结语
这篇文章我们认识到了unordered_map和unordered_set的封装，接下来，小编还会带来C++11的知识，敬请期待~
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~