[C++] 哈希的模拟实现---闭散列法（中）

定义

• 闭散列法，又称开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。

如何寻找下一个空位置

• 线性探测法：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止；
  缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，导致搜索效率降低；
• 二次探测法：按2次方去找“下一个”空位置。

基于闭散列法实现哈希

1）实现基本框架

hashDate

	//标识当前存储位置的状态情况
	enum Status{
		EMPTY,
		EXITS,
		DELETE
	};

	template <class K, class V>
	struct HashData{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};
1
2
3
4
5
6
7
8
9
10
11
12

hashTable

• 对于自定义类型，其构造、拷贝构造、赋值重载、析构等默认成员函数，编译器会自动生成
• 哈希表里的数据类型为hashData

	template <class K, class V, class HashFunc>
	class HashTable{
	private:
		vector<HashData<K, V>> _table;  //vector中的数据类型为HashData
		size_t _n;  //哈希表中有效数据个数
	};
1
2
3
4
5
6

hashFunc

• hashFunc仿函数：实现key值转化为int型，保证在哈希函数运算时能进行取模运算

	struct intHashFunc{
		int operator()(int i){
			return i;
		}
	};

	struct stringHashFunc{
		int operator()(string s){
			int count = 0;
			for (auto &e : s){
				count += e;
			}
			return count;
		}
	};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2）实现基本操作

insert插入操作

• 判断是否需要插入-----是否需要增容（负载因子>0.5）-----线性探测法找待插入位置-----插入元素

bool insert(const pair<K, V>& kv){
			//考虑是否需要增容的问题
			if (_table.size() == 0){
				_table.resize(8);
			}
			
			HashFunc hf;
			HashData<K, V>* ret = find(kv.first);
			if (ret != nullptr){  //元素已经在哈希表中存在，不需要再次插入
				return true;
			}

			//负载因子大于0.5就增容
			if ((double)_n / (double)_table.size() > 0.5){
				HashTable<K, V, HashFunc> newhash;
				newhash._table.resize(_table.size() * 2);
				for (auto& e : _table){
					if (e._status == EXITS)
						newhash.insert(e._kv);  //把数据插入到新的哈希表中
				}
				_table.swap(newhash._table);  //交换两个哈希表的table
			}

			//插入数据
			size_t start = hf(kv.first) % _table.size();
			size_t index = start;
			size_t i = 1;
			while (_table[index]._status == EXITS){
				index = start + i;  //线性探测法
				index %= _table.size();
				++i;
			}
			_table[index]._kv = kv;
			_table[index]._status = EXITS;
			_n++;
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

find查找操作

HashData<K, V>* find(const K& key){
			HashFunc hf;
			size_t start = hf(key) % _table.size();
			size_t index = start;
			size_t i = 1;
			while (_table[index]._status != EMPTY){  
				if (_table[index]._status == EXITS && _table[index]._kv.first == key){
					return &_table[index];
				}
				 //往后探测下一个位置
				index = start + i;
				index %= _table.size();
				++i;
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

erase删除操作

• 查找待删除元素的位置-----该元素的状态置为DELETE即可

bool erase(const K& key){
			HashData<K, V>* ret = find(key);
			if (ret){
				ret->_status = DELETE;
				return true;
			}
			else
				return false;
		}
1
2
3
4
5
6
7
8
9