1、哈希表-线性探测法理论

线性探测法的理论我们在上一篇博客已经阐述了。

现在我们来看看线性探测法的增删查的代码思想：

1.1、哈希表的增加元素

注意：

• 往后遍历寻找空闲位置的时候，要注意是环形遍历哦！不然访问数组就越界了。
• 在添加元素，发生位置被占用，即发生哈希冲突后，在向后遍历寻找空闲位置的时候，我们要知道，这个空闲的位置是有两种情况的：
  • 1、这个位置一直是空的，没放过元素。
  • 2、这个位置是空的，以前放过元素，后来被删除了。

1.2、哈希表的查询操作

• 当用哈希函数计算得出的下标值是3，然后去访问数组，查询时，发现该值不等于要查询的元素的值val，说明当时放val的时候发生了哈希冲突，这时候就要向后遍历了；
• 访问4下标的时候发现这个位置是空的（空的有两种情况），如果这个位置一直是空的，则就不用继续向后找了，val不存在！因为是线性探测法，所以当时val如果要放的时候肯定是要放在这里的。
• 但是如果这个位置是空的，但是之前放过元素，后来被删除了，这个位置之前存放了元素，然后val插入的时候，就插到后面的空闲的位置了，所以此时我们还要继续往后遍历寻找val值。

所以我们需要定义一个Bucket节点来表示每一个元素的所有的内容。

//桶的状态
enum State
{
	STATE_UNUSE, //从未使用过的桶
	STATE_USING, //正在使用的桶 放着是一个有效的元素，没有被删过 
	STATE_DEL,  //元素被删除了的桶，认为桶里的元素无效了 
};
//我们删除桶里的元素，并不是真正把值删除掉，而是把桶的状态置为STATE_DEL就认为桶里的元素无效了 
//桶的类型
struct Bucket
{
	Bucket(int key = 0, State state = STATE_UNUSE)
		: key_(key)
		, state_(state)
	{}

	int key_;      //存储的数据
	State state_;  //桶的当前状态
};

1.3、哈希表的删除操作

2、哈希表-线性探测法代码实现

2.1、素数表中的素数

求素数的代码：（用于素数表中的素数取值）

int main()
{
	int data = 3;

	for (int i = data; i < 10000; i++)
	{
		int j = 2;
		for (; j < i; j++)
		{
			if (i % j == 0)
				break;
		}

		if (j == i)
			cout << i << " ";
	}
	cout << endl;

	return 0;
}

代码：

#include <iostream>
using namespace std;

//桶的状态
enum State
{
	STATE_UNUSE, //从未使用过的桶
	STATE_USING, //正在使用的桶 放着是一个有效的元素，没有被删过 
	STATE_DEL,  //元素被删除了的桶，认为桶里的元素无效了 
};
//我们删除桶里的元素，并不是真正把值删除掉，而是把桶的状态置为STATE_DEL就认为桶里的元素无效了
//不用将其置为0或-1...

//桶的类型
struct Bucket
{
	Bucket(int key = 0, State state = STATE_UNUSE)	//刚开始都是STATE_UNUSE，没有使用过的状态
		: key_(key)
		, state_(state)
	{}

	int key_;      //存储的数据
	State state_;  //桶的当前状态
};

//线性探测哈希表类型  
class HashTable
{
public:
	//构造
	HashTable(int size = primes_[0], double loadFactor = 0.75)//构造函数 
		: useBucketNum_(0)
		, loadFactor_(loadFactor)
		, primeIdx_(0)
	{
		//把用户传入的size调整到最近的比较大的素数上
		if (size != primes_[0])
		{
			for (; primeIdx_ < PRIME_SIZE; primeIdx_++)
			{
				if (primes_[primeIdx_] >= size)
					break;
			}
			//用户传入的size值过大，已经超过最后一个素数，调整到最后一个素数
			if (primeIdx_ == PRIME_SIZE)
			{
				primeIdx_--;
			}
		}

		tableSize_ = primes_[primeIdx_];
		table_ = new Bucket[tableSize_];//开辟构造，调用Bucket的默认构造函数初始化 
	}
	
	//析构
	~HashTable()//析构函数 
	{
		delete[]table_;
		table_ = nullptr;
	}

public:
	//插入元素，这里不去重，k值可以重复插入
	bool insert(int key)
	{
		//考虑扩容
		double factor = useBucketNum_ * 1.0 / tableSize_;
		cout << "factor:" << factor << endl;
		if (factor > loadFactor_)
		{
			//哈希表开始扩容
			expand();
		}

		int idx = key % tableSize_;//计算下标 

		int i = idx;
		do
		{
			if (table_[i].state_ != STATE_USING)
			{
				table_[i].state_ = STATE_USING;
				table_[i].key_ = key;
				useBucketNum_++;
				return true;//O(1)
			}
			i = (i + 1) % tableSize_;//环形路径 
		} while (i != idx);//O(n) 
		//最多跑一圈，而且不可能跑一圈，因为哈希表是不可能放满的，超过加载因子就扩容 
		//do while 是先执行一次，再判断循环 
		return false;
	}

	//删除元素，只是把当前状态修改一下而已 
	bool erase(int key)
	{
		int idx = key % tableSize_;//计算出哈希值 

		int i = idx;
		do
		{
			if (table_[i].state_ == STATE_USING && table_[i].key_ == key)
			{
				table_[i].state_ = STATE_DEL;
				useBucketNum_--;
			}
			i = (i + 1) % tableSize_;
		} while (table_[i].state_ != STATE_UNUSE && i != idx);	//table_[i].state_ != STATE_UNUSE表示后面确实没有这个元素

		return true;
	}

	//查询  count(key)
	bool find(int key)
	{
		int idx = key % tableSize_;

		int i = idx;
		do
		{
			if (table_[i].state_ == STATE_USING && table_[i].key_ == key)
			{
				return true;
			}
			i = (i + 1) % tableSize_;
		} while (table_[i].state_ != STATE_UNUSE && i != idx);

		return false;
	}

private:
	//扩容操作
	void expand()
	{
		++primeIdx_;	//取素数表后一个元素值
		if (primeIdx_ == PRIME_SIZE)//越界了 
		{
			throw "HashTable is too large, can not expand anymore!";
		}

		Bucket* newTable = new Bucket[primes_[primeIdx_]];
		for (int i = 0; i < tableSize_; i++)
		{
			if (table_[i].state_ == STATE_USING)//旧表有效的数据，重新哈希放到扩容后的新表
			{
				int idx = table_[i].key_ % primes_[primeIdx_];

				int k = idx;
				do
				{
					if (newTable[k].state_ != STATE_USING)//空闲的 
					{
						newTable[k].state_ = STATE_USING;
						newTable[k].key_ = table_[i].key_;
						break;
					}
					k = (k + 1) % primes_[primeIdx_];
				} while (k != idx);
			}
		}

		delete[]table_;
		table_ = newTable;
		tableSize_ = primes_[primeIdx_];
	}

private:
	Bucket* table_;//指向动态开辟的哈希表，不要使用vector，因为它是二倍自动扩容，自增长
	//要用vector也可以，因为哈希表有装载因子，达到0.75，哈希表进行扩容 
	int tableSize_;//哈希表当前的长度
	int useBucketNum_;//已经使用的桶的个数
	double loadFactor_;//哈希表的装载因子

	static const int PRIME_SIZE = 10;//素数表的大小
	static int primes_[PRIME_SIZE];//素数表
	int primeIdx_;//当前使用的素数在素数表中的下标值 
};

int HashTable::primes_[PRIME_SIZE] = { 3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773 };//素数表的定义 
//素数表的最后几个元素代表开辟哈希表数组堆空间的最大的一些内存大小，再大的话堆内存就开辟失败了 
//所有哈希表的素数表都是一样的，可以定义成静态的

int main()
{
	HashTable htable;
	htable.insert(21);
	htable.insert(32);
	htable.insert(14);
	htable.insert(15);

	htable.insert(22);

	cout << htable.find(14) << endl;
	htable.erase(14);
	cout << htable.find(14) << endl;

	return 0;
}

目录:

一.线性探测的概念

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

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

二.线性探测原理

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

三.功能性接口

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

	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;	//有效元素的个数
};

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