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

embedded/2024/9/23 23:31:40/

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.ppmy.cn/embedded/100805.html

相关文章

三维平面电磁铁、交流电磁铁、显微镜磁场北京大学方案

根据用户北京大学需求设计制造方案如下 三维平面电磁铁产品规格 5MPS63-25型三维平面电磁铁&#xff0c;X、Y方向磁场由2对正交的磁极产生&#xff0c;Z轴由一组同轴线圈产生&#xff1b; 每轴对应的两个线圈正接产生均匀磁场&#xff0c;反接产生梯度磁场&#xff1b; …

Linux 离线安装docker和docker-compose

前言 公司有 docker 和 docker-compose 离线包安装部署的需求&#xff0c;本文应运而生撰写时间&#xff1a;2024-06-07&#xff08;初稿&#xff09; 1 应用版本 docker&#xff1a;20.10.7, build f0df350docker-compose&#xff1a;1.25.1 2 物料准备 服务器账号/密码d…

记录一下在IIS上部署服务器上遇到的一系列问题及解决方案

注&#xff1a;遇到问题要先查看日志&#xff0c;配置时遇到的问题在windows窗口搜索 事件查看器 Windows日志下&#xff0c;应用程序里&#xff0c;来源为IIS AspNetCore Module V2为配置服务器&#xff0c;并启动时产生的日志&#xff0c;错误信息会记录在此 如果是通讯时遇…

怎样写好提示词(Prompt) 一

提示工程是一门新兴的学科&#xff0c;专注于以最佳实践构建LLM的最佳输入&#xff0c;从而尽可能以程序化方式生成目标输出。AI工程师必须知道如何与AI进行交互&#xff0c;以获取可用于应用程序的有利结果。此外&#xff0c;AI工程师还必须知道如何正确提问和编写高质量的提示…

数学建模起步感受(赛前15天)

0基础直接上手数模&#xff0c;因为大一&#xff01;年轻就是无所畏惧&#xff01;开个玩笑&#xff0c;因为数模比赛比一年少一年… 抱着不打也是浪费的态度&#xff0c;我开始着手准备 首先python啥也不会&#xff0c;知道有元组这玩意… 仅仅在刷软考题的时候遇到python选择…

AI大模型独角兽 MiniMax 基于 Apache Doris 升级日志系统,PB 数据秒级查询响应

作者&#xff1a;MiniMax 基础架构研发工程师 Koyomi、香克斯、Tinker 导读&#xff1a;早期 MiniMax 基于 Grafana Loki 构建了日志系统&#xff0c;在资源消耗、写入性能及系统稳定性上都面临巨大的挑战。为此 MiniMax 开始寻找全新的日志系统方案&#xff0c;并基于 Apache …

【Docker】Docker学习02 | docker-cli的基本命令

本文首发于 ❄️慕雪的寒舍 简单了解一下docker client的常用命令&#xff0c;更多命令可以查看完整命令列表。不同命令之间的关系&#xff0c;可以查看下图。 如果你看不到图片&#xff0c;不用担心&#xff0c;后面对每个命令进行介绍的时候&#xff0c;会提到它们的作用的。…

[mysql][sql]mysql查询表大小

select table_schema as 数据库, table_name as 表名, table_rows as 记录数, truncate(data_length/1024/1024, 2) as 数据容量(MB), truncate(index_length/1024/1024, 2) as 索引容量(MB) from information_schema.tables where 11 and table_schemadb001 order by table_ro…