初级数据结构——哈希表

ops/2024/12/27 4:05:57/

目录

  • 前言
  • 一、哈希表的基本概念
  • 二、哈希表的构成
  • 三、哈希表的工作原理
  • 四、哈希表的冲突解决
  • 五、哈希表的优缺点
  • 六、哈希表的应用场景
  • 七、代码模版
  • 八、总结
  • 九、结语

前言

这一期我们一起学习初级数据结构最后一篇内容,初级数据结构——哈希表。数据结构中的哈希表(Hash Table,也叫散列表)是一种高效的数据结构,它提供了快速的插入、删除和查找操作。以下是对哈希表的详细分析:

在这里插入图片描述

一、哈希表的基本概念

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

二、哈希表的构成

哈希表数组:一个固定大小的数组,用于存储数据。数组的大小通常为质数,以减少潜在的哈希冲突。

哈希函数:一个将关键字映射到哈希表数组中某个位置的函数。哈希函数的选择对哈希表的性能至关重要。常见的哈希函数实现方式包括除法散列法、平方散列法和斐波那契散列法等。

存储槽:哈希表数组中的每个元素称为存储槽,用于存储键值对。

三、哈希表的工作原理

插入操作:计算关键字的哈希值,根据哈希值找到对应的存储槽。如果该槽为空,则直接将关键字和值插入到该槽中。如果该槽已被占用,则根据冲突解决策略处理(如使用链表法或开放寻址法)。

查找操作:计算关键字的哈希值,根据哈希值找到对应的存储槽。如果该槽为空,则表示关键字不存在。如果该槽已被占用,则根据冲突解决策略查找并返回对应的关键字和值。

删除操作:计算关键字的哈希值,找到对应的存储槽,并删除该槽中的键值对。但需要注意的是,在删除时可能需要处理冲突,以确保哈希表的正确性。

四、哈希表的冲突解决

哈希冲突(Hash Collision)是指不同的关键字通过同一个哈希函数可能得到同一哈希地址,即key1 ≠ key2,而Hash(key1) = Hash(key2)。为了处理哈希冲突,通常有两种方法:

链表法:在每个存储槽中维护一个链表,所有映射到该槽的关键字都存储在链表中。当发生冲突时,将新的关键字插入到对应槽的链表中。

开放寻址法:寻找空闲位置来存储冲突的元素。开放寻址法包括线性探测、二次探测、双散列和再哈希法等方法。

五、哈希表的优缺点

优点:
哈希表能够快速地处理大量的数据,提供快速的插入、删除和查找操作。
哈希表的实现相对简单,代码易于理解和维护。

缺点:
哈希表是基于数组的,数组创建后扩容成本比较高,因此当哈希表被填满时,性能会严重下降。
哈希表中的数据都是没有顺序的,因此不支持顺序遍历。
哈希函数的选择对哈希表的性能至关重要,但设计一个高效的哈希函数并不容易。

六、哈希表的应用场景

哈希表在许多场景中都有广泛应用,以下是一些常见的应用场景:

数据库索引:哈希表可以用于加速数据库查询操作,提高查询性能。

缓存系统:哈希表可以用于实现缓存系统,如Redis等,提高数据访问速度。

编译器:哈希表可以用于实现编译器的符号表,加速变量查找和替换操作。

字典和集合:哈希表可以用于实现字典和集合数据结构,提高查找、插入和删除操作的性能。

七、代码模版

#include<iostream>
using namespace std;template<typename KeyType,typename ValueType>
class HashNode {
public:KeyType key;ValueType value;HashNode* next;HashNode(const KeyType& key, const ValueType& value) {//有参构造函数this->key = key;this->value = value;this->next = NULL;}};template<typename KeyType, typename ValueType>
class HashTable {int size;HashNode<KeyType, ValueType>** table;//相当于一个二维数组int hash(const KeyType& key) const {//哈希表的索引位置,默认size参数为256int hashkey = key % size;//取余求索引if (hashkey < 0) {hashkey += size;}return hashkey;}
public:HashTable(int size = 256);//代表哈希表的长度为256~HashTable();void insert(const KeyType& key, const ValueType& value);//插入元素void remove(const KeyType& key);//删除元素bool find(const KeyType& key, ValueType& value) const;//查找元素};template<typename KeyType, typename ValueType>
HashTable<KeyType,ValueType>::HashTable(int size) {this->size = size;this->table = new HashNode<KeyType, ValueType>* [size];for (int i = 0; i < size; i++) {this->table[i] = NULL;//哈希表里面的元素要致空}
}template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {for (int i = 0; i < size; i++) {if (table[i]) {HashNode<KeyType, ValueType>* curr = table[i];while (curr) {HashNode<KeyType, ValueType>* t = curr->next;delete curr;curr = t;}table[i] = NULL;}}
}template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {int idx = hash(key);//先计算键的索引HashNode<KeyType, ValueType>* now = new HashNode<KeyType, ValueType>(key, value);if (!table[idx]) {//该索引对应的链表没有节点就把该节点变成头结点table[idx] = now;}else {now->next = table[idx];//头插法table[idx] = now;}
}template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {int idx = hash(key);if (table[idx]) {//如果该索引的链表不为空if (table[idx]->key == key) {HashNode<KeyType, ValueType>* t = table[idx]->next;delete table[idx];table[idx] = t;}else {HashNode<KeyType, ValueType>* curr = table[idx];while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) {HashNode<KeyType, ValueType>* t = curr->next->next;delete curr->next;curr->next = t;}}}
}template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value) const {int idx = hash(key);if (table[idx]) {if (table[idx]->key == key) {value = table[idx]->value;return true;}else {HashNode<KeyType, ValueType>* curr = table[idx];while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) {value = curr->next->value;return true;}}}return false;
}template<typename KeyType>
class hashCounter {//哈希表计数器,记录一个键有多少个元素多少个元素int* counter;int counterIndex;int counterSize;HashTable<KeyType, int>* hash;public:hashCounter(int size = 256);~hashCounter();void reset();int add(const KeyType& key);int sub(const KeyType& key);int get(const KeyType& key);
};template<typename KeyType>
hashCounter<KeyType>::hashCounter(int size) {counterSize = size;counterIndex = 0;counter = new int[counterSize];hash = NULL;reset();//重新申请内存空间
}template<typename KeyType>
hashCounter<KeyType>::~hashCounter() {delete[]counter;if (hash) {delete hash;hash = NULL;}
}template<typename KeyType>
void hashCounter<KeyType>::reset() {if (hash) {delete hash;hash = NULL;}hash = new HashTable<KeyType, int>(counterSize);counterIndex = 0;for (int i = 0; i < counterSize; i++) {counter[i] = 0;}
}template<typename KeyType>
int hashCounter<KeyType>::add(const KeyType& key) {int idx;if (!hash->find(key, idx)) {//如果在哈希表里找不到这个键说明键的个数加一idx = counterIndex++;hash->insert(key, idx);//这里要好好理解,用来标记key所以的value的值}return ++counter[idx];//记录每一个key链表有多少个元素,加元素就加一
}template<typename KeyType>
int hashCounter<KeyType>::sub(const KeyType& key) {int idx;if (hash->find(key, idx)) {return --counter[idx];//减元素就减一}return 0;
}template<typename KeyType>
int hashCounter<KeyType>::get(const KeyType& key) {int idx;if (hash->find(key, idx)) {return counter[idx];}return 0;
}int main() {hashCounter<long long>h(1000);for (int i = 0; i < 5; i++) {h.add(1);}h.add(2);h.add(2);h.sub(1);cout << h.get(1) << endl;return 0;
}

八、总结

综上所述,哈希表是一种高效的数据结构,具有快速的插入、删除和查找操作。但需要注意的是,哈希表也有其缺点和局限性,因此在实际应用中需要根据具体场景和需求进行选择和优化。

九、结语

下期我们一起来做有关哈希表的经典例题,一共二十多道,巩固一下知识点,加强我们对哈希表的应用能力,更完下期初级数据结构也算是完结了,我们下期不见不散。

在这里插入图片描述

关注我让我们一起学习编程,希望大家能点赞关注支持一下,让我有持续更新的动力,谢谢大家
在这里插入图片描述


http://www.ppmy.cn/ops/139611.html

相关文章

Scratch游戏推荐 | 磁铁与磁场原理模型——探索科学的奥秘!

今天为大家推荐一款既有趣又富有教育意义的Scratch互动作品——《磁铁与磁场原理模型》&#xff01;由ps49student503-25制作&#xff0c;这款作品通过直观的方式展示了磁铁和磁场的相互作用&#xff0c;帮助玩家深入了解磁场的方向与强度。快来拖动磁铁&#xff0c;观察磁场如…

weblogic开启https

JSK证书生成 生成密钥库和证书 使用Java的keytool命令来生成一个Java密钥库&#xff08;Keystore&#xff09;和证书。keytool是Java开发工具包&#xff08;JDK&#xff09;中用于管理密钥库和证书的命令行工具。 #创建证书存放目录 [weblogicosb1 jksHL]$ mkdir -p /home/w…

JAVA面试基础(总结了很多)

最近帮整理了一份JAVA的面试基础&#xff0c;不过很基础后面还回继续更新。 java的专业技能 2.1 java的基础部分 2.1.1 简单讲一下java的跨平台原理 由于各操作系统&#xff08;windows,liunx等&#xff09;支持的指令集&#xff0c;不是完全一致的。就会让我们的程序在不同的操…

HiveSQL 中判断字段是否包含某个值的多种方法详解

目录 一、数据准备 二、判断字段是否包含某值的方法 like 方法 locate 函数方法 instr 函数方法 regexp_extract 函数方法 strpos 方法&#xff08;Hive 不支持&#xff0c;其他技术支持&#xff09; 三、总结 在使用 HiveSQL 进行数据处理与分析时&#xff0c;常常会遇…

用 Python 从零开始创建神经网络(十三):训练数据集(Training Dataset)

训练数据集&#xff08;Training Dataset&#xff09; 引言 引言 既然我们在讨论数据集和测试&#xff0c;就值得提到关于训练数据集的一些操作&#xff0c;这些操作称为预处理。然而&#xff0c;重要的是要记住&#xff0c;无论我们对训练数据进行什么预处理&#xff0c;这些…

ubuntu 安装微信,记录

1.下载 Weixin for Linux (Test Version) 2.命令行 duyichengduyicheng-computer:~/Downloads$ sudo dpkg -i WeChatLinux_x86_64.deb 3.等等 4.扫一扫 5.测试一下。 完成。

【Linux】命令行参数环境变量

命令行参数 main 函数⼀共有三个参数&#xff0c;在命令行部分先关注前两个参数&#xff1a; 1、argc‌&#xff1a;表示命令行参数的个数 2、argv&#xff1a;表示命令行参数的清单 根据下⾯的代码观察这两个参数具体的效果&#xff1a; #include <stdio.h>int main…

centos 常见问题处理

免密登录配置 # 在当前机器下 执行命令 生成 私钥和公钥 ~/.ssh 目录下 ssh-keygen -t rsa # 执行如下命令 把公钥 放到 对应机器上的 ~/.ssh/authorized_keys ssh-copy-id 172.17.68.220 # 如此 两台机器两两配置 centos ssh连接慢 vim /etc/ssh/sshd_config # UseD…