1 哈希表
哈希表一个通过哈希函数来计算数据存 储位置的数据结构,通常支持如下操作:
插入( 键,值) : 插入键值对( 键,值)
Get( key) : 如果存在键为键的键值对则返回其值,否则返回空值
删除( 键) : 删除键为键的键值对哈希表( Hash Table,又称为散列表) ,是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h( k) 将元素关键字k作为自变量,返回元素的存储下标。解决哈希冲突使用:拉链法
拉链法: 哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后。
class LinkList : """单链表实现""" class Node : def __init__ ( self, item= None ) : """初始化链表节点:param item: 节点存储的数据,默认为None""" self. item = item self. next = None 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 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 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 return False def delete ( self, obj) : """从链表中删除指定的元素:param obj: 要删除的元素:return: 如果成功删除,返回True;否则返回False""" current = self. head previous = None while 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. next return False def __iter__ ( self) : """返回链表的迭代器对象:return: 链表的迭代器对象""" return self. LinkListIterator( self. head) def __repr__ ( self) : """返回链表的字符串表示形式:return: 链表的字符串表示形式,格式为"<<" + 元素 + ">>"""" return "<<" + "," . join( map ( str , self) ) + ">>"
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 ) )
print ( lk. find( 4 ) )
lk. delete( 2 )
print ( lk. find( 2 ) )
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. 云存储服务商可以利用它来判断用户要上传的文件 是否已经存在于服务么器上,从而实现秒传的功能,同时避免存储过多相同的文件副本。