渭南专业做网站,深圳建网建网站,互联网公司净利排名,遵义制作公司网站的公司这篇博客要说的是哈希算法#xff0c;哈希又称为散列#xff0c;它是将存储的值和存储的位置建立起关联关系的一种算法#xff0c;或者说是一种将任意长度的数据映射为固定长度的输出的算法。 什么意思呢#xff1f;我们来看一个例子#xff1a;比如说我们要存储1#xf… 这篇博客要说的是哈希算法哈希又称为散列它是将存储的值和存储的位置建立起关联关系的一种算法或者说是一种将任意长度的数据映射为固定长度的输出的算法。 什么意思呢我们来看一个例子比如说我们要存储123456这几个数据我们可以开6个空间大小的数组用于存储正好下标位置跟数据值之间是有一定的关系的很容易存储。 但是假如是下面6个数据呢123100010011002难道我们还要开1000个空间不成当然不可以这太浪费了于是就开始想办法让它们都对于总个数6取余不就得到范围比较小的值了吗。它们取余后分别得到123450我们让这几个数据当作它们各自的位置这样每一个数据都和一个位置相互对应了这就是一种解决问题的方法。 上面两个例子已经很形象的说明了什么是哈希并且第一个例子就是我们的直接定址法第二个例子就是除留余数法。 但是我们的除留余数法还是有问题的有没有可能两个数取余后得到的数相同肯定是有可能的这种情况就叫哈希冲突。我们可以知道哈希冲突越多那么效率就越低。所以我们一般当负载因子或者叫载荷因子就是实际存的数据个数除以表的大小大于某个数就要扩容增大表的大小。这样就可以一定程度的保证效率。那么接下来我们就要解决哈希冲突有两种方法一种叫闭散列开放定址法一种叫开散列拉链法也叫哈希桶 它们分别是什么意思呢下面我们分别来说闭散列开放定址法就是在这个固定长度的数组中如果一个值要放的位置已经有其他的值了那么就从这个位置向后边找直到找到空的位置放入如果找到结尾那么再返回头去找。这个向后边找可以一个一个找就叫线性探测也可以14916.....这样二次方数这样找就叫做二次探测。 下面一个是哈希桶也叫开散列拉链法就是我们在哈希表中存某个数据所在节点的指针如果下个数据仍然在这个位置那么就挂在上个数据的下边就可以了挂上数据之后就像一个桶或者像拉链于是名字由此得名 那么接下来我们就分别用这两种解决哈希冲突的方法来实现一下哈希表这里我们的哈希表中的值先按整形看等后边我们再慢慢加上模板等一系列东西,先看第一种方法 enum state {EMPTY,EXIST,DELETE
};
struct HashNode {int val0;state stateEMPTY;
};
class HashTable {
public:HashTable(size_t n 10) {_hashvec.resize(n);}HashNode* find(size_t key) {int hashi key % _hashvec.size();while (_hashvec[hashi].state ! EMPTY _hashvec[hashi].val ! key) {hashi;hashi % _hashvec.size();}if (_hashvec[hashi].state EMPTY)return nullptr;return _hashvec[hashi];}bool insert(size_t data) {if (find(data))return false;if (_n * 10 / _hashvec.size() 7) {//扩容HashTable newtable;newtable._hashvec.resize(_hashvec.size()*2);for (size_t i 0; i _hashvec.size(); i) {if(_hashvec[i].stateEXIST)newtable.insert(_hashvec[i].val);}_hashvec.swap(newtable._hashvec);}size_t hashi data % _hashvec.size();while (_hashvec[hashi].state EXIST) {hashi;hashi % _hashvec.size();}_hashvec[hashi].val data;_hashvec[hashi].state EXIST;_n;return true;}bool erase(size_t data) {HashNode* tmp find(data);if (tmp nullptr)return false;tmp-state DELETE;--_n;return true;}
private:size_t _n0;vectorHashNode _hashvec;
}; 再看第二种方法 struct HashNode {HashNode(size_t n0):val(n),_next(nullptr){}size_t val 0;HashNode* _next nullptr;};class HashTable {public:HashTable(size_t n10) {_hashvec.resize(n, nullptr);}HashNode* find(size_t key) {size_t hashi key % _hashvec.size();HashNode* cur _hashvec[hashi];while (cur) {if (cur-val key)return cur;cur cur-_next;}return nullptr;}bool insert(size_t key) {if (find(key))return false;if (_n _hashvec.size()) {//扩容HashTable newtable(_hashvec.size() * 2);for (size_t i 0; i _hashvec.size(); i) {HashNode* cur _hashvec[i];HashNode* next nullptr;while (cur) {next cur-_next;size_t hashi cur-val % newtable._hashvec.size();cur-_next newtable._hashvec[hashi];newtable._hashvec[hashi] cur;/*if (newtable._hashvec[hashi] nullptr) {newtable._hashvec[hashi] cur;}else {HashNode* tmp newtable._hashvec[hashi];while (tmp-_next) {tmp tmp-_next;}tmp-_next cur;}cur-_next nullptr;*/cur next;}_hashvec[i] nullptr;}_hashvec.swap(newtable._hashvec);}size_t hashi key % _hashvec.size();HashNode* newnode new HashNode(key);newnode-_next _hashvec[hashi];_hashvec[hashi] newnode;_n;return true;}bool erase(size_t key) {size_t hashi key % _hashvec.size();HashNode* prev nullptr;HashNode* cur _hashvec[hashi];while (curcur-val ! key) {prev cur;cur cur-_next;}if (cur nullptr)return false;if (prev nullptr) {_hashvec[hashi] cur-_next;}else {prev-_next cur-_next;}delete cur;return true;}private:size_t _n 0;vectorHashNode* _hashvec;};
}
