哈希的介绍及实现
发布时间
阅读量：
阅读量
目录
一.undered_set undered_map
1.介绍
二.底层结构
2.1哈希概念
2.2哈希函数
2.3哈希冲突解决
2.3.1闭散列
2.3.2开散列
3.模拟实现
3.1存储结点的改造
3.2.unordered_map与unordered_set
3.3迭代器的实现
一.undered_set undered_map
1.介绍
二者的用法与set和map是一样的，只不过不会对其数据进行排序。
举个例子：
void test1()
{
unordered_set<int> s;
s.insert(3);
s.insert(9);
s.insert(5);
s.insert(2);
s.insert(99);
s.insert(4);
for (auto ch : s)
{
cout << ch << " "；
}
cout << endl;
}
结果：99 3 9 5 2 4
AI写代码 void test3()
{
unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "剩余"));
dict["string"];
dict["apple"];
dict["left"] = "剩余";
dict["string"] = "字符串";
for (auto ch : dict)
{
cout << ch.first << "-" << ch.second << endl;
}
}
结果:
sort-排序
string-字符串
left-剩余
apple-
AI写代码比较下它们的性能：
随级生成1000000个数，看下它们插入，查找的时间。
void test2()
{
int N = 1000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (int i = 0; i < N; i++)
{
v.push_back(rand()+i);
}
int begin1 = clock();
unordered_set<int> u_s;
set<int> s;
for (auto ch : v)
{
u_s.insert(ch);
}
int end1 = clock();
int begin2 = clock();
for (auto ch : v)
{
s.insert(ch);
}
int end2 = clock();
cout << "unordered_set插入的时间为：" << end1-begin1 << endl;
cout << "set插入的时间为：" << end2 - begin2 << endl;
int begin3 = clock();
for (auto ch : v)
{
u_s.find(ch);
}
int end3 = clock();
int begin4 = clock();
for (auto ch : v)
{
s.find(ch);
}
int end4 = clock();
cout << "unordered_set查找的时间为：" << end3 - begin3 << endl;
cout << "set查找的时间为：" << end4 - begin4 << endl;
}
AI写代码结果：
二.底层结构
2.1哈希概念
顺序结构以及平衡树 中，元素关键码与其存储位置之间没有对应的关系，因此在 查找一个元素
时，必须要经过关键码的多次比较 。 顺序查找时间复杂度为 O(N) ，平衡树中为树的高度，即
O(log_2 N)
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快的找到该元素。
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则查找成功。
这种方式就叫做哈希（散列）方法，哈希方法中使用的转换函数叫做哈希（散列）函数，构造出来的结构叫做哈希表（散列表）。
举个例子：
哈希函数设置为： hash(key) = key % capacity ; capacity 为存储元素底层空间总的大小。
，但可能会出现冲突的情况，例如11%10=1；
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突 或哈希碰撞 。
2.2哈希函数
哈希函数设计的原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值
域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
AI写代码若哈希函数设计不合理，则可能出现哈希冲突的情况
常见哈希函数 ：
2. 直接定址法 --( 常用 )
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2. 除留余数法 --( 常用 )
设散列表中允许的 地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，
**按照哈希函数：Hash(key) = key% p(p <=m),将关键码转换成哈希地址 **
3. 平方取中法 --( 了解 )
**假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址 ； **
再比如关键字为 4321 ，对它平方就是 18671041 ，抽取中间的 3 位 671( 或 710) 作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突，
解决哈希冲突 两种常见的方法是： 闭散列 和 开散列。
2.3哈希冲突解决
2.3.1闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置的下一个位置
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 。
例如：
插入元素时： 
删除元素时：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素
会影响其他元素的搜索 。
线性探测采用标记的伪删除法来删除一个元素 。 enum State { EMPTY , EXIST , DELETE };
二次探测 ：
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位
置的方式往后逐个找，二次探测可改为每次往后走i*i个位置。
负载因子：
模拟实现一个可存储键值对的哈希（闭散列）：
思路：1.先实现一个结构体，里面可存储键值对，在加上一个状态来标志数据是否存在。
2.当数据类型不能直接转换为整数进行映射时，可增加一个仿函数来使其转换为对应的整 数
3.构建一个类，创建一个vector（用vector来存储这些结构体），和一个变量记录数据的个 数。
enum State
{
EMPTY,
EXITS,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state=EMPTY;
};
AI写代码 template<class K>
struct DefaultHash
{
size_t operator()(const K& key)
{
return size_t(key);
}
};
template<>
struct DefaultHash<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto ch : key)
{
hash = hash * 131 + ch;
}
return hash;
}
};
创建对应的仿函数来进行转换
AI写代码 template<class K, class V, class HashFunc = DefaultHash<K>>
class HashTable
{
typedef HashData<K, V> Data;
public:
bool insert(const pair<K, V> kv)//当负载因子为0.7时进行扩容
{
if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)
{
size_t newsize = _size == 0 ? 10 : 10 * _size;
HashTable<K, V, HashFunc> newHT;
newHT._tables.resize(newsize);
for (auto& e : _tables)
{
if (e._state == EXITS)//若其旧表的数据存在，将其插入新表，扩容后，位置关系要重新映射
{
newHT.insert(e._kv);
}
}
newHT._tables.swap(_tables);//将旧表与新表的数据交换
}
HashFunc hf;//将对应的数据转换为整数
int Hashi = hf(kv.first) % (_tables.size());//用除留余数法进行映射
while (_tables[Hashi]._state==EXITS)
{
Hashi++;
Hashi %= _tables.size();
}
_tables[Hashi]._kv = kv;
_tables[Hashi]._state = EXITS;
++_size;
return true;
}
Data* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
HashFunc hf;
int Hashi = hf(key) % (_tables.size());
while (_tables[Hashi]._state!=EMPTY)
{
if (_tables[Hashi]._kv.first == key&&_tables[Hashi]._state!=DELETE)
{
return &_tables[Hashi];
}
Hashi++;
Hashi %= _tables.size();
}
return nullptr;
}
bool Erase(const K& key)//删除只需将该位置上数据的状态为置为DELETE
{
Data* ret = find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
else
{
return false;
}
}
private:
vector<Data> _tables;
size_t _size = 0; // 存储关键字个数
};
AI写代码研究表明： 当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任
何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在
搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子 a 不超过 0.5 ， 如果超出
必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
2.3.2开散列
开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中 。
例如：
若对应下表存在数据，肯定是发生冲突的元素。
模拟实现一个可存储键值对的哈希（开散列）
思路：
与上面基本类似，
1先实一个结构体，里面可存储键值对，在加上一个指针指向下一个结构体。
2.当数据类型不能直接转换为整数进行映射时，可增加一个仿函数来使其转换为对应的整 数
3.构建一个类，创建一个vector（用vector来存储这些结构体），和一个变量记录数据的个 数（指vector指桶的个数，不是指全部元素个数）。
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
HashData<K, V>* _next;
HashData(const pair<K,V>& kv)
:_kv(kv)
,_next(nullptr)
{
}
};
AI写代码
template<class K, class V, class HashFunc = DefaultHash<K>>
class HashTable
{
typedef HashData<K, V> Data;
public:
HashFunc hf;
~HashTable()//对于vector是内置类型，会自动调用它的析构函数，但vector里面是链表结构，是结点的指针，要逐一释放
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
while (cur)
{
Data* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool insert(const pair<K, V> kv)
{
if (find(kv.first))
return false;
if (_tables.size() == 0 || _tables.size()==_size)
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Data*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
while (cur)//插入时直接改变链接的关系，减小开销
{
Data* next = cur->_next;
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
}
newTable.swap(_tables);
}
int Hashi = hf(kv.first) % (_tables.size());
Data* newnode = new Data(kv);
newnode->_next = _tables[Hashi];
_tables[Hashi] = newnode;
++_size;
return true;
}
Data* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
int Hashi = hf(key)%_tables.size();先找到被查找元素对应下标，转换为链表的查找
Data* cur = _tables[Hashi];
while (cur != nullptr)
{
if (cur->_kv.first == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
bool erase(const K& key)
{
if (_tables.size() == 0)
return false;
int Hashi = hf(key) % _tables.size();先找到被删除元素对应下标，转换为链表的删除
Data* prev = nullptr;
Data* cur = _tables[Hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[Hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Data*> _tables;
size_t _size = 0; // 存储关键字个数
};
AI写代码3.模拟实现
与之前介绍的set与map类似，unordered_map与unordered_set的底层也是用了同一个结构，也是通过模板来进行适配（也是用开散列的方式实现的）。
先对哈希表进行改造。
3.1存储结点的改造
template<class T>
struct HashData
{
T _data;
HashData<T>* _next;
HashData(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
AI写代码T的类型可能是unordered_map传过来的键值对或者unordered_set传过来的int,自定义类型等。
3.2.unordered_map与unordered_set
由于在插入数据时，是根据第一个参数过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，所以与要一个仿函数来提取出第一个参数。
此外，为了不同类型的数据（如自定义类型）也可以通过关键码进行映射，最好把HashFunc函数放在unorder_Set，unorder_Map那一层，这样可以自己写一个仿函数来应对不同的数据类型。
template<class K, class HashFunc = DefaultHash<K>>
class unorder_Set
{
public:
struct setKey//提取出第一个参数。
{
const K& operator()(const K& key)
{
return key;
}
};
bool insert(const K& kv)
{
_Set.insert(kv);
}
bool find(const K& key)
{
return _Set.find(key);
}
bool erase(const K& key)
{
return _Set.erase(key);
}
private:
HashTable< K, K,setKey,HashFunc> _Set;
};
AI写代码 template<class K,class V, class HashFunc = DefaultHash<K>>
class unorder_Map
{
public:
struct mapKey//提取出第一个参数。
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
bool insert(const pair<K,V>& kv)
{
return _Map.insert(kv);
}
bool find(const K& key)
{
return _Map.find();
}
bool erase(const K& key)
{
return _Map.erase(key);
}
private:
HashTable< K, pair<K, V>, mapKey,HashFunc> _Map;
};
AI写代码 template<class K, class T, class Ofkey, class HashFunc>
class HashTable
{
typedef HashData<T> Data;
public:
HashFunc hf;//求第一个参数映射的下标
Ofkey hk;//取第一个参数
bool insert(const T& data)
{
bool pos = find(hk(data));
if (pos)
{
return false;
}
if (_tables.size() == 0 || _tables.size() == _size)
{
size_t newSize = _tables.size() == 0 ? 2 : _tables.size() * 2;
vector<Data*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
while (cur)
{
Data* next = cur->_next;
size_t hashi = hf(hk(cur->_data)) % _tables.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
}
newTable.swap(_tables);
}
int Hashi = hf(hk(data)) % (_tables.size());
Data* newnode = new Data(data);
newnode->_next = _tables[Hashi];
_tables[Hashi] = newnode;
++_size;
return true;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
while (cur)
{
Data* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool find(const K& key)
{
if (_tables.size() == 0)
return false;
int Hashi = hf(key) % _tables.size();
Data* cur = _tables[Hashi];
while (cur != nullptr)
{
if (hk(cur->_data) == key)
{
return true;
}
else
{
cur = cur->_next;
}
}
return false;
}
bool erase(const K& key)
{
if (_tables.size() == 0)
return false;
int Hashi = hf(key) % _tables.size();
Data* prev = nullptr;
Data* cur = _tables[Hashi];
while (cur)
{
if (hk((cur->_data)) == key)
{
if (prev == nullptr)
{
_tables[Hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Data*> _tables;
size_t _size = 0;
};
AI写代码画图分析一下：
结果：
3.3迭代器的实现
此处的迭代器要实现++，--等操作，
迭代器就是封装了存储数据的结点，同时迭代器在操作过程中，（例如一个桶遍历完，需要找到下一桶，所以还包要含储存这些结点的结构，此处包含HashTable的指针更容易实现。
template<class K,class T,class Ofkey,class HashFunc>
class Hash_iterator
{
typedef Hash_iterator<K, T, Ofkey, HashFunc> self;//重命名为self
typedef HashData<T> Node;//将存储信息的结点命名为Node
public:
Hash_iterator(Node* node,HashTable<K,T,Ofkey,HashFunc>* hash)//构造函数
:_node(node)
,_hash(hash)
{
}
self& operator++()
{
if (_node->_next != nullptr)
{
_node = _node->_next;
}
else//桶为空，则去查找下一个桶
{
HashFunc hf;//求第一个参数映射的下标
Ofkey hk;//取第一个参数
int hashi = hf(hk(_node->_data)) % _hash->_tables.size();
hashi++;
while (hashi < _hash->_tables.size())
{
if(_hash->_tables[hashi])
{
_node = _hash->_tables[hashi];
break;
}
else
{
hashi++;
}
}
if (hashi == _hash->_tables.size())
{
_node = nullptr;
}
return *this;
}
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const self& s) const
{
return _node != s._node;
}
bool operator==(const self& s) const
{
return _node == s._node;
}
private:
Node* _node;//每个结点的指针
HashTable<K, T, Ofkey, HashFunc>* _hash;//哈希表的指针
};
AI写代码哈希表拥有迭代器后，可增加begin()，end(),等函数，同时还可对insert，find函数进行改造，使其与STL库中的哈希更相似。
template<class K, class T,class Ofkey, class HashFunc>
class HashTable
{
typedef HashData<T> Data;
public:
template<class K, class T, class Ofkey, class HashFunc>
friend class Hash_iterator;
HashFunc hf;//求第一个参数映射的下标
Ofkey hk;//取第一个参数
typedef Hash_iterator<K, T, Ofkey, HashFunc> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
if (cur)
{
return iterator(cur, this);//this就是指这个哈希表的指针
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
pair<iterator,bool> insert(const T& data)//返回值是有迭代器和bool值组成的键值对
{
iterator pos = find(hk(data));//若插入失败，返回存在元素的迭代器，bool值为false
if (pos != end())
{
return make_pair(pos, false);
}
if (_tables.size() == 0 || _tables.size() == _size)
{
size_t newSize = _tables.size() == 0 ? 2 : _tables.size() * 2;
vector<Data*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Data* cur = _tables[i];
while (cur)
{
Data* next = cur->_next;
size_t hashi = hf(hk(cur->_data)) % _tables.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
}
newTable.swap(_tables);
}
int Hashi = hf(hk(data)) % (_tables.size());
Data* newnode = new Data(data);
newnode->_next = _tables[Hashi];
_tables[Hashi] = newnode;
++_size;
return make_pair(iterator(newnode, this), true)；//插入成功，返回新插入元素的迭代
//器，bool值为false
}
iterator find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr,this);
int Hashi = hf(key) % _tables.size();
Data* cur = _tables[Hashi];
while (cur != nullptr)
{
if (cur->_data==key)
{
eturn iterator(cur, this)；
}
else
{
cur = cur->_next;
}
}
return iterator(nullptr, this);
}
..............
.............
AI写代码 template<class K,class V, class HashFunc = DefaultHash<K>>
class unorder_Map
{
public:
struct mapKey
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
}
typedef typename HashTable<K, pair<K, V>, mapKey, HashFunc>::iterator iterator;
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;//ret.first是迭代器，也就是存储数据的结构体指针，重载了->,拿
// 到的是 &_node->_data;，此处编译器做了优化（此处的data是键值对）
}
iterator begin()
{
return _Map.begin();
}
iterator end()
{
return _Map.end();
}
pair<iterator, bool> insert(const pair<K,V>& kv)
{
return _Map.insert(kv);
}
iterator find(const K& key)
{
return _Map.find();
}
bool erase(const K& key)
{
return _Map.erase(key);
}
private:
HashTable< K, pair<K, V>, mapKey,HashFunc> _Map;
};
template<class K, class HashFunc = DefaultHash<K>>
class unorder_Set
{
public:
struct setKey
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename HashTable<K, K, setKey, HashFunc>::iterator iterator;
pair<iterator, bool> insert(const K& kv)
{
return _Set.insert(kv);
}
iterator find(const K& key)
{
return _Set.find(key);
}
bool erase(const K& key)
{
return _Set.erase(key);
}
private:
HashTable< K, K,setKey,HashFunc> _Set;
};
AI写代码全部评论 (0)
还没有任何评论哟~