【数据结构3】哈希表、哈希表的应用(集合与字典、md5算法和文件的哈希值)

1 哈希表

哈希表一个通过哈希函数来计算数据存 储位置的数据结构,通常支持如下操作:
插入(键,值):插入键值对(键,值)
Get(key):如果存在键为键的键值对则返回其值,否则返回空值
删除():删除键为键的键值对哈希表(Hash Table,又称为散列表),是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。解决哈希冲突使用:拉链法
拉链法:哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后。

在这里插入图片描述

class LinkList:"""单链表实现"""# Node类表示链表中的一个节点class Node:def __init__(self, item=None):"""初始化链表节点:param item: 节点存储的数据,默认为None"""self.item = item  # 存储节点的数据self.next = None  # 指向下一个节点的指针,初始为None# LinkListIterator类用于实现链表的迭代器class LinkListIterator:def __init__(self, node):"""初始化链表迭代器:param node: 链表的起始节点"""self.node = node  # 保存当前节点,用于迭代def __next__(self):"""获取链表中的下一个元素:return: 当前节点的数据:raises StopIteration: 如果没有更多节点,则停止迭代"""if self.node:cur_node = self.node  # 保留当前节点self.node = cur_node.next  # 移动到下一个节点return cur_node.item  # 返回当前节点的数据else:raise StopIteration  # 如果没有更多节点,则停止迭代def __iter__(self):"""返回迭代器对象自身:return: 迭代器对象自身"""return self  # 返回迭代器对象自身,使其可以在for循环中使用def __init__(self, iterable=None):"""初始化链表:param iterable: 可迭代对象,用于初始化链表的元素"""self.head = None  # 链表头节点的引用,初始化为空self.tail = None  # 链表尾节点的引用,初始化为空if iterable:self.extend(iterable)  # 如果传入了可迭代对象,则扩展链表def append(self, obj):"""在链表末尾添加一个新节点:param obj: 要添加的元素"""s = LinkList.Node(obj)  # 创建一个新节点if not self.head:self.head = s  # 如果链表为空,将头节点和尾节点都指向新节点self.tail = selse:self.tail.next = s  # 将当前尾节点的next指针指向新节点self.tail = s  # 更新尾节点为新节点def extend(self, iterable):"""扩展链表,将可迭代对象中的每个元素添加到链表中:param iterable: 可迭代对象"""for obj in iterable:self.append(obj)  # 依次添加可迭代对象中的每个元素def find(self, obj):"""查找链表中是否存在指定的元素:param obj: 要查找的元素:return: 如果找到目标元素,则返回True;否则返回False"""for n in self:if n == obj:return True  # 如果找到了目标元素,返回Truereturn False  # 如果遍历结束也没有找到目标元素,返回Falsedef delete(self, obj):"""从链表中删除指定的元素:param obj: 要删除的元素:return: 如果成功删除,返回True;否则返回False"""current = self.head  # 当前节点,初始化为链表的头节点previous = None  # 前一个节点的引用,初始化为Nonewhile current:if current.item == obj:if previous:previous.next = current.next  # 跳过当前节点else:self.head = current.next  # 如果删除的是头节点,更新头节点if current == self.tail:self.tail = previous  # 如果删除的是尾节点,更新尾节点return True  # 删除成功previous = currentcurrent = current.nextreturn False  # 如果没有找到目标元素,返回Falsedef __iter__(self):"""返回链表的迭代器对象:return: 链表的迭代器对象"""return self.LinkListIterator(self.head)  # 返回一个迭代器对象,从头节点开始迭代def __repr__(self):"""返回链表的字符串表示形式:return: 链表的字符串表示形式,格式为"<<" + 元素 + ">>""""return "<<" + ",".join(map(str, self)) + ">>"  # 返回链表的字符串表示形式,元素之间用逗号分隔,整体用"<<"和">>"包围# lk = LinkList([1, 2, 3, 4, 5])
# print(lk)
# for element in lk:
#     print(element)class HashTable:"""哈希表实现"""def __init__(self, size=101):self.size = size  # 哈希表的大小self.T = [LinkList() for _ in range(self.size)]  # 初始化哈希表数组,每个位置是一个链表def h(self, k):"""哈希函数,将键k映射到表中的索引位置"""return k % self.size  # 计算哈希值def insert(self, k):"""插入一个键到哈希表中"""i = self.h(k)  # 计算键的哈希值,确定插入位置if self.find(k):print('重复插入')  # 如果键已存在,打印提示else:self.T[i].append(k)  # 将键插入到相应位置的链表中print(f'{k}插入成功')  # 插入成功提示def find(self, k):"""查找哈希表中是否存在指定的键"""i = self.h(k)  # 计算键的哈希值,确定查找位置return self.T[i].find(k)  # 在链表中查找键def delete(self, k):"""从哈希表中删除指定的键"""i = self.h(k)  # 计算键的哈希值,确定删除位置if self.T[i].delete(k):print(f'{k}删除成功')  # 删除成功提示else:print(f'{k}未找到')  # 如果键不存在,打印提示# 使用示例
lk = HashTable()
lk.insert(1)
lk.insert(2)
lk.insert(3)
print(lk.find(2))  # 输出: True
print(lk.find(4))  # 输出: False
lk.delete(2)  # 删除键2
print(lk.find(2))  # 输出: False

2 哈希表的应用-集合与字典

字典与集合都是通过哈希表来实现的。
a={'name': 'Alex', 'age':18, 'gender': 'an'}
使用哈希表存储字典,通过哈希函数将字典的键映射为下标。假设h('name')=3,h('age')=1,h('gender')= 4,则哈希表存储为[None, 18,None,'Alex''Man']
如果发生哈希冲突,则通过拉链法或开发寻址法解决

3 哈希表的应用-md5算法和文件的哈希值

MD5(Message-Digest Algorithm 5)曾经是密码学中常用的哈希函数,可以把任意长度的数据映射为128 位的哈希值。
其曾经包含如下特征:
1.同样的消息,其MD5值必定相同;
2.可以快速计算出任意给定消息的MD5值:
3.除非暴力的枚举所有可能的消息,否则不可能从哈 希值反推出消息本身;
4.两条消息之间即使只有微小的差别,其对应的MD5 值也应该是完全不同、完全不相关的;
5.不能在有意义的时间内人工的构造两个不同的消息 使其具有相同的MD5值。应用举例:文件的哈希值
算出文件的哈希值,若两个文件的哈希值相同,则可认为这两个文件是相同的。
因此:
1.用户可以利用它来验证下载的文件是否完整
2.云存储服务商可以利用它来判断用户要上传的文件 是否已经存在于服务么器上,从而实现秒传的功能,同时避免存储过多相同的文件副本。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/409178.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用kafka改造分布式事务

文章目录 1、kafka确保消息不丢失&#xff1f;1.1、生产者端确保消息不丢失1.2、kafka服务端确保消息不丢失1.3、消费者确保正确无误的消费 2、生产者发送消息 KafkaService3、UserInfoServiceImpl -> login()4、service-account - > AccountListener.java 1、kafka确保消…

Renesa Version Board开发RT-Thread 之UART驱动应用

目录 概述 1 硬件介绍 2 软件配置 2.1 RT-Thread Studio配置参数 2.2 FSP配置MCU 3 RT-Thread中UART的接口介绍 3.1 RT-Thread UART简介 3.2 RT-Thread 下的UART接口 4 UART的应用 4.1 应用功能实现 4.2 源代码文件 5 测试 程序下载地址&#xff1a; RenesaVersio…

应用层协议(上)Http(URL、Cookie、Session)内含逻辑图解通俗易懂!

绪论​ “少年没有乌托邦 心向远方自明朗”&#xff0c;本章是应用层常用且重要的协议htttp&#xff0c;没看过应用层建议一定先看那一篇后再看本章才能更好的去从上到下的理解应用层。 话不多说安全带系好&#xff0c;发车啦&#xff08;建议电脑观看&#xff09;。 1.Http协…

Linux rocky 9.2 安装mysql-8.0.39-linux-glibc2.28-x86_64.tar.xz

数据库官方下载&#xff1a;MySQL :: Download MySQL Community Server 本文也绑定该资源包&#xff0c;免费提供下载学习。 1.系统版本 2.新建目录&#xff0c;存放数据库安装包&#xff0c;并且上传 需要用到的工具&#xff1a;yum -y install vim lrzsz tar 上传解压&…

探索Python交互式编程的新境界:Python-prompt-toolkit的魔法

文章目录 探索Python交互式编程的新境界&#xff1a;Python-prompt-toolkit的魔法背景&#xff1a;为何选择Python-prompt-toolkit&#xff1f;Python-prompt-toolkit是什么&#xff1f;如何安装Python-prompt-toolkit&#xff1f;简单使用&#xff1a;Python-prompt-toolkit的…

C++,std::queue 详解

文章目录 1. 概述2. 包含头文件3. 基本操作3.1 构造函数3.2 赋值操作3.3 成员函数 4. 迭代器5. 示例6. 注意事项参考 1. 概述 std::queue 是 C 标准模板库&#xff08;STL&#xff09;中的一个容器适配器&#xff0c;它提供了一种先进先出&#xff08;FIFO&#xff09;的数据结…

【研发日记】嵌入式处理器技能解锁(五)——TI C2000 DSP的中断系统

文章目录 前言 背景介绍 中断框架 外设中断 ePIE模块 CPU中断 中断嵌套 应用实例 总结 参考资料 前言 见《【研发日记】嵌入式处理器技能解锁(一)——多任务异步执行调度的三种方法》 见《【研发日记】嵌入式处理器技能解锁(二)——TI C2000 DSP的SCI(串口)通信》 见…

基于Java的小区物业管理系统APP的设计与实现(论文+源码)_kaic

摘 要 小区物业管理系统是现代社会中非常热门的软件&#xff0c;伴随着社区规模的不断扩大和住户的不断增多&#xff0c;本系统的主要目的是辞别帐本以及传统的单一数据管理系统&#xff0c;快捷的保存用户各种数据信息。本系统针对Java系统展开&#xff0c;使用Java、SpringB…

无人机RTK定位定向技术详解

无人机RTK&#xff08;Real-Time Kinematic&#xff0c;实时动态差分技术&#xff09;定位定向技术&#xff0c;是无人机领域的一项高精度导航与定位技术。它结合了全球导航卫星系统&#xff08;如GPS、GLONASS、Galileo、BDS等&#xff09;与实时差分技术&#xff0c;通过地面…

超越GPT4V,最强多模态MiniCPM-V2.6模型分享

MiniCPM-V2.6是由OpenBMB开发的一款多模态大型语言模型&#xff08;MLLM&#xff09;&#xff0c;专为视觉-语言理解设计。 MiniCPM-V2.6模型能够处理图像、视频和文本输入&#xff0c;并提供高质量的文本输出。 MiniCPM-V 2.6模型在单图像理解方面超越了广泛使用的专有模型&…

机器学习课程学习周报九

机器学习课程学习周报九 文章目录 机器学习课程学习周报九摘要Abstract一、机器学习部分1.1 Word Embedding1.1.1 词嵌入的基本概念1.1.2 word2vec连续词袋模型CBOW1.1.3 word2vec跳字模型Skip-gram 1.2 Transformer代码实践DatasetDataloaderModelLearning rate scheduleModel…

windows javascript 打开、关闭摄像头

1. 效果 打开摄像头 关闭摄像头&#xff08;包括指示灯也关了的&#xff09; 2. 代码 open_close_camera.html // open_close_camera.html <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>use camera</title>…

使用Dotween制作按钮弹性动画效果

效果&#xff1a; 方式&#xff1a; 优点&#xff0c;不需要写任何代码、稳定、可自定义效果

Agent实际落地的应用 未来生活的无形助手

在这个信息爆炸的时代&#xff0c;我们每个人都在追求更高效的生活方式。想象一下&#xff0c;如果有一个无形的助手&#xff0c;能够理解我们的需求&#xff0c;自动处理繁琐的任务&#xff0c;甚至为我们提供个性化的建议&#xff0c;那将是多么美好的体验&#xff01;这正是…

数字模拟IC设计前端、后端、前仿、后仿新版虚拟机

虚拟化平台&#xff1a;VMware Workstation 15 Pro以上版本 操作系统&#xff1a;CentOS Linux release 7.9.2009 (Core) 一、射频模拟IC设计必备软件 Cadence IC06.18.350/IC23.10.080&#xff08;virtuoso&#xff09; Cadence SPECTRE23.10.538-isr10 Cadence ASSURA04.…

Spring Boot OAuth2.0应用

本文展示Spring Boot中&#xff0c;新版本OAuth2.0的简单实现&#xff0c;版本信息&#xff1a; spring-boot 2.7.10 spring-security-oauth2-authorization-server 0.4.0 spring-security-oauth2-client 5.7.7 spring-boot-starter-oauth2-resource-server 2.7.10展示三个服务…

远程供水无障碍,管线车助力全面消防防护_鼎跃安全

夏季是各类自然灾害的高发季节&#xff0c;其中森林火灾尤为频繁。这一时期的气候特征是干旱少雨&#xff0c;伴随着高温和强风&#xff0c;使得森林火灾的发生频率大幅增加。由于夏季空气湿度低&#xff0c;植被含水量减少&#xff0c;一旦出现火源&#xff0c;火势极易蔓延。…

数据结构-链表-第二天

结合leetcode学习c 链表比数组更易增加和删除数据&#xff0c;但访问速度更慢 定义 链表&#xff08;linked list&#xff09;是一种线性数据结构&#xff0c;其中的每个元素都是一个节点对象&#xff0c;各个节点通过“引用”相连接。 引用记录了下一个节点的内存地址&#…

windows本地搭建zookeeper和kafka环境

zookeeper 1.1 下载zookeeper 下载地址 随便进一个站点&#xff0c;默认是新版本&#xff0c;旧版本点击archives进入&#xff0c;选择合适的版本下载&#xff0c;本文使用的是3.7.2 下载时候选择apache-zookeeper-3.7.2-bin.tar.gz 格式的&#xff0c;编译后的&#xff0c;解…

centos 虚拟机器刚刚安装没有ip地址的问题

刚刚安装好的虚拟机器&#xff0c;我们通过 ip addr 查看ip发现是这样的 该虚拟机器没有ip地址&#xff0c;那么怎么办 原来是在/etc/sysconfig/network-scripts/ifcfg-ens33中关于网络的配置有问题 ONBOOTno 表示不开启网卡&#xff0c;我们需要将这个值进行修改为yes 当前…