例如:数据集合{1,7,6,4,5,9}; 哈希函数设置为:hash(key) = key % capacity;
和
(i != j),有
!=
,但有:Hash(
) == Hash(
),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,
按照哈希函数Hash(key) = key% p(p<=m)
, 将关键码转换成哈希地址
= (
+
)% m, 或者:
= (
-
)% m。其中: i = 1,2,3…,
是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。示例如下所示:
每一个元素格子可以分成三种状态:
enum STATE
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数————可用于识别荷载因子
代码如下所示:
HashData<const K, V>* Find(const K& key)
{
// 线性探测
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state == EXIST
&& _table[hashi]._kv.first == key)
{
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
插入过程基本程序设计思路:
_n * 10 / _table.size() >= 7
,进入扩容_table[hashi]._state == EXIST
,
进行 二次探测 hashi %= _table.size();
重新寻找新hashi
3.找到状态为EMPTY的hashi时,存入数据,调整状态
_table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n;
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
// 扩容
//if ((double)_n / (double)_table.size() >= 0.7)
if (_n * 10 / _table.size() >= 7) //荷载因子
{
size_t newSize = _table.size() * 2;
// 遍历旧表,重新映射到新表
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
// 遍历旧表的数据插入到新表即可
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
// 线性探测
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST)
{
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
删除过程基本程序设计思路:
// 按需编译
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
()
,让其实现函数的功能
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
struct DefaultHashFunc<string>
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
// BKDR
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
//调用时
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
...};
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
// BKDR
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace open_address
{
enum STATE
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
public:
HashTable()
{
_table.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
// 扩容
//if ((double)_n / (double)_table.size() >= 0.7)
if (_n * 10 / _table.size() >= 7)
{
size_t newSize = _table.size() * 2;
// 遍历旧表,重新映射到新表
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
// 遍历旧表的数据插入到新表即可
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
// 线性探测
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST)
{
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key)
{
// 线性探测
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state == EXIST
&& _table[hashi]._kv.first == key)
{
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
// 按需编译
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数
};
}
//哈希桶
namespace hash_bucket
{
HashTable...//哈希表
HashNode...//节点
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
}
//哈希表
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
....};
//节点
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};
// 头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
引入:
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = _table.size()*2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
if(...)//剩余操作
}
// 遍历旧表,顺手牵羊,把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];//旧表
while (cur)
{
Node* next = cur->_next;//保存下一个地址
//找到新的对应位置
size_t hashi = hf(cur->_kv.first) % newSize; //hf为仿函数,在开散列相关章可以查看
//头插到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
//把旧表置空
_table[i] = nullptr;
}
//最后交换新旧表首元素地址
_table.swap(newTable);
bool Insert(const pair<K, V>& kv)
{
if(Find(kv.first))
{
return false;
}
HashFunc hf;
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = _table.size()*2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
// 遍历旧表,顺手牵羊,把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kv.first) % _table.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
namespace hash_bucket
{
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_table.resize(10, 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;
}
}
bool Insert(const pair<K, V>& kv)
{
if(Find(kv.first))
{
return false;
}
HashFunc hf;
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = _table.size()*2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
// 遍历旧表,顺手牵羊,把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kv.first) % _table.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
cout << cur->_kv.first <<":"<< cur->_kv.second<< "->";
cur = cur->_next;
}
printf("NULL\n");
}
cout << endl;
}
private:
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
};
}
#include"HashTable.h"
int main()
{
HashTable<int, int> ht;
int a[] = { 1,111,4,7,15,25,44,9 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Erase(15);
auto ret = ht.Find(4);
//ret->_kv.first = 41;
ret->_kv.second = 400;
//HashTable<string, string, StringHashFunc> dict;
HashTable<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("left", "xxx"));
auto dret = dict.Find("left");
//dret->_kv.first = "xx";//不可修改,const
dret->_kv.second = "左边";
string s1("xxx");
string s2("xxx");
DefaultHashFunc<string> hf;
cout << hf(s1) << endl;
cout << hf(s2) << endl;
cout << hf("bacd") << endl;
cout << hf("abcd") << endl;
cout << hf("abbe") << endl;
cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;
return 0;
}