当前位置:

哈希及哈希表的实现

访客 2023-09-19 398 0

目录

哈希及哈希表的实现

一、哈希的引入 

二、概念

三、哈希冲突

四、哈希函数

常见的哈希函数

1、直接定址法

2、除留余数法

五、哈希冲突的解决

1、闭散列

2、开散列


一、哈希的引入 

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log_2 N),搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。

这种思想就是我们接下来要讲的哈希了。


二、概念

如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
当向该结构中:
插入元素:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

当有这些数据时:1,4,5,6,7,9。我们可以通过下图的方式去插入数据。

 用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快。


三、哈希冲突

按照上面的方式,如果我们插入的是 1,2,32,222,7,9这几个数呢?

我们发现,如果按照哈希的思想去插入的话,2,32,22将会被放在同一个位置,这样就会引起一些麻烦。如果我去访问下标为2位置的数据,到底访问的哪一个呢?我们将这种现象称为哈希冲突。

不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。


四、哈希函数

引起哈希冲突的一个原因可能是:哈希函数设计不够合理。

常见的哈希函数

1、直接定址法

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B。
优点:简单、均匀。
缺点:需要事先知道关键字的分布情况。
使用场景:适合查找比较小且连续的情况。

2、除留余数法

设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p (p<=m),将关键码转换成哈希地址。


五、哈希冲突的解决

1、闭散列

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。

那么这个下一个位置怎么确定呢?我们有两种方法来帮助我们寻找“下一个”位置。

~ 线性探测 

比如三中的情况,插入2之后,现在需要插入元素32,先通过哈希函数计算哈希地址为2,因此32理论上应该插在该位置,但是该位置已经放了值为2的元素,即发生哈希冲突。这时我们就需要去寻找该位置后面的空位置了。

线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

如下图,32只能插入在3的位置了。 

 注:采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素
会影响其他元素的搜索。比如删除元素2,如果直接删除掉,32查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

在有限的空间内,随着我们插入的数据越来越多,冲突的概率也越来越大,查找效率越来越低,所以闭散列的冲突表不可能让它满了,所以我们就引入了负载因子:

负载因子(载荷因子):等于表中的有效数据个数/表的大小,衡量表的满程度,在闭散列中负载因子不可能超过1(1代表满了)。一般情况下,负载因子一般在0.7左右。负载因子越小,冲突概率也越小,但是消耗的空间越大,负载因子越大,冲突概率越大,空间的利用率越高。

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){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}};namespace closehash{enum State{EMPTY,DELETE,EXIST};template<class K,class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:bool insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newsize);for (auto& e : _tables){if (e._state == EXIST){newHT.insert(e._kv);}}_tables.swap(newHT._tables);}Hash hash;size_t index = hash(kv.first) % _tables.size();//如果kv.first是string类型,那么就无法取模,因此我们要使用仿函数将其转换成整型//线性探测while (_tables[index]._state == EXIST){index++;index %= _tables.size();}_tables[index]._kv = kv;_tables[index]._state = EXIST;_size++;return true;}HashData<K, V>* Find(const K& key){if (_tables.size() == 0){return nullptr;}Hash hash;size_t hashi = hash(key) % _tables.size();size_t start = hashi;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();if (hashi == start){break;}}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_size--;return true;}elsereturn false;}private:vector<HashData<K, V>> _tables;size_t _size = 0; //存储了多少个有效数据};

2、开散列

概念:开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

 

从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

那么是不是我们只需要开固定的空间,然后其他的数据就一直连接到对应的桶的后面,那样桶是不是太长了呢?

桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容。

增容条件:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容。

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 Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;free(cur);cur = next;}_tables[i] = nullptr;}}bool insert(const pair<K, V>& kv){//去重if (Find(kv.first)){return false;}Hash hash;//扩容if (_size == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10;vector<Node*> newTables;newTables.resize(newsize, nullptr);//将旧表中结点移动映射到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hash(kv.first) % _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_size++;return true;}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;elsecur = cur->_next;}return nullptr;}bool erase(const K& key){if (_tables.size() == 0){return nullptr;}Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){// 1、头删// 2、中间删if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_size--;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;size_t _size = 0;};

发表评论

  • 评论列表
还没有人评论,快来抢沙发吧~