哪里网站建设好,潍坊 logo设计公司,百度搜索推广是什么,精品课程网站设计该哈希表实现是闭散列实现法。
闭散列表#xff1a; 闭散列#xff1a;也叫开放定址法#xff0c;当发生哈希冲突时#xff0c;如果哈希表未被装满#xff0c;说明在哈希表中必然还有空位置#xff0c;那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻…该哈希表实现是闭散列实现法。
闭散列表 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢
线性探测 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
注意除了线性探测你还可以进行二次探测等看个人实现策略。
如何插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突 使用线性探测找到下一个空位置插入新元素 比如2.1中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4 因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
如何删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
线性探测实现插入 bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子0.7就扩容if (_n*10 / _tables.size() 7){size_t newSize _tables.size() * 2;HashTableK, V, Hash 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;}什么是负载因子 负载因子是关键词key的存储个数与哈希表内存大小之比一般取0.75左右这样做是为了提高存储效率只有百分之75的内存可以用剩余的百分之25是不存储的减少哈希冲突。
如何扩展内存 定义一个新的对象开好想要的内存将旧表的数据重新查到新的哈希表中旧表的数据分布与新表的数据分布不一样将旧表数据插入完之后再将新表的哈希表数据与旧表的数据进行交换。
哈希表的查找 HashDataK, 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;}
数据有三种状态存在删除为空。
存在和删除的状态下如果没有找到要查找的数据就要向后继续查找因为插入时进行的是线性插入只有为空和删除的位置才进行插入所以有可能想要的数据会出现在删除状态的后面。
注意如果是二次探测就进行二次查找
哈希表的删除 // 伪删除法bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s DELETE;--_n;return true;}else{return false;}}
将要删除的数据状态进行标记就行了如果标记为空就会影响查找函数的进行就可能会出现查找错误的情况。
完整代码及其测试代码
#includevectortemplateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}//cout key : hash endl;return hash;}
};namespace open_address
{enum Status{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;Status _s; //状态};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子0.7就扩容if (_n*10 / _tables.size() 7){size_t newSize _tables.size() * 2;HashTableK, V, Hash 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;}HashDataK, 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;}// 伪删除法bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s DELETE;--_n;return true;}else{return false;}}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;}private:vectorHashDataK, V _tables;size_t _n 0; // 存储的关键字的个数};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.Find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashDatastring, 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();}
}
