|
仅作笔记使用，准备秋招中，时间不多，来不及解释啦！！！
散列表（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;
}
return;
}
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;
//}
溜了溜了~~~
|