哈希
概念
存储的值和存储位置的映射的关联关系
常见的哈希函数:
1.直接定址法--(常用)
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀
缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况
2.除留余数法--(常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,
按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3.创建一个哈希表
enum State {
EMPTY,
EXIST,
DELETE
};
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K, class V>
struct HashTable {
public:
private:
vector<HashData<K, V>> _tables;
size_t n = 0;
};
哈希冲突解决
a. 闭散列开放定址法(本质是当前位置冲突了,后面找一个合适的位置继续存储(x: 线性探测 y: 二次探测))
b. 开散列拉链法/哈希桶
线性探测解决哈希冲突
插入:
i = key % 表的大小
如果i位置已经有值了,就往后走找空位置,放进去
查找:
i = key % 表的大小
如果i位不是要查找的key就往后查找,直到找到或者遇到空
如果找到表结尾位置,要往头回绕
哈希冲突越多,效率就越低
负载因子/载荷因子 = 实际存进去的数据个数/表的大小
闭散列(开放定址法):一般会控制在0.7左右
线性探测的插入Insert
先看Find里面有没有Key,有的话就结束插入。
但是在映射key的哈希值时,如果是int那就好办,如果是string类型怎么办呐?
所以这里我们要写写一个哈希仿函数, 因为string比较常用,我们把string特化一下
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) {
size_t hash = 0;
for (auto e : s) {
hash += e;
hash *= 131;
}
return hash;
}
};
现在我们就可以写Find函数了
HashData<K, V>* Find(const K& key) {
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY) {
if (_tables[hashi]._kv.first == key
&& _tables[hashi]._state == EXIST) {
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
再来写Insert插入,这里负载因子大于0.7就去扩容,保证不满,且不会死递归
bool Insert(const pair<K, V> kv) {
if (Find(kv.first))
return false;
if (_n * 10 / _tables.size() >= 7) { // 注意这里是size,而不是capacity
HashTable<K, V, Hash> NewHT(_tables.size() * 2);
for (auto& e : _tables)
if (e._state == EXIST) // 存在才加入
NewHT.Insert(e._kv); // 插入e._kv
_tables.swap(NewHT._tables); // 交换tables即可
}
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._state == EXIST) {
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n; // 最后记得++_n个数
return true; // 最后记得返回true
}
线性探测的删除Erase
Erase只需把存在的状态设置成DELETE
bool Erase(const K& key) {
HashData<K, V>* ret = Find(key);
if (ret) {
--_n;
ret->_state = DELETE;
return true;
}
else
return false;
}
哈希桶解决哈希冲突
首先创造一个节点,为链表
struct HashNode {
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K, V> kv) //记得列表初始化
:_next(nullptr)
,_kv(kv)
{}
};
创建一个Hash表,加上默认构造函数
template<class K, class V>
struct HashTable {
typedef HashNode Node;
HashTable() {
_tables.resize(10, nullptr);
}
private:
vector<Node*> _tables;
size_t n = 0;
};
添加仿函数
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) {
size_t hash = 0;
for (auto e : s) {
hash += e;
hash *= 131;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
写一个Find函数,看tables里面有没有重复,这样可以防止后面再去查找是否含有这个元素
Node* Find(const K& key) {
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
再写一个析构函数,保证可析构
~HashTable() {
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
哈希桶的Insert插入函数
bool Insert(const pair<K, V> kv) {
if (Find(kv.first))
return false;
Hash hs;
if (_n == _tables.size()) {
vector<Node*> NewHT(_tables.size() * 2, nullptr);
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(cur->_kv.first) % NewHT.size(); // 需要hs一下first
cur->_next = NewHT[hashi];//直接用cur来链接,不需要自己newnode
NewHT[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(NewHT);
}
size_t hashi = hs(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n; //不要忘记++_n
return true;
}
哈希桶的Erase删除函数
bool Erase(const K& key) {
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev)
prev->_next = cur->_next;
else
_tables[hashi] = cur->_next;
delete cur; // 记得delete cur和--_n
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
哈希封装umap、set
根据红黑树封装map和set的时候,需要用一个红黑树来封装map和set
所以这里我们依然用一个哈希表来封装unordered_map、unordered_set
创建一个HashNode
template<class T>
struct HashNode {
HashNode<T>* _next;
T _data;
HashNode(const T data)
:_next(nullptr)
, _data(data)
{}
};
创建一个__HTIterator
template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;//HT*
__HTIterator(Node* node, HT* ht)
:_node(node)
,_ht(ht)
{}
T& operator*() {//T&
return _node->_data;
}
Self& operator++() {
if (_node->_next) {
_node = _node->_next;
}
else {
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(cur->_data)) % _ht->_tables.size();//->
hashi++;
while (hashi < _ht->_tables.size()) {
if (_ht->_tables[hashi]) {
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_tables.size())
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s) {
return _node != s._node;
}
};
把HashTable用KeyOfT改一下
template<class K, class T, class KeyOfT, class Hash>
struct HashTable {
typedef HashNode<T> Node;
public:
typedef __HTIterator<K, T, KeyOfT, Hash> iterator;
iterator begin() {
for (int i = 0; i < _tables.size(); ++i) {
if (_tables[i]) {
return iterator(_tables[i], this);
}
}
return end();
}
iterator end() {
return iterator(nullptr, this);
}
HashTable() {
_tables.resize(10, nullptr);
_n = 0; // _n = 0 不要忘记
}
~HashTable() {
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const T& data) { //T&
KeyOfT kot;
if (Find(kot(data)))
return false;
Hash hs;
if (_n == _tables.size()) {
vector<Node*> NewHT(_tables.size() * 2, nullptr);
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % NewHT.size(); // 需要hs一下first
cur->_next = NewHT[hashi];//直接用cur来链接,不需要自己newnode
NewHT[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(NewHT);
}
size_t hashi = hs(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev)
prev->_next = cur->_next;
else
_tables[hashi] = cur->_next;
delete cur; // 记得delete cur和--_n
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n;
};
添加一个MyOrdered_set.h
#include "HashTable.h"
namespace lkt {
template <class K, class Hash = HashFunc<K>>
class unordered_set {
struct SetKeyOfT
{
const K& operator()(const K& key) {
return key;
}
};
typedef typename lkt2::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
iterator begin() {
return _ht.begin();
}
iterator end() {
return _ht.end();
}
bool Insert(const K& key) {
return _ht.Insert(key);
}
private:
lkt2::HashTable<K, V, SetKeyOfT, Hash> _ht;
};
}
在__HTIterator前添加,前置声明
template<class K, class T, class KeyOfT, class Hash>
struct HashTable;
在HashTab里面友元一个
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;
添加一个MyOrdered_map.h
#include "HashTable.h"
namespace lkt {
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 lkt2::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
iterator begin() {
return _ht.begin();
}
iterator end() {
return _ht.end();
}
bool Insert(const pair<K, V> kv) {
return _ht.Insert(kv);
}
private:
lkt2::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
HashTable汇总代码
#pragma once
#include <iostream>
using namespace std;
#include <string>
#include <vector>
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) {
size_t hash = 0;
for (auto e : s) {
hash += e;
hash *= 131;
}
return hash;
}
};
namespace lkt2 {
template<class T>
struct HashNode {
HashNode<T>* _next;
T _data;
HashNode(const T data)
:_next(nullptr)
, _data(data)
{}
};
template<class K, class T, class KeyOfT, class Hash>
struct HashTable;
template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
__HTIterator(Node* node, HT* ht)
:_node(node)
,_ht(ht)
{}
T& operator*() {//T&
return _node->_data;
}
Self& operator++() {
if (_node->_next) {
_node = _node->_next;
}
else {
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();//->
hashi++;
while (hashi < _ht->_tables.size()) {
if (_ht->_tables[hashi]) {
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_tables.size())
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s) {
return _node != s._node;
}
private:
Node* _node;
HT* _ht;//HT*
};
template<class K, class T, class KeyOfT, class Hash>
struct HashTable {
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;
typedef HashNode<T> Node;
public:
typedef __HTIterator<K, T, KeyOfT, Hash> iterator;
iterator begin() {
for (int i = 0; i < _tables.size(); ++i) {
if (_tables[i]) {
return iterator(_tables[i], this);
}
}
return end();
}
iterator end() {
return iterator(nullptr, this);
}
HashTable() {
_tables.resize(10, nullptr);
_n = 0; // _n = 0 不要忘记
}
~HashTable() {
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const T& data) { //T&
KeyOfT kot;
if (Find(kot(data)))
return false;
Hash hs;
if (_n == _tables.size()) {
vector<Node*> NewHT(_tables.size() * 2, nullptr);
for (int i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % NewHT.size(); // 需要hs一下first
cur->_next = NewHT[hashi];//直接用cur来链接,不需要自己newnode
NewHT[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(NewHT);
}
size_t hashi = hs(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key) {
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev)
prev->_next = cur->_next;
else
_tables[hashi] = cur->_next;
delete cur; // 记得delete cur和--_n
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n;
};
}