哈希概念 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
文章图片
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。但是有一个问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
哈希冲突 对于两个数据元素的关键字 Ki和 Kj(i != j)，有 Ki != Kj，但有：Hash(Ki) == Hash(Kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词"。
发生哈希冲突该如何处理呢？
哈希函数 引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
1.直接定址法（常用）
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。优点：简单、均匀。缺点：需要事先知道关键字的分布情况。使用场景：适合查找比较小且连续的情况。
2.除留余数法（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。
【数据结构|哈希表详解】注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但还是无法避免哈希冲突
哈希冲突解决 解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
1.线性探测
比如之前图中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入：
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
文章图片
删除：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
//哈希表每个空间给个标记
//EMPTY此位置空，EXIST此位置已经有元素，DELETE元素已经删除
enum State
{
EMPTY,
EXIST,
DELETE
};
线性探测的实现
#include
#include
using namespace std;
//哈希表每个空间给个标记
//EMPTY此位置空，EXIST此位置已经有元素，DELETE元素已经删除
enum State
{
EMPTY,
EXIST,
DELETE
};
template
struct HashNode
{
T _data;
State _state;
};
//set仿函数
template
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
//map仿函数
template
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
template
class HashTable
{
typedef HashNode Node;
public:
HashTable(size_t N = 10)
{
_table.resize(N);
//resize后可以使用[]随机访问
for (size_t i = 0;
i < _table.size();
++i)
{
_table[i]._state = EMPTY;
}
_size = 0;
} bool Insert(const T& data)
{
//检查容量
CheckCapacity();
KeyOfT koft;
size_t index = koft(data) % _table.size();
while (_table[index]._state == EXIST)
{
if (koft(_table[index]._data) == koft(data))
{
return false;
}
//线性探测
++index;
if (index == _table.size())
{
index = 0;
}
}
_table[index]._data = https://www.it610.com/article/data;
_table[index]._state = EXIST;
++_size;
return true;
} Node* Find(const K& key)
{
KeyOfT koft;
int index = key % _table.size();
while (_table[index]._state != EMPTY)
{
if (_table[index]._state == EXIST && koft(_table[index]._data) == key)
{
return &_table[index];
}
++index;
if (index == _table.size())
{
index = 0;
}
}
return nullptr;
} bool Erase(const K& key)
{
Node* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
return false;
} void MapPrint()
{
for (size_t i = 0;
i < _table.size();
++i)
{
if (_table[i]._state == EXIST)
{
cout << _table[i]._data.first << ":" << _table[i]._data.second << endl;
}
}
cout << endl;
} void SetPrint()
{
for (size_t i = 0;
i < _table.size();
++i)
{
if (_table[i]._state == EXIST)
{
cout << _table[i]._data << " ";
}
}
cout << endl;
}
private:
vector _table;
size_t _size;
};
哈希表什么情况下进行扩容？如何扩容？
文章图片
void CheckCapacity()
{
if (_size * 10 / _table.size() >= 7)
{
int newCapacity = _table.size() * 2;
HashTable newHT(newCapacity);
for (size_t i = 0;
i < _table.size();
++i)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._data);
}
}
_table.swap(newHT._table);
}
}
线性探测优点：实现非常简单
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？
2.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i2) % m，或者：Hi = (H0 - i2) % m。其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。 对于之前图中如果要插入44，产生冲突，使用解决后的情况为：
文章图片
文章图片
研究表明：当表的长度为质数且表负载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的负载因子a不超过0.5，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
文章图片
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时（即负载因子等于1的时候），可以给哈希表增容。但是随着数据量过大，一个桶中链表节点仍然会非常多，这个时候我们可以将单链表换成平衡树挂在每一个桶中，很大程度上提高了效率。
void CheckCapacity()
{
KeyOfT koft;
//通过仿函数获取K或者K/V模型中的K
//如果负载因子==1，则扩容
if (_num == _table.size())
{
vector newTable;
size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
newTable.resize(newSize);
for (size_t i = 0;
i < _table.size();
++i)
{
Node* cur = _table[i];
while (cur)
{
//重新计算data在newTable中的位置
//HashFunc函数是用来将K中的数据类型转换成整型方便寻找哈希地址
size_t index = HashFunc(koft(cur->_data)) % newTable.size();
//将_table中的data搬移到newTable中
Node* next = cur->_next;
cur->_next = newTable[index];
newTable[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
}
只能存储key为整形的元素，其他类型怎么解决？
实际运用中，key一般为string类型
字符串哈希算法
template
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
//模板特化，字符串转整型
template<>
struct _Hash>
{
size_t operator()(const string& key)
{
//BKDR算法
size_t hash = 0;
for (size_t i = 0;
i < key.size();
++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
开散列的实现
#include
#include
using namespace std;
template
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
: _data(data)
, _next(nullptr)
{}
};
template
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
//模板特化，字符串转整型
template<>
struct _Hash>
{
size_t operator()(const string& key)
{
//BKDR算法
size_t hash = 0;
for (size_t i = 0;
i < key.size();
++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
//set的仿函数
template
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
//map的仿函数
template
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
template>
class HashOpen
{
typedef HashNode Node;
public:
~HashOpen()
{
Clear();
} void Clear()
{
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;
}
} size_t HashFunc(const K& key)
{
Hash hash;
return hash(key);
} bool Insert(const T& data)
{
KeyOfT koft;
//通过仿函数获取K或者K/V模型中的K
//如果负载因子==1，则扩容
if (_num == _table.size())
{
vector newTable;
size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
newTable.resize(newSize);
for (size_t i = 0;
i < _table.size();
++i)
{
Node* cur = _table[i];
while (cur)
{
//重新计算data在newTable中的位置
//HashFunc函数是用来将K中的数据类型转换成整型方便寻找哈希地址
size_t index = HashFunc(koft(cur->_data)) % newTable.size();
//将_table中的data搬移到newTable中
Node* next = cur->_next;
cur->_next = newTable[index];
newTable[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}//检查data是否已经存在
size_t index = HashFunc(koft(data)) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return false;
}
cur = cur->_next;
}
//插入data
Node* newNode = new Node(data);
newNode->_next = _table[index];
_table[index] = newNode;
++_num;
return true;
} Node* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
} bool Erase(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _table.size();
Node* cur = _table[index];
Node* prev = nullptr;
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_table[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_num;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector _table;
size_t _num = 0;
};
测试用例：
void Test1()
{
HashOpen> h;
h.Insert(4);
h.Insert(14);
h.Insert(24);
h.Insert(6);
h.Insert(16);
h.Insert(46);
h.Insert(8);
h.Insert(21);
h.Insert(5);
h.Insert(85);
h.Insert(27);
auto pos = h.Find(24);
if (pos)
{
cout << "找到了" << endl;
}
else
{
cout << "没找到" << endl;
} bool ret = h.Erase(24);
if (ret)
{
cout << "删除成功" << endl;
}
else
{
cout << "删除失败" << endl;
}
}void Test2()
{
HashOpen, MapKeyOfT> h;
h.Insert(make_pair(3, 3));
h.Insert(make_pair(23, 23));
h.Insert(make_pair(13, 13));
h.Insert(make_pair(5, 5));
h.Insert(make_pair(85, 85));
h.Insert(make_pair(35, 35));
h.Insert(make_pair(44, 44));
h.Insert(make_pair(56, 56));
auto pos = h.Find(35);
if (pos)
{
cout << "找到了" << endl;
}
else
{
cout << "没找到" << endl;
} bool ret = h.Erase(35);
if (ret)
{
cout << "删除成功" << endl;
}
else
{
cout << "删除失败" << endl;
}
}void Test3()
{
HashOpen, string, SetKeyOfT>> h;
h.Insert("BSTree");
h.Insert("AVLTree");
h.Insert("RBTree");
cout << h.HashFunc("BSTree") << endl;
cout << h.HashFunc("AVLTree") << endl;
cout << h.HashFunc("RBTree") << endl;
}
开散列与闭散列比较 应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
模拟实现unordered_map、unordered_set（底层哈希）
#pragma once
#include
#include
using namespace std;
template
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
: _data(data)
, _next(nullptr)
{}
};
// 前置声明
template
class HashOpen;
template
struct __HashTableIterator
{
typedef __HashTableIterator Self;
typedef HashOpen HT;
typedef HashNode Node;
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->_table.size();
++i;
for (;
i < _pht->_table.size();
i++)
{
Node* cur = _pht->_table[i];
if (cur)
{
_node = cur;
return *this;
}
}
_node = nullptr;
}
return *this;
} bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct _Hash>
{
size_t operator()(const string& key)
{
//BKDR算法
size_t hash = 0;
for (size_t i = 0;
i < key.size();
++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
template>
class HashOpen
{
typedef HashNode Node;
public:
//迭代器中会用到私有_table，设置为友元
friend struct __HashTableIterator < K, T, KeyOfT, Hash>;
typedef __HashTableIterator iterator;
iterator begin()
{
for (size_t i = 0;
i < _table.size();
i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
} iterator end()
{
return iterator(nullptr, this);
}
public:
~HashOpen()
{
Clear();
} void Clear()
{
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;
}
} size_t HashFunc(const K& key)
{
Hash hash;
return hash(key);
} pair Insert(const T& data)
{
KeyOfT koft;
//如果负载因子==1，则扩容
if (_num == _table.size())
{
vector newTable;
size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
newTable.resize(newSize);
for (size_t i = 0;
i < _table.size();
++i)
{
Node* cur = _table[i];
while (cur)
{
//重新计算data在newTable中的位置
size_t index = HashFunc(koft(cur->_data)) % newTable.size();
//将_table中的data搬移到newTable中
Node* next = cur->_next;
cur->_next = newTable[index];
newTable[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}//检查data是否已经存在
size_t index = HashFunc(koft(data)) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return make_pair(iterator(cur, this), false);
}
cur = cur->_next;
}
//插入data
Node* newNode = new Node(data);
newNode->_next = _table[index];
_table[index] = newNode;
++_num;
return make_pair(iterator(newNode, this), true);
;
} Node* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
} bool Erase(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key) % _table.size();
Node* cur = _table[index];
Node* prev = nullptr;
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_table[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector _table;
size_t _num = 0;
};
#pragma once
#include "HashOpen.hpp"namespace Unordered_Map
{
template
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
public:
typedef typename HashOpen, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _h.begin();
}iterator end()
{
return _h.end();
}pair insert(const pair& kv)
{
return _h.Insert(kv);
}V& operator[](const K& key)
{
pair ret = _h.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashOpen, MapKeyOfT> _h;
};
void test_unordered_map()
{
unordered_map, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("string", "字符串"));
dict["left"] = "修改左边";
dict["end"] = "尾部";
//unordered_map::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}
#pragma once
#include "HashOpen.hpp"namespace Unordered_Set
{
template
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashOpen::iterator iterator;
iterator begin()
{
return _h.begin();
}iterator end()
{
return _h.end();
}pair insert(const K& k)
{
return _h.Insert(k);
}
private:
HashOpen _h;
};
void test_unordered_set()
{
unordered_set s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
unordered_set::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
推荐阅读
- 算法|JavaScript数据结构与算法 - 哈希表详解
- 数据结构与算法|【Java数据结构】哈希表详解
- 哈希表|哈希表2--Hashmap的实现详解
- 《C语言杂俎》|证明堆排序的时间复杂度
- 指针|【发际线大作战】C++学习记录之用户自定义数据类型
- C++|set、map及AVL树
- 蓝桥真题|【蓝桥真题3】蓝桥改革变难，想进国赛这些能力你可缺一不可
- 算法|开学季——经典计算机教材带你起飞！
- python|python数据结构-链表