【C++】多态：实现一个可以自定义哈希函数的哈希表类

2024-06-06 18:48
文章标签 c++ 实现 函数 自定义 哈希 多态 表类

本文主要是介绍【C++】多态：实现一个可以自定义哈希函数的哈希表类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

请实现一个可以自定义哈希函数的哈希表类

哈希函数

哈希函数包括：函数、函数对象、Lambda表达式

分析

一片内存空间存储数据，一个可以自行配置的哈希方法，冲突处理方法。

根据题意哈希函数的类型，所以要传入一个可调用对象来配置哈希函数，可以存储可调用类型的是 function。

基础版本

#include <iostream>
#include <vector>
using namespace std;class Node { //拉链法的节点
public :Node() = default;Node(string, Node *);string data();Node *next();void insert(Node *);void erase_next();
private :string __data;Node *__next;
};class HashTable {
public ://function可以存储函数对象typedef function<int(string)> HASH_FUNC_T;HashTable(HASH_FUNC_T hash_func, int);bool insert(string);bool erase(string);bool find(string);private :int size;HASH_FUNC_T hash_func;vector<Node> data;
};Node::Node(string data, Node *next = nullptr) : __data(data), __next(next) {}
string Node::data() { return this->__data; }
Node *Node::next() { return this->__next; }
void Node::insert(Node *p) {p->__next = this->__next;this->__next = p;
}void Node::erase_next() {if (this->__next == nullptr) return ;Node *q = this->__next;this->__next = this->__next->__next;delete q;return ;
}HashTable::HashTable(HASH_FUNC_T hash_func, int size = 10000) : size(size), data(size), hash_func(hash_func) {}
bool HashTable::insert(string s) {if (find(s)) return false;int h = hash_func(s) % size;//传入的字符串插入到哈希表相应的位置//data[h]为虚拟头节点data[h].insert(new Node(s));return true;
}bool HashTable::erase(string s) {int h = hash_func(s) % size;for (Node *p = &data[h]; p->next(); p = p->next()) {if (p->next()->data() != s) continue;p->erase_next();return true;}return false;
}bool HashTable::find(string s) {int h = hash_func(s) % size;for (Node *p = data[h].next(); p; p = p->next()) {if (p->data() == s) return true;}return false;
}int BKDRHash(string s) {int seed = 31;int h = 0;for (int i = 0; s[i]; i++) {h = h * seed + s[i];}//将负的哈希值变成正的哈希值return h & 0x7fffffff;
}class APHash_class {
public ://重载()使其成为函数对象int operator()(string s) {int h = 0;for (int i = 0; s[i]; i++) {if (i % 2) {h = (h << 3) ^ s[i] ^ (h >> 5);} else {h = ~((h << 7) ^ s[i] ^ (h >> 11));}}return h & 0x7fffffff;}
};int main() {//用函数配置哈希函数HashTable h1(BKDRHash);APHash_class APHash;//用函数对象配置哈希函数HashTable h2(APHash);int op;string s;while (cin >> op >> s) {switch (op) {case 0: {cout << "insert " << s << " to hash table 1 = ";cout << h1.insert(s) << endl;cout << "insert " << s << " to hash table 2 = ";cout << h2.insert(s) << endl;} break; //insertcase 1: {cout << "erase " << s << " from hash table 1 = ";cout << h1.erase(s) << endl;cout << "erase " << s << " from hash table 2 = ";cout << h2.erase(s) << endl;} break; //erasecase 2: {cout << "find " << s << " at hash table 1 = ";cout << h1.find(s) << endl;cout << "find " << s << " at hash table 2 = ";cout << h1.find(s) << endl;} break; //find}}return 0;
}

运行结果：
image-20210312163032148

优化版本一：实现 [] 运算符

当前实现的哈希表表现得像个 unordered_map ，想让它表现得像个数组一样，于是实现 [] 运算符。

#include <iostream>
#include <vector>
using namespace std;class Node { //拉链法的节点
public :Node() = default;Node(string, int, Node *);string key();int value;Node *next();void insert(Node *);void erase_next();
private :string __key;Node *__next;
};class HashTable {
public ://function可以存储函数对象typedef function<int(string)> HASH_FUNC_T;HashTable(HASH_FUNC_T hash_func, int);bool insert(string, int);bool erase(string);bool find(string);int &operator[](string);private :Node *__insert(string, int);Node *__find(string);int size;HASH_FUNC_T hash_func;vector<Node> data;
};Node::Node(string key, int value = 0, Node *next = nullptr) : __key(key), value(value),  __next(next) {}
string Node::key() { return this->__key; }
Node *Node::next() { return this->__next; }
void Node::insert(Node *p) {p->__next = this->__next;this->__next = p;
}void Node::erase_next() {if (this->__next == nullptr) return ;Node *q = this->__next;this->__next = this->__next->__next;delete q;return ;
}HashTable::HashTable(HASH_FUNC_T hash_func, int size = 10000) : size(size), data(size), hash_func(hash_func) {}bool HashTable::insert(string key, int value = 0) {if (find(key)) return false;return __insert(key, value); //返回地址是否为空
}Node *HashTable::__insert(string key, int value = 0) {int h = hash_func(key) % size;//传入的字符串插入到哈希表相应的位置//data[h]为虚拟头节点data[h].insert(new Node(key, value));return data[h].next();
}bool HashTable::erase(string s) {int h = hash_func(s) % size;for (Node *p = &data[h]; p->next(); p = p->next()) {if (p->next()->key() != s) continue;p->erase_next();return true;}return false;
}bool HashTable::find(string s) {return __find(s);
}
Node *HashTable::__find(string key) {int h = hash_func(key) % size;for (Node *p = data[h].next(); p; p = p->next()) {if (p->key() == key) return p;}return nullptr;
}int &HashTable::operator[](string key) {Node *p;if (!(p = __find(key))) return (__insert(key)->value);return p->value;
}int BKDRHash(string s) {int seed = 31;int h = 0;for (int i = 0; s[i]; i++) {h = h * seed + s[i];}//将负的哈希值变成正的哈希值return h & 0x7fffffff;
}class APHash_class {
public ://重载()使其成为函数对象int operator()(string s) {int h = 0;for (int i = 0; s[i]; i++) {if (i % 2) {h = (h << 3) ^ s[i] ^ (h >> 5);} else {h = ~((h << 7) ^ s[i] ^ (h >> 11));}}return h & 0x7fffffff;}
};int main() {//用函数配置哈希函数HashTable h1(BKDRHash);APHash_class APHash;//用函数对象配置哈希函数HashTable h2(APHash);int op;string s;h1["hello"] = 123;h1["world"] = 456;cout << h1["hello"] << " " << h1["world"] << " " << h1["hahaha"] << endl; //输出123 456 0while (cin >> op >> s) {switch (op) {case 0: {cout << "insert " << s << " to hash table 1 = ";cout << h1.insert(s) << endl;cout << "insert " << s << " to hash table 2 = ";cout << h2.insert(s) << endl;} break; //insertcase 1: {cout << "erase " << s << " from hash table 1 = ";cout << h1.erase(s) << endl;cout << "erase " << s << " from hash table 2 = ";cout << h2.erase(s) << endl;} break; //erasecase 2: {cout << "find " << s << " at hash table 1 = ";cout << h1.find(s) << endl;cout << "find " << s << " at hash table 2 = ";cout << h1.find(s) << endl;} break; //find}}return 0;
}

优化版本二：扩容哈希表

  • 新建哈希表
  • 将原哈希表中的数据插入到新建的哈希表中
  • 交换新建的哈希表和原哈希表中的内容
#include <iostream>
#include <vector>
using namespace std;class Node { //拉链法的节点
public :Node() = default;Node(string, int, Node *);string key();int value;Node *next();void insert(Node *);void erase_next();
private :string __key;Node *__next;
};class HashTable {
public ://function可以存储函数对象typedef function<int(string)> HASH_FUNC_T;HashTable(HASH_FUNC_T hash_func, int);bool insert(string, int);bool erase(string);bool find(string);int capacity();int &operator[](string);private :Node *__insert(string, int);Node *__find(string);void __expand();int __size, data_cnt;HASH_FUNC_T hash_func;vector<Node> data;
};Node::Node(string key, int value = 0, Node *next = nullptr) : __key(key), value(value),  __next(next) {}
string Node::key() { return this->__key; }
Node *Node::next() { return this->__next; }
void Node::insert(Node *p) {p->__next = this->__next;this->__next = p;
}void Node::erase_next() {if (this->__next == nullptr) return ;Node *q = this->__next;this->__next = this->__next->__next;delete q;return ;
}HashTable::HashTable(HASH_FUNC_T hash_func, int size = 2) : __size(size), data(__size), hash_func(hash_func), data_cnt(0) {}int HashTable::capacity() {return this->__size;
}bool HashTable::insert(string key, int value = 0) {if (find(key)) return false;return __insert(key, value); //返回地址是否为空
}Node *HashTable::__insert(string key, int value = 0) {if (data_cnt >= __size) __expand();cout << "__insert " << key << " " << value << endl;int h = hash_func(key) % __size;//传入的字符串插入到哈希表相应的位置//data[h]为虚拟头节点data[h].insert(new Node(key, value));data_cnt += 1;//拉链法的每条链上有2个节点return data[h].next();
}void HashTable::__expand() {cout << "Expand hash table" << endl;int new_size = __size * 2;HashTable temp_h(hash_func, new_size);//遍历当前哈希表中的数据依次插入到新的哈希表中for (int i = 0; i < __size; i++) {for (Node *p = data[i].next(); p; p = p->next()) {temp_h[p->key()] = p->value;}}//交换当前哈希表和临时哈希表swap(*this, temp_h);return ;
}bool HashTable::erase(string s) {int h = hash_func(s) % __size;for (Node *p = &data[h]; p->next(); p = p->next()) {if (p->next()->key() != s) continue;p->erase_next();data_cnt -= 1;return true;}return false;
}bool HashTable::find(string s) {return __find(s);
}
Node *HashTable::__find(string key) {int h = hash_func(key) % __size;for (Node *p = data[h].next(); p; p = p->next()) {if (p->key() == key) return p;}return nullptr;
}int &HashTable::operator[](string key) {Node *p;if (!(p = __find(key))) return (__insert(key)->value);return p->value;
}int BKDRHash(string s) {int seed = 31;int h = 0;for (int i = 0; s[i]; i++) {h = h * seed + s[i];}//将负的哈希值变成正的哈希值return h & 0x7fffffff;
}class APHash_class {
public ://重载()使其成为函数对象int operator()(string s) {int h = 0;for (int i = 0; s[i]; i++) {if (i % 2) {h = (h << 3) ^ s[i] ^ (h >> 5);} else {h = ~((h << 7) ^ s[i] ^ (h >> 11));}}return h & 0x7fffffff;}
};int main() {//用函数配置哈希函数HashTable h1(BKDRHash);APHash_class APHash;//用函数对象配置哈希函数HashTable h2(APHash);int op;string s;cout << h1.capacity() << endl;cout << h2.capacity() << endl;h1["hello"] = 123;h1["world"] = 456;h1["maureen"] = 789;cout << h1.capacity() << endl;cout << h1["hello"] << " " << h1["world"] << " " << h1["hahaha"] << endl;while (cin >> op >> s) {switch (op) {case 0: {cout << "insert " << s << " to hash table 1 = ";cout << h1.insert(s) << endl;cout << "insert " << s << " to hash table 2 = ";cout << h2.insert(s) << endl;} break; //insertcase 1: {cout << "erase " << s << " from hash table 1 = ";cout << h1.erase(s) << endl;cout << "erase " << s << " from hash table 2 = ";cout << h2.erase(s) << endl;} break; //erasecase 2: {cout << "find " << s << " at hash table 1 = ";cout << h1.find(s) << endl;cout << "find " << s << " at hash table 2 = ";cout << h1.find(s) << endl;} break; //find}}return 0;
}

运行结果：
image-20210313115200542

这篇关于【C++】多态：实现一个可以自定义哈希函数的哈希表类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1036933。

相关文章

Python使用python-can实现合并BLF文件

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库：CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合
阅读更多...
Python使用OpenCV实现获取视频时长的小工具

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文
阅读更多...
golang版本升级如何实现

golang版本升级如何实现

《golang版本升级如何实现》：本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola
阅读更多...
MySQL 中的 CAST 函数详解及常见用法

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字
阅读更多...
SpringBoot中SM2公钥加密、私钥解密的实现示例详解

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...
MySQL 定时新增分区的实现示例

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后，有时候会需要自动创建分区。比如，一些表数据量非常大，有些数据是热点数据，按照日期分区MululbU
阅读更多...
MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
Python内置函数之classmethod函数使用详解

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》：本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客
阅读更多...
IDEA中新建/切换Git分支的实现步骤

IDEA中新建/切换Git分支的实现步骤

《IDEA中新建/切换Git分支的实现步骤》本文主要介绍了IDEA中新建/切换Git分支的实现步骤,通过菜单创建新分支并选择是否切换,创建后在Git详情或右键Checkout中切换分支,感兴趣的可以了... 前提：项目已被Git托管1、点击上方栏Git->NewBrancjsh...2、输入新的分支的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2