目录
一、哈希概念
1、哈希冲突
2、哈希冲突的解决
a、闭散列
🟢插入
🟢查找
🟢删除
🟢其他类型的数据
🟢实现
b、 开散列
🟢插入
🟢查找
🟢删除
🟢析构
🟢其他类型的数据
🟢实现
一、哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)
1、哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
2、哈希冲突的解决
解决哈希冲突两种常见的方法是：闭散列和开散列
a、闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把 key 存放到冲突位置中的“下一个” 空位置中去。
会使用线性探测的方法。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
🟢插入
通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素
插入就会面临扩容的问题，如果我们按照之前的思路在原来空间上直接扩容，这样size就会改变，每个元素对应的地址位置会发生变化。所以我们直接新建一个哈希表，将旧表的数据遍历插入到新的表中，然后交换新表和旧表。
插入的数值先求出哈希值，如果对应的哈希值的状态是存在，哈希++，当遇到没有放入值的地方时，将插入的值放入，将状态改为存在，关键字++。
🟢查找
当状态存在并且 kv 相等时，返回相等的值，如果没有找到，返回空。为了避免删除之后的值被查到到，查找时对数组的状态进行限制。
🟢删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
所以我们记录每一个位置的状态：哈希表每个空间给个标记，EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
找到值将要删除的值的状态设置为DELETE，关键字的个数--，如果没有找到返回 false。
🟢其他类型的数据
当我们想统计字符串或者其他类型的数据时，我们需要找到其对应的地址。之前 int 类型可以直接用key值%capacity 的值 。当处理其他的值时，我们可以使用仿函数将其强制转换为int类型。string不能直接转换为int，我们刻画一个仿函数处理string类型。
🟢实现
namespace open_address
{
enum Status
{
EMPTY,
EXIST,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
Status _s; //状态
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
cout << key << ":" << hash << endl;
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//负载因子是空间占有率=存储数据的个数/表的大小
// 负载因子0.7就扩容
if (_n * 10 / _tables.size() == 7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V> newHT;
newHT._tables.resize(newSize);
// 遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
Hash hf;
size_t hashi =hf(kv.first) % _tables.size();
while (_tables[hashi]._s == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._s = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key)
{
Hash hf;
size_t hashi = hf(key) % _tables.size();
while (_tables[hashi]._s != EMPTY)
{
if (_tables[hashi]._s == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
}
return NULL;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
//printf("[%d]->%d\n", i, _tables[i]._kv.first);
cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
}
else if (_tables[i]._s == EMPTY)
{
printf("[%d]->\n", i);
}
else
{
printf("[%d]->D\n", i);
}
}
cout << endl;
}
// 伪删除法
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_s = DELETE;
--_n;
return true;
}
else
{
return false;
}
}
private:
vector<HashData<K,V>> _tables;
size_t _n = 0; // 存储的关键字的个数
};
void TestHT1()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//HashTable<string, int, HashFuncString> ht;
HashTable<string, int> ht;
for (auto& e : arr)
{
//auto ret = ht.Find(e);
HashData<string, int>* ret = ht.Find(e);
if (ret)
{
ret->_kv.second++;
}
else
{
ht.Insert(make_pair(e, 1));
}
}
ht.Print();
ht.Insert(make_pair("apple", 1));
ht.Insert(make_pair("sort", 1));
ht.Insert(make_pair("abc", 1));
ht.Insert(make_pair("acb", 1));
ht.Insert(make_pair("aad", 1));
ht.Print();
}
}
b、 开散列
开散列概念：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。
🟢插入
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，哈希表是一个指针数组，指向第一个关键码。
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点， 再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。
扩容的逻辑：
①当负载因子到达1时就进行扩容
②按照二倍扩容开空间，开辟一个新的哈希表。
③遍历旧表，将旧表上的结点全部拿下来，按照插入逻辑迁到新表上。
④最后遍历完后，将新表和旧表交换一下，这样数据就到旧表上了。如果我们采用相同的方法，要拷贝每一个哈希桶，但是哈希桶的数据都是一样的，这样会造成浪费。
插入的逻辑：
①对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，
②为插入的元素新建一个节点，将元素头插到哈希桶里。
为什么要头插而不是尾插呢？尾插也可以，但是尾插还需要找尾，头插直接插入到哈希表里即可，让新结点的尾部指向原来的新结点，而原来新结点的位置就变成了新结点。
③关键个数n++；
🟢查找
计算数值对应的哈希地址，看该哈希地址上是否有该值。不过由于哈希冲突，可能查找的值在哈希桶头结点的后面。所以需要遍历一下哈希桶。
🟢删除
删除逻辑：
①首先根据除留余数法计算数值的哈希地址。
②遍历所在的哈希桶，在遍历时，需要记录前面结点的位置。
③找到要删除结点后，删除（让前一个节点的next指向删除节点的next），没有找到就继续往后找，记录前面位置。
③注意要删除结点可能是头结点。
🟢析构
vector不是会自动调用析构函数吗？为什么我们还需要自己写析构函数呢？
vector存储的数据指针类型，是自定义类型，没有默认构造，所以我们开辟的结点的那些空间，需要我们自己释放，不然无法释放。析构需要遍历哈希表，都释放即可。
🟢其他类型的数据
现在只能存储key为整型的元素，如果遇到其他类型需要怎么处理呢？
这里就需要使用仿函数
对于数值类型我们可以直接强制类型转换成 size_t 类型，这样做的好处就是对于负数我们也可以进行取模了。如果对于string类型，那我们可以将string类型的字符全部相加，这样就会得到一个数值。不过这样可能会存在大量的冲突，可能两个不同的字符串，最后得到的数值是一样大的。所以为了减少冲突。又大佬依据大量的数据处理，得出，每个字符都乘数131后再相加，这样就可以大大减少冲突概率。
我们可以使用一个模板的特化，根据传的模板类型来调用不同的仿函数了。模板的特化，当数据类型是 int 的时候就默认使用 HashFunc<int>,当数据类型是string类型时，就默认使用HashFunc<string>
🟢实现
namespace hash_bucket
{
template<class K, class V>
struct HashNode
{
HashNode* _next;
pair<K, V> _kv;
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
template <class K>
struct HashFunc//默认的仿函数可以让数据模
{
size_t operator()(const K& key)
{
return (size_t)key;
//将key强行类型转化
//这样作的意义：可以负数也可以进行模了
}
};
//template <class string>
//struct HashFunc
//{
// size_t operator()(const string& str)
// {
// //为了减少冲突，我们将字符串的每个字符的值相加
// size_t hash = 0;
// for (auto& it : str)
// {
// hash *= 131;
// hash += it;
// }
// return hash;
// }
//};
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
//字母相同，顺序不同
hash *= 31;
hash += e;
}
cout << key << ":" << hash << endl;
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10);
}
~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;
}
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
// 负载因子最大到1时，扩容
if (_n == _tables.size())
{
vector<Node*> newTables;
newTables.resize(_tables.size() * 2, nullptr);
// 遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
//扩容后，空间size变大了，有的数据就可能会存到不同的桶里了
//拿下来的结点要重新计算放进哪个位置
Node* cur = _tables[i];
while (cur)
{
//记录cur的下一个节点
Node* next = cur->_next;
Hash hf;
// 挪动到映射的新表
size_t hashi = hf(kot(cur->data)) % newTables.size();
cur->_next = newTables[i];
//头插 这个结点的 接到插入结点的前面对吧
//那么next就接到newtavle[i]
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
else
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hf;
size_t hashi =hf(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
//如果删除的是头结点，指向头结点的next
if (prev = nullptr)
{
_tables[hashi] = 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 _n = 0;
};
}
