线性探测-闭散列

爱被打了一巴掌 2022-10-16 06:11 146阅读 0赞

![在这里插入图片描述][20210527140212852.png]

### 线性探测的实现 ###

*  目录:
 *   *  一.线性探测的概念
     *  二.线性探测原理
     *  三.功能性接口
     *   *  1.构造
         *  2.insert
         *  3.Capacity
         *  4.Swap
         *  5.find
         *  6.erase

# 目录: #

## 一.线性探测的概念 ##

>  我们在这里讲到的线性探测是解决哈希冲突中闭散列的一种方式

> **闭散列**：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。  
> ~  
> **线性探测**：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

## 二.线性探测原理 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

>  闭散列解决哈希冲突的方法就是将元素后移,存放到为空的位置去.

## 三.功能性接口 ##

### 1.构造 ###

enum STATE{ 		//创建一个枚举
    
    	EXIST,		//存在状态
    	DELETE,		//假删除状态
    	EMPTY		//空状态
    };
    
    template<class K, class V>
    struct HashNode{ 	//创建哈希结构体保存对应的KV键值对,并且将这个表的初始状态变为空
    
    	pair<K, V> _kv;
    	STATE _state = EMPTY;
    };
    
    //顺序表实现hash
    template<class K, class V>
    class HashTable{ 		//hash创建
    
    public:
    	typedef HashNode<K, V> Node;		//定义别名
    
    	HashTable(size_t n = 10)		//构造函数构造缺省值为10
    		:_hTable(n)
    		, _size(0)		//存在元素改为0
    	{ }

### 2.insert ###

>  步骤:  
> 1.计算插入元素的哈希位置  
> 2.判断对应的位置是否有元素存在  
> 3.有元素则向后遍历找空存放  
> 4.无元素则直接存放

bool insert(const pair<K, V>& kv){ 
    
    		//0.判断容量是否够用
    		checkCapacity();	//调用函数
    		//1.计算哈希位置
    		int idx = kv.first%_hTable.size();
    
    		//2.判断key是否存在
    		while (_hTable[idx]._state != EMPTY){ 
    
    			//如果当前位置数据有效,且key相同
    			if (_hTable[idx]._state == EXIST
    				&&kv.first == _hTable[idx]._kv.first)
    			{ 
    				return false;
    			}
    			//继续搜索
    			++idx;
    			if (idx == _hTable.size())
    				idx = 0;
    		}
    		//插入
    		_hTable[idx]._kv = kv;
    		_hTable[idx]._state = EXIST;
    		++_size;
    
    		return true;
    	}

### 3.Capacity ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

void checkCapacity(){ 
    	
    		//负载因子: < 1
    		//存在的元素/容量 0.7
    		if (_hTable.size() == 0 || _size * 10 / _hTable.size() >= 7){ //当内部的元素存储超过7成的时候就开辟新的表
    
    			//开新表
    			int newC = _hTable.size() == 0 ? 10 : 2 * _hTable.size();	//创建出对应的二倍的空间
    			HashTable<K, V> newHt(newC);
    
    			for (int i = 0; i < _hTable.size(); ++i){ 		//在for循环内部
    
    				//插入状态为exist的数据
    				if (_hTable[i]._state == EXIST)	//将内部存在的元素
    				{ 
    					newHt.insert(_hTable[i]._kv);	//依次在新表里面进行插入
    				}
    			}
    			Swap(newHt);	//交换新表和旧表
    		}
    	}

### 4.Swap ###

void Swap(HashTable<K, V>& Ht){ 	//这里的交换就是让新的表指向对应的位置,容量进行交换
    
    		swap(_hTable, Ht._hTable);
    		swap(_size, Ht._size);
    
    	}

### 5.find ###

>  步骤:  
> 1.按照查找位置计算所在的位置  
> 2.如果对应的kv键值对是完全对应的,则直接输出  
> 3.如果没有找到,则继续向后进行遍历

Node* find(const K& key){ 
    
    		//计算对应的位置
    		int idx = key%_hTable.size();	//先找出所在元素在哈希表中的位置
    		while (_hTable[idx]._state != EMPTY){ 		//判断对应的位置是否有元素的存在
    
    			if (_hTable[idx]._state == EXIST
    				&& key == _hTable[idx]._kv.first)	//如果元素存在且对应的键值相互对应
    			{ 
    				return &_hTable[idx];	//则找到,直接输出
    			}
    			++idx;	//没找到则向后遍历
    			if (idx == _hTable.size())	
    			//如果遍历到最后一个位置没有找到,则变为0从第一个重新开始查找
    			{ 
    				idx = 0;
    			}
    		}
    		return nullptr;	//实在没有找到则直接返回空
    	}

### 6.erase ###

>  步骤:  
> 1.找到对应的元素进行删除  
> 2.注意这里的删除是**假删除**,元素还存在,只不过将其置为DELETE状态  
> 3.这里的假删除是为了在插入的时候可以正常的插入.

bool erase(const K& key){ 
    
    		Node* node = find(key);
    		if (node){ 
    
    			//假删除
    			--_size;
    			node->_state = DELETE;
    			return true;
    		}
    		return false;
    	}
    
    
    private:
    	vector<Node> _hTable;
    	size_t _size;	//有效元素的个数
    };

>  这就是对于线性探测的实现,主要**对于它产生哈希冲突的时候是如何解决的理解**.

[20210527140212852.png]: /images/20221014/20542464c7074798b95cbab2e29d9e61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221014/0c5c6affc93a449095f99d1b5dfc49cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221014/297bc15d5ce64bc2bc81c37a1988a23a.png