哈希表概念
哈希表可以简单理解为:把数据转化为数组的下标,然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据,直接计算出这个数据的下标,然后就可以直接访问数组对应的位置,所以可以用O(1)的复杂度直接找到数据。
其中,这个数据对应的数字叫做关键码(Key),这个把关键码转化为下标的规则,叫做哈希函数(Hash)。
要注意的是,有一些数据并不是整型,比如字符串,对象等等。对于这种数据,我们要先用一套规则把它们转化为整数(关键码),然后再通过哈希函数映射为数组下标。
哈希函数
哈希函数原则:
- 哈希函数转换后,生成的地址(下标)必须小于哈希表的最大地址(下标)
- 哈希函数计算出来的地址(下标)必须均匀地分布
- 哈希函数尽可能简单
直接定址法
取关键字的某个线性函数为哈希表的地址:
除留余数法
假设哈希表的地址数目为
m
,取Key
对m
取模后得到的值作为下标
闭散列 - 开放定址法
闭散列,也叫做开放定址法,当发生哈希冲突时,如果哈希表没有被装满,说明哈希表中还有空位置,那么我们可以把发生冲突的数据放到下一个空位置去。
基本结构
首先我们需要一个枚举,来标识哈希表的不同状态:
enum State
{
EMPTY,
EXIST,
DELETE
};
EMPTY
:空节点EXIST
:数值存在DELETE
:数值被删除
哈希表的基本结构:
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:
HashTable(size_t size = 10)
{
_tables.resize(size);
}
private:
vector<HashData<K, V>> _tables;//哈希表
size_t _n = 0;//元素个数
};
HashTable
构造函数:
HashTable(size_t size = 10)
{
_tables.resize(size);
}
查找
想要在哈希表中查找数据,无非就遵顼以下规则:
通过哈希函数计算出数据对应的地址
去地址处查找,如果地址处不是目标值,往后继续查找
遇到EMPTY
还没有找到,说明数据不存在哈希表中
遇到DELETE
和EXIST
,继续往后查找
代码如下:
HashData<K, V>* Find(const K& key)
{
size_t hashi = 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;
}
但是当前的代码存在一个问题:哈希表作用于泛型,key % _tables.size()
有可能是违法的行为,因为key
可能不是一个数字。
对此我们可以在模板中多加一个仿函数的参数,用户可以在仿函数中自定义数据 -> 整型
的转换规则,然后我们在对这个整型使用除留余数法获取地址。
在那之前,我们可以先写一个仿函数,用于处理整型 -> 整型
的转化:
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
在STL中,整型-> 整型
转化的函数,被写为了一个模板,而这个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)//把字符串的每一个字符ASCII码值加起来
{
hash += e;
hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
}
return hash;
}
};
我们将这个HashFunc<K>
仿函数作为哈希表的第三个模板参数的默认值:
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{};
通过仿函数来统一获得整型,再进行除留余数操作:
Hash hs;
size_t hashi = hs(key) % _tables.size();
插入
插入的基本逻辑如下:
- 先通过Find接口,查找目标值在不在哈希表中,如果目标值已经存在,返回flse,表示插入失败
- 通过哈希函数计算出目标值对应的下标
- 向下标中插入数据:如果下标对应的位置已经有数据,往后查找,直到某一个位置为
EMPTY
或者DELETE.
如果下标对应的位置没有数据,直接插入- 插入后,把对应位置的状态转化为
EXIST
代码如下:
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
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++;//哈希表中的元素个数+1
return true;
}
当这个哈希表越满,我们查找数据的效率就越低,甚至说:如果查找一个不存在的数据,我们可能要用O(N)的复杂度遍历整个哈希表.因此我们因该把哈希表的负载率控制在一定值,当超过一定值,我们就要进行扩容操作。
if ((double)_n / _tables.size() >= 0.7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V, Hash> newHT(newSize);
for (auto& e : _tables)
{
if (e._state == EXIST)
newHT.Insert(e._kv);
}
_tables.swap(newHT._tables);
}
插入总代码:
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if ((double)_n / _tables.size() >= 0.7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V, Hash> newHT(newSize);
for (auto& e : _tables)
{
if (e._state == EXIST)
newHT.Insert(e._kv);
}
_tables.swap(newHT._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++;
return true;
}
删除
先通过Find接口找到要删除的值
- 如果没找到,返回false,表示删除失败
- 如果找到,把对应节点的状态改为
DELETE
最后再把哈希表的
_n - 1
,表示存在的节点数少了一个。
代码如下:
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
_n--;
return true;
}
return false;
}
总代码展示
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)//把字符串的每一个字符ASCII码值加起来
{
hash += e;
hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
}
return hash;
}
};
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 Hash = HashFunc<K>>
class HashTable
{
public:
HashTable(size_t size = 10)
{
_tables.resize(size);
}
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;
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if ((double)_n / _tables.size() >= 0.7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V, Hash> newHT(newSize);
for (auto& e : _tables)
{
if (e._state == EXIST)
newHT.Insert(e._kv);
}
_tables.swap(newHT._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++;
return true;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
_n--;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//元素个数
};
开散列 - 哈希桶
在STL库中,采用的是更加优秀的开散列方案。
哈希表的数组vector
中,不再直接存储数据,而是存储一个链表的指针。当一个数值映射到对应的下标后,就插入到这个链表中。其中每一个链表称为一个哈希桶,每个哈希桶中,存放着哈希冲突的元素.
基本结构
对于每一个节点,其要存储当前节点的值,也要存储下一个节点的指针,基本结构如下:
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 = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable(size_t size = 10)
{
_tables.resize(size);
}
private:
vector<Node*> _tables; //链表指针数组
size_t _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;
}
}
查找
查找的基本逻辑如下:
- 先通过哈希函数计算出数据对应的下标
- 通过下标找到对应的链表
- 遍历链表,找数据:如果某个节点的数据匹配上了,返回该节点指针,如果遍历到了nullptr,返回空指针表示没找到
代码如下:
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;
}
插入
插入的基本逻辑如下:
- 先通过Find接口,查找目标值在不在哈希表中,如果目标值已经存在,返回flse,表示插入失败
- 通过哈希函数计算出目标值对应的下标
- 向下标中插入数据
代码如下:
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();//计算下标
Node* newNode = new Node(kv);//创建节点
newNode->_next = _tables[hashi];//头插
_tables[hashi] = newNode;
++_n;//更新元素个数
return true;
}
关于扩容:如果我们单纯的进行插入,就要把原先的所有节点释放掉,再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来,因此我们要重写一个逻辑,把原先的节点进行迁移。
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(cur->_kv.first) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr; //防止移交的节点被析构
}
_tables.swap(newTables);
}
删除
删除逻辑:
- 通过哈希函数计算出对应的下标
- 到对应的哈希桶中查找目标值
- 如果找到,删除对应的节点
- 如果没找到,返回false表示删除失败
_n - 1
表示删除了一个元素
代码如下:
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;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
代码展示
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)//把字符串的每一个字符ASCII码值加起来
{
hash += e;
hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
}
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 = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable(size_t size = 10)
{
_tables.resize(size);
}
~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;
}
}
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;
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
Hash hs;
//哈希桶情况下,负载因子到1才扩容
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(cur->_kv.first) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr; //防止移交的节点被析构
}
_tables.swap(newTables);
}
size_t hashi = hs(kv.first) % _tables.size();
Node* newNode = new Node(kv);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
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;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables; //链表指针数组
size_t _n = 0;//元素个数
};