目录
一.哈希的相关概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log2N)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该结构中:
- 插入元素:根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素:对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
44插入的位置和4冲突了,我们将这种情况称为哈希冲突
哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
发生哈希冲突该如何处理呢？
二.哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理
哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数:
1. 直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2. 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p将关键码转换成哈希地址)
3. 平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
4. 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。
通常应用于关键字长度不等时采用此法
6.数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况
注意:哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
三.哈希冲突解决
解决哈希冲突两种常见的方法是：闭散列和开散列
1.闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
1. 线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
//线性探测
//计算d中的key在表中映射的位置
size_t index = koft(d) % _tables.size();
while (_tables[index]._state == EXITS)
{
if (koft(_tables[index]._data) == koft(d))
{
return false;
}
++index;
if (index == _tables.size())
{
index = 0;
}
}
_tables[index]._data = d;
_tables[index]._state = EXITS;
_num++;采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
enum State
{
EMPTY,
EXITS,
DELETE,
};
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_num;
return true;
}
else
{
return false;
}
}思考：哈希表什么情况下进行扩容？如何扩容？
我们通过负载因子来决定什么情况下增容,负载因子 = 表中数据/表的大小 -->衡量哈希表满的程度
表越接近满,插入数据越容易冲突,冲突越多,效率越低,哈希表并不是满了增容,在开放定址法中,一般负载因子到0.7左右就开始增容,负载因子越小,冲突概率越低,整体效率越高,但是浪费空间越大,所以负载因子一般取一个折中值
KeyOfT koft;
if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
{
//开2倍的新表
//遍历旧表的数据,将旧表的数据在新表中重新映射
//释放旧表
vector<HashData> newtables;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newtables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXITS)
{
size_t index = koft(_tables[i]._data) % newtables.size();
while (newtables[index]._state == EXITS)
{
++index;
if (index == _tables.size())
{
index = 0;
}
}
newtables[index] = _tables[i];
}
}
_tables.swap(newtables);
}我们也可以通过复用insert来实现
HashTable<K, T, KeyOfT> newht;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newht._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXITS)
{
newht.Insert(_tables[i]._data);
}
}
_tables.swap(newht._tables);线性探测优点：实现非常简单
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？
2.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法 为：H_i = (H_0 + i^2 )% m.其中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小
//二次探测
size_t start = koft(d) % _tables.size();
size_t index = start;
int i = 1;
while (_tables[index]._state == EXITS)
{
if (koft(_tables[index]._data) == koft(d))
{
return false;
}
index = start + i * i;
++i;
index %= _tables.size();
}
_tables[index]._data = d;
_tables[index]._state = EXITS;
_num++;
return true; void TestHashTables()
{
HashTable<int, int, SetKeyOfT<int>> ht;
ht.Insert(2);
ht.Insert(12);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(1);
ht.Insert(5);
ht.Insert(6);
}线性探测
二次探测
通过图片可以看出他们之间插入位置的不同
2.开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中
1.开散列的增容
我们通过负载因子来判断什么时候增容,当负载因子为1的时候增容
//如果负载因子等于1就增容,避免大量的哈希冲突
if ( _tables.size() == _num)
{
vector<Node*> newtables;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newtables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = HashFunc(koft(cur->_data)) % newtables.size();
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}因为我们计算映射的位置时是用数据%表的大小,但是有时候我们会传入string类似的类型,他们不可以直接%,所以我们需要一个仿函数来处理这些不能直接%的类型
template<class K>
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct _Hash<std::string>
{
size_t operator()(const std::string& key)
{
//BKDR Hash
size_t hash = 0;
for (size_t i = 0; i < key.size(); ++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key);
}我们特化了一个处理string类型的模板,当传入string的时候就会调用特化的模板,其余情况使用默认的
2.开散列的插入
size_t index = HashFunc(koft(data)) % _tables.size();
//查找值在不在表中
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return false;
}
else
{
cur = cur->_next;
}
}
//头插(尾插也可以)
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_num;
return true;3.开散列的查找
Node* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}4.开散列的删除
bool Erase(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_tables[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}void TestHashTables1()
{
HashTable<int, int, SetKeyOfT<int>> ht;
ht.Insert(2);
ht.Insert(12);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(1);
ht.Insert(5);
ht.Insert(6);
ht.Insert(16);
ht.Insert(26);
ht.Insert(36);
}
void TestHashTables2()
{
HashTable<string, string, SetKeyOfT<string>> ht;
ht.Insert("sort");
ht.Insert("vector");
ht.Insert("string");
}
我们可以看到冲突的数据排列在一个链表中
即便传的是string也能够正常处理
四.整体代码
1.HashTable.h
#pragma once
#include<vector>
#include<string>
template<class K>
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
template<class K, class V>
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
namespace close_hash
{
enum State
{
EMPTY,
EXITS,
DELETE,
};
template<class T>
struct HashData
{
T _data;
State _state;
};
//unordered_set --> HashTable<K, K>
//unordered_map --> HashTable<K, pair<K, V>>
template<class K, class T, class KeyOfT>
class HashTable
{
typedef HashData<T> HashData;
public:
bool Insert(const T& d)
{
//负载因子 = 表中数据/表的大小 -->衡量哈希表满的程度
//表越接近满,插入数据越容易冲突,冲突越多,效率越低
//哈希表并不是满了增容,在开放定址法中,一般负载因子到0.7左右就开始增容
//负载因子越小,冲突概率越低,整体效率越高,但是浪费空间越大
//所以负载因子一般取一个折中值
KeyOfT koft;
if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
{
//开2倍的新表
//遍历旧表的数据,将旧表的数据在新表中重新映射
//释放旧表
/*vector<HashData> newtables;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newtables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXITS)
{
size_t index = koft(_tables[i]._data) % newtables.size();
while (newtables[index]._state == EXITS)
{
++index;
if (index == _tables.size())
{
index = 0;
}
}
newtables[index] = _tables[i];
}
}
_tables.swap(newtables);*/
HashTable<K, T, KeyOfT> newht;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newht._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXITS)
{
newht.Insert(_tables[i]._data);
}
}
_tables.swap(newht._tables);
}
//线性探测
//计算d中的key在表中映射的位置
/*size_t index = koft(d) % _tables.size();
while (_tables[index]._state == EXITS)
{
if (koft(_tables[index]._data) == koft(d))
{
return false;
}
++index;
if (index == _tables.size())
{
index = 0;
}
}
_tables[index]._data = d;
_tables[index]._state = EXITS;
_num++;*/
//二次探测
size_t start = koft(d) % _tables.size();
size_t index = start;
int i = 1;
while (_tables[index]._state == EXITS)
{
if (koft(_tables[index]._data) == koft(d))
{
return false;
}
index = start + i * i;
++i;
index %= _tables.size();
}
_tables[index]._data = d;
_tables[index]._state = EXITS;
_num++;
return true;
}
HashData* Find(const K& key)
{
KeyOfT koft;
//计算key在表中映射的位置
size_t index = koft(key) % _tables.size();
while (_tables[index]._state != EMPTY)
{
if (koft(_tables[index]._data) == key)
{
if (_tables[index]._state == EXITS)
{
return &_tables[index];
}
else if (_tables[index]._state == DELETE)
{
return nullptr;
}
}
++index;
if (index == _tables.size())
{
index = 0;
}
return nullptr;
}
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_num;
return true;
}
else
{
return false;
}
}
private:
vector<HashData> _tables;
size_t _num = 0;//存了几个有效数据
};
void TestHashTables()
{
HashTable<int, int, SetKeyOfT<int>> ht;
ht.Insert(2);
ht.Insert(12);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(1);
ht.Insert(5);
ht.Insert(6);
}
}
namespace open_hash
{
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 KeyOfT,class Hash>
struct __HashTableIterator
{
typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
Node* _node;
HT* _pht;
__HashTableIterator(Node* node, HT* pht) :_node(node),_pht(pht) { }
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT koft;
size_t i = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();
++i;
for (; i < _pht->_tables.size(); i++)
{
Node* cur = _pht->_tables[i];
if (cur)
{
_node = cur;
return *this;
}
}
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K>
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct _Hash<std::string>
{
size_t operator()(const std::string& key)
{
//BKDR Hash
size_t hash = 0;
for (size_t i = 0; i < key.size(); ++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash=_Hash<K>>
class HashTable
{
typedef HashNode<T> Node;
public:
friend struct __HashTableIterator<K, T, KeyOfT, Hash>;
typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
~HashTable()
{
Clear();
}
void Clear()
{
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;
}
}
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key);
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT koft;
//如果负载因子等于1就增容,避免大量的哈希冲突
if (_tables.size() == _num)
{
vector<Node*> newtables;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newtables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = HashFunc(koft(cur->_data)) % newtables.size();
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t index = HashFunc(koft(data)) % _tables.size();
//查找值在不在表中
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return make_pair(iterator(cur, this), false);
}
else
{
cur = cur->_next;
}
}
//头插(尾插也可以)
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_num;
return make_pair(iterator(newnode, this), true);
}
Node* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
bool Erase(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_tables[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables;
size_t _num = 0;
};
void TestHashTables1()
{
HashTable<int, int, SetKeyOfT<int>> ht;
ht.Insert(2);
ht.Insert(12);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(1);
ht.Insert(5);
ht.Insert(6);
ht.Insert(16);
ht.Insert(26);
ht.Insert(36);
}
void TestHashTables2()
{
HashTable<string, string, SetKeyOfT<string>> ht;
ht.Insert("sort");
ht.Insert("vector");
ht.Insert("string");
HashTable<string, string, SetKeyOfT<string>>::iterator it = ht.begin();
while (it != ht.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}2.Hash.cpp
#include<iostream>
using namespace std;
#include"HashTable.h"
int main()
{
close_hash::TestHashTables();
open_hash::TestHashTables1();
open_hash::TestHashTables2();
return 0;
}