哈希表的实现

以下代码已在gitee上开源，仓库地址：https://gitee.com/tgwTTT/c-lreant/tree/master/hash

哈希表是c++学习中重要的一部分，如c++里面的unordered_set/map都是用hash封装的，查找效率较由红黑树封装的map/set更加高效，下面是我将带领大家用开放定址法建立hash表

下面使用线性探测法建立hash表的过程

首先什么是线性探测法？

将上面的数据映射到M=11的表中，我们首先需要将数据取模

然后依次填入表中，但是数据有相同的，这就意味着发生了线性冲突，需要使用线性探测法，向后加，指导找到空位

变成了这个样子，当插入30遇到已经被19占了的情况，向后移动。但是值得我们注意的是 当负载因子（元素个数/元素空间）>0.7,我们必须对容量进行扩容。下面是实现过程

#pragma once
#include
#include
#include 
using namespace std;
enum State {
	EXIST,
	EMPTY,
	DELETE
};

template
struct HashData {
	pair_kv;
	State _state = EMPTY;
};

template
class HashTable {
private:
	vector> _tables;
	size_t _n;//数据个数
public:
	HashTable()
		:_tables(11)
		,_n(0){ }
	bool Insert(const pair& kv) {
		if (Find(kv.first)) {
			return false;
		}
			//扩容，保证负载因子在0.7左右
		if (_n / _tables.size() >= 0.7) {
			//vector> newtables(_tables.size()*2);
			//for (auto& data : _tables) {
			//	i = 1;
			//	//旧表数据映射到新表
			//	while (data._state == EXIST) {
			//		size_t hash0 = data.first % newtables.size();
			//		++i;
			//	}
			//}
			//_tables.swap(newtables);
			HashTablenewht;
			newht._tables.resize(_tables.size() * 2);
			for (auto data : _tables) {
				if(data._state==EXIST)
				newht.Insert(data._kv);
			}
			_tables.swap(newht._tables);
		}
		size_t hash0 = kv.first % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state ==EXIST) {
			//线性探测
			hashi = (hashi + i)% _tables.size();
			++i;
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		++_n;
		return true;
	}
	HashData* Find(const K& key) {
		size_t hash0 = key % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state != EMPTY ) {
			//线性探测
			if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST) {
				return &_tables[hashi];
			}
			hashi = (hashi + i) % _tables.size();
			++i;
		}
		return nullptr;
	}
	bool Erase(const K& key) {
		HashData* ret = Find(key);
		if (ret == nullptr) {
			cout << "删除失败" << endl;
			return false;
		}
		else {
			ret->_state = DELETE;
			return true;
		}
	}
};

下面是测试代码：

test.cpp

#include
#include"hashT.h"
using namespace std;
void test_hash_1() {
    int a[] = { 19,30,52,63,11,22 };
    HashTableht;
    for (auto e : a) {
        ht.Insert({ e,e });
    }
    ht.Erase(30);
    if (ht.Find(30)) {
        cout << "找到了" << endl;
    }
    else {
        cout << "没找到" << endl;
    }
}
void main() {
    test_hash_1();
}

测试结果：

今天的更新就到这了，如有错误，请评论区留言