【C++】学习笔记——哈希_2

🕗 发布于 2024-07-24 23:56 c++ 学习笔记

文章目录

十八、哈希
- 3. 实现哈希表
未完待续

十八、哈希

3. 实现哈希表

哈希表的实现方法有蛮多种，这里我们选一个比较经典的开散列法来实现哈希表。由于STL库里的哈希表都是将负载因子（插入的数据/哈希表的容量）设置为1，所以我们这里也将负载因子设置为1。

哈希表的存储节点

开散列法实现的哈希表，是通过数组来当哈希表，但是数组中存储的都是指针，像一个链表一样，将同索引的数据在这个指针下串联起来。

// 哈希表数据节点类型
template<class K, class V>
struct HashNode
{
    // 指向同一个桶的下一个节点
HashNode<K, V>* _next;
    // 当前数据
std::pair<K, V> _kv;

HashNode(const std::pair<K, V>& kv)
:_next(nullptr)
,_kv(kv)
{}
};

哈希函数

哈希表是通过哈希函数来确定存储的位置的，但是对于不同的类型，我们无法统一看待。

// 哈希函数
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

// 哈希函数模板特化
template<>
struct HashFunc<std::string>
{
size_t operator()(const std::string& s)
{
// 哈希值
size_t hash = 0;
for (auto e : s)
{
hash += e;
hash *= 131;
}

return hash;
}
};

哈希表的定义

// 哈希表， Hash是仿函数（哈希函数）
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
// 构造函数
HashTable()
{
_tables.resize(10, nullptr);
_n = 0;
}

// 析构函数
~HashTable()
{
// 遍历每个桶
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 遍历每个桶的每个数据节点
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
private:
    // 哈希表每个位置都是一个链表（桶）
std::vector<Node*> _tables;
    // 数据个数
size_t _n;
};

哈希表的插入

// 插入数据
bool Insert(const std::pair<K, V>& kv)
{
    // 该数据存在就不插入
if (Find(kv.first))
return false;

    // 创建哈希函数对象
    Hash hs;

// 负载因子到1就扩容（满了才扩容）
if (_n == _tables.size())
{
        // 创建临时哈希表对象
std::vector<Node*> newTables(_tables.size() * 2, nullptr);
        // 遍历每个桶
for (size_t i = 0; i < _tables.size(); ++i)
{
// 遍历桶中的每个数据节点
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;

// 通过哈希函数计算索引，将旧节点头插到新表
size_t hashi = hs(cur->_kv.first) % newTables.size();
                // 新节点指向原本的首元节点
cur->_next = newTables[hashi];
                // 头指针指向新节点
newTables[hashi] = cur;

cur = next;
}

_tables[i] = nullptr;
}

        // 交换表
_tables.swap(newTables);
}

    // 通过哈希函数计算索引
size_t hashi = hs(kv.first) % _tables.size();
Node* newnode = new Node(kv);

// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;

    // 数据个数+1
++_n;
return true;
}

哈希表的查找

由于哈希表是通过哈希函数来确定存储位置的，所以我们也可以通过哈希函数来找到数据。

// 查找数据
Node* Find(const K& key)
{
    // 哈希函数对象
Hash hs;
    // 通过哈希函数查找所在的桶
size_t hashi = hs(key) % _tables.size();
    // 遍历
Node* cur = _tables[hashi];
while (cur)
{
        // 找到了
if (cur->_kv.first == key)
{
return cur;
}

cur = cur->_next;
}

    // 没找到
return nullptr;
}

哈希表的删除

// 删除数据
bool Erase(const K& key)
{
    // 哈希函数对象
Hash hs;
    // 通过哈希函数查找所在的桶
size_t hashi = hs(key) % _tables.size();
    // 遍历
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
// 删除
if (prev)
{
prev->_next = cur->_next;
}
else
{
_tables[hashi] = cur->_next;
}

delete cur;

--_n;
return true;
}

prev = cur;
cur = cur->_next;
}

return false;
}

测试函数

void TestHT1()
{
HashTable<int, int> ht;
int a[] = { 1,4,24,34,7,44,17,37 };
for (auto e : a)
{
ht.Insert(std::make_pair(e, e));
}

ht.Insert(std::make_pair(5, 5));
ht.Insert(std::make_pair(15, 15));
ht.Insert(std::make_pair(25, 25));

ht.Erase(5);
ht.Erase(15);
ht.Erase(25);
ht.Erase(35);

HashTable<std::string, std::string> dict;
dict.Insert(std::make_pair("sort", "排序"));
dict.Insert(std::make_pair("string", "字符串"));
}

完整代码+结果

HashTable.h：

#pragma once

#include <iostream>
#include <vector>
#include <string>

// 哈希函数
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

// 哈希函数模板特化
template<>
struct HashFunc<std::string>
{
size_t operator()(const std::string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash += e;
hash *= 131;
}

return hash;
}
};

namespace hash_bucket
{
    // 哈希表数据节点类型
template<class K, class V>
struct HashNode
{
        // 指向同一个桶的下一个节点
HashNode<K, V>* _next;
        // 当前数据
std::pair<K, V> _kv;

HashNode(const std::pair<K, V>& kv)
:_next(nullptr)
,_kv(kv)
{}
};

    // 哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
        // 构造函数
HashTable()
{
_tables.resize(10, nullptr);
_n = 0;
}

        // 插入数据
bool Insert(const std::pair<K, V>& kv)
{
            // 该数据存在就不插入
if (Find(kv.first))
return false;

            // 创建哈希函数对象
            Hash hs;

// 负载因子到1就扩容(满了才扩容)
if (_n == _tables.size())
{
                // 创建临时哈希表对象
std::vector<Node*> newTables(_tables.size() * 2, nullptr);
                // 遍历每个桶
for (size_t i = 0; i < _tables.size(); ++i)
{
// 遍历桶中的每个数据节点
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;

// 通过哈希函数计算索引，将旧节点头插到新表
size_t hashi = hs(cur->_kv.first) % newTables.size();
                        // 新节点指向原本的首元节点
cur->_next = newTables[hashi];
                        // 头指针指向新节点
newTables[hashi] = cur;

cur = next;
}

_tables[i] = nullptr;
}

                // 交换表
_tables.swap(newTables);
}

            // 通过哈希函数计算索引
size_t hashi = hs(kv.first) % _tables.size();
Node* newnode = new Node(kv);

// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;

            // 数据个数+1
++_n;
return true;
}

        // 查找数据
Node* Find(const K& key)
{
            // 哈希函数对象
Hash hs;
            // 通过哈希函数查找所在的桶
size_t hashi = hs(key) % _tables.size();
            // 遍历
Node* cur = _tables[hashi];
while (cur)
{
                // 找到了
if (cur->_kv.first == key)
{
return cur;
}

cur = cur->_next;
}

            // 没找到
return nullptr;
}

        // 删除数据
bool Erase(const K& key)
{
            // 哈希函数对象
Hash hs;
            // 通过哈希函数查找所在的桶
size_t hashi = hs(key) % _tables.size();
            // 遍历
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
// 删除
if (prev)
{
prev->_next = cur->_next;
}
else
{
_tables[hashi] = cur->_next;
}

delete cur;

--_n;
return true;
}

prev = cur;
cur = cur->_next;
}

return false;
}

// 析构函数
~HashTable()
{
// 遍历每个桶
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 遍历每个桶的每个数据节点
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
private:
        // 哈希表每个位置都是一个链表（桶）
std::vector<Node*> _tables;
        // 数据个数
size_t _n;
};

void TestHT1()
{
HashTable<int, int> ht;
int a[] = { 1,4,24,34,7,44,17,37 };
for (auto e : a)
{
ht.Insert(std::make_pair(e, e));
}

ht.Insert(std::make_pair(5, 5));
ht.Insert(std::make_pair(15, 15));
ht.Insert(std::make_pair(25, 25));

ht.Erase(5);
ht.Erase(15);
ht.Erase(25);
ht.Erase(35);

HashTable<std::string, std::string> dict;
dict.Insert(std::make_pair("sort", "排序"));
dict.Insert(std::make_pair("string", "字符串"));
}
}

test.cpp：

#include <iostream>
#include "HashTable.h"
using namespace std;

int main()
{
    hash_bucket::TestHT1();
    return 0;
}

结果：
在这里插入图片描述

未完待续

原文地址：https://blog.csdn.net/m0_69828905/article/details/140638435

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：SSRF：服务端请求伪造
下一篇：MyBatis相关问题汇总

配置cobbler服务提供centos7安装源
由RedHat公司基于python语言开发，作用：快速批量部署Linux系统。
阅读更多2024-09-17
【MySQL学习】基础指令全解：构建你的数据库技能
本文详细介绍了SQL操作指令的各种基础和高级操作，帮助读者掌握SQL数据库技巧。
阅读更多2024-09-17
OpenGL笔记二十一之几何类设计
— 2024-09-16 下午。
阅读更多2024-09-17
UiBot教程：实现复杂流程图的高效方法
我们需要在两个流程块之间传递“字符串格式的系统时间”，所以最简单的方法就是在流程图中定义一个变量。举个例子，我们可以创建一个名为x的流程图变量，这样在流程图所包含的所有流程块中都可以直接使用这个变量。
阅读更多2024-09-17
12 数组——27. 移除元素 ★
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
阅读更多2024-09-17
工资重回“3000块”时代
3000元是一个心理价位，但实际上对于许多家庭来说，可能在县城生活，除了基本的生活开销，很难剩下更多的钱。也就是说，如果你的工作收入在这个“五千块定律”所设定的范围内，并且在三年内没有超过平均水平的涨
阅读更多2024-09-17
谷歌向安卓用户推出Gemini Live聊天机器人
即使你的手机处于锁定状态，屏幕处于关闭状态，你也可以开始与助手交谈，而且还可以通过谷歌(Google)的新款Pixel Buds Pro 2无线耳机进行访问，这样你就可以在手机放在包里的时候免提通话。
阅读更多2024-09-17
Linux进阶命令-sed&split
sed（Stream Editor）是一个流编辑器，用于在文本流中进行文本替换和转换操作。它通常用于命令行环境下，可以接受标准输入（stdin）、文件内容或管道输入，并对文本进行修改或处理。
阅读更多2024-09-17
RTMP直播播放器的几种选择
在选择RTMP直播播放器时，需要根据具体的应用场景、平台兼容性、功能需求以及用户体验等因素进行综合考虑。同时，也可以参考其他用户的评价和专业评测来选择最适合的播放器。
阅读更多2024-09-17
Linux套接字
套接字是实现网络通信的核心组件，它提供了灵活且强大的接口，使得开发者能够轻松地在网络环境中构建复杂的应用程序。无论是TCP还是UDP协议，都可以通过适当的套接字类型来满足不同的通信需求.
阅读更多2024-09-17