C++ 手写简单哈希散列表_c++手写哈希表

仅作笔记使用，准备秋招中，时间不多，来不及解释啦！！！

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

• 对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突

sample_hashmap.h:

// 创建日期：2022-07-13
// 作者：YZM
// 参考：https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/src/Data_struct_tool/HashTable/sample_HashMap.h
#pragma once
#ifndef SAMPLE_HASHMAP_H
#define SAMPLE_HASHMAP_H
 
#include<iostream>
#include<vector>
using namespace std;
 
template<typename T>
struct Node {
	Node* next;
	T val;
	Node() :next(nullptr), val(0) {};
	Node(T _val) :next(nullptr), val(_val) {};
	Node(T _val, Node* nxt) :next(nxt), val(_val) {};
};
 
template<typename T>
class HashTable {
private:
	const static int init_buckets_size = 49; // 桶的初始数量
	int buckets_size; // 桶的数量
	int keys_count; // key的数量
	vector<Node<T>>buckets; // 不定义成指针类型，免去初始化的步骤
	int hashfun(T val); // 哈希函数
public:
	HashTable();
	~HashTable();
	int& operator[](int index) const; // 重载[]运算符，哈希表暂时用不到
	void insert(T val); // 插入
	void erase(T val); // 删除
	bool find(T val); // 寻找
	void expand(); // 扩容
	void clear(); // 清空并释放资源
	void print(); // 打印检查
};
#endif 
 

sample_hashmap.cpp:

#include "sample_hashmap.h"
using namespace std;
 
template<typename T>
HashTable<T>::HashTable():buckets_size(init_buckets_size), keys_count(0), buckets(vector<Node<T>>(init_buckets_size)){}
 
template<typename T>
HashTable<T>::~HashTable() {
	clear();
}
 
template<typename T>
int HashTable<T>::hashfun(T val) {
	return val % buckets_size; // 取模是最简单的哈希函数，如果对于string等类型，需要模板偏特化来另外实现
}
 
template<typename T>
void HashTable<T>::insert(T val) {
	int key = hashfun(val);
	Node<T>* newNode = new Node<T>(key);
	newNode->next = buckets[key].next;
	buckets[key].next = newNode;
	++keys_count; // 元素数量增加
	expand(); // 考虑是否扩容
}
 
template<typename T>
void HashTable<T>::erase(T val) {
	int key = hashfun(val);
	Node<T>* cur = buckets[key].next; // 数组元素是结构体对象，.next调出结构体成员.
	Node<T>* pre = nullptr;
	while (cur) {
		if (cur->val == val) {
			if (pre == nullptr) { // 刚好在链表头部
				buckets[key].next = cur->next;
				delete cur;
			}
			else { // 不在链表头部
				pre->next = cur->next;
				delete cur;
			}
			break;
		}
		pre = cur;
		cur = cur->next;
	}
	--keys_count; // 元素数量减少
}
 
template<typename T>
bool HashTable<T>::find(T val) { // 计算key，并在对应链表中查找有无该数
	int key = hashfun(val);
	Node<T>* cur = buckets[key].next;
	while (cur) {
		if (cur->val == val) return true;
		cur = cur->next;
	}
	return false;
}
 
template<typename T>
void HashTable<T>::clear() {
	for (int i = 0; i < buckets_size; ++i) { // 遍历数组，每个散链表都用while循环删除申请的节点资源
		Node<T>* cur = buckets[i].next;
		while (cur) {
			Node<T>* pre = cur;
			cur = cur->next;
			delete pre;
		}
		buckets[i].next = nullptr;
	}
}
 
template<typename T>
void HashTable<T>::expand() { // 当key的数量比桶的数量多时扩容到原来的两倍
	if (keys_count > buckets_size) {
		buckets_size <<= 1;
		buckets.resize(buckets_size);
	}
}
 
 
 
template<typename T>
void HashTable<T>::print() {
	for (int i = 0; i < buckets_size; ++i) {
		Node<T>* cur = buckets[i].next;
		while (cur) {
			cout << cur->val << ' ';
			cur = cur->next;
		}
	}
	cout << endl;
}
 
//int main() {
//	HashTable<int>hash;
//	hash.insert(4);
//	hash.print();
//	hash.clear();
//	hash.print();
//	hash.insert(4);
//	hash.print();
//	hash.erase(4);
//	hash.print();
//	return 0;
//}

溜了溜了~~~