【数据结构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.云存储服务商可以利用它来判断用户要上传的文件 是否已经存在于服务么器上，从而实现秒传的功能，同时避免存储过多相同的文件副本。