文章目录
1.什么是哈希表2.哈希冲突3.哈希表的实现(拉链法)4.哈希表的应用哈希表的应用--集合与字典哈希表的应用--MD5算法(已被破解,不再安全)哈希表的应用--SHA2算法
1.什么是哈希表
哈希表,是一种线性表的存储结构,由一个直接寻址表和一个哈希函数组成. 哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标 基本操作: insert(key,value) get(key) delete(key)
直接寻址表: 当关键字的全域U比较小时,直接寻址是一种简单有效的方法 缺点: 当域U很大时,需要消耗大量内存,很不实际 如果域U很大而实际出现的key很少,则大量空间被浪费
直接寻址表+哈希函数就是哈希表 构建大小为m的寻址表T key为k的元素放到h(k)位置上 h(k)是一个函数,其将域U映射到表T[0,1,…,m-1]
2.哈希冲突
由于哈希表大小有限,因此对于任何哈希函数,都会出现两个不同元素映射到同一个位置上的情况,这种情况叫做哈希冲突 解决方法: 1.开放寻址法(不太好) 如果哈希函数返回的位置上已经有值,则可以向后探查新的位置 线性探查: i + 1, i + 2, … 二次探查: i + 1^2, i - 1^2, i + 2^2, i - 2^2, … 二度哈希: 有n个哈希函数,当使用第1个哈希函数发生冲突时,则尝试使用h2,h3,… 2. 拉链法 哈希表每个位置都放一个链表,当冲突时,冲突的元素被加到该位置链表的最后
常见哈希函数: 除法哈希: h(k) = k % n 乘法哈希: h(k) = floor(m*(Akey%1)) 全域哈希: h(K) = ((akey + b) % p) % m a,b = 1,2,…,p-1
3.哈希表的实现(拉链法)
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: Xiang Hai
# wechat: xiaoyou42952
"""
哈希表的实现(拉链法)
"""
class Linklist:
class Node:
def __init__(self, item=None):
self.item = item
self.next = None
class LinklistIterator:
def __init__(self, node):
self.node = node
def __next__(self):
if self.node:
cur_node = self.node
self.node = cur_node.next
return cur_node.item
else:
raise StopIteration
def __iter__(self):
return self
def __init__(self, iterable=None):
self.head = None
self.tail = None
if iterable:
self.extend(iterable)
def append(self, obj):
s = Linklist.Node(obj)
if not self.head:
self.head = s
self.tail = s
else:
self.tail.next = s
self.tail = s
def extend(self, iterable):
for obj in iterable:
self.append(obj)
def find(self, obj):
for n in self:
if n == obj:
return True
else:
return False
def __iter__(self):
return self.LinklistIterator(self.head)
def __repr__(self):
return "<<"+",".join(map(str,self))+">>"
# lk = Linklist([1,2,3,4,5])
# print(lk)
# 类似于集合的结构
class HashTable:
def __init__(self, size=101):
self.size = size
self.T = [Linklist() for i in range(self.size)]
def h(self, k):
return k % self.size
def insert(self, k):
i = self.h(k)
if self.find(k):
print("Duplicated Insert.")
else:
self.T[i].append(k)
def find(self, k):
i = self.h(k)
return self.T[i].find(k)
ht = HashTable()
ht.insert(0)
ht.insert(1)
ht.insert(3)
ht.insert(102)
ht.insert(508)
print(",".join(map(str, ht.T)))
print(ht.find(3))
4.哈希表的应用
哈希表的应用–集合与字典
字典与集合都是通过哈希表实现 使用哈希表存储字典,通过哈希函数将字典的键映射为下标 如果发生哈希冲突,则通过拉链法或开放寻址法解决
哈希表的应用–MD5算法(已被破解,不再安全)
MD5(Message-Digest Algorithm 5) 曾经是密码学中常用的哈希函数,可以 把任意长度的数据映射为128位的哈希值 1. 同样的消息,其MD5值必定相同 2. 可以快速计算 3. 除非暴力枚举,否则不可能从哈希值反推出消息本身 4. 两条消息之间之间即使只有微小差别,其对应的MD5值也完全不同不相关 5. 不能在有意义的时间内人工构造两个不同的消息,使其具有相同的MD5值 应用: 文件的哈希值 1.验证下载文件的完整性 2.云存储服务商可以用来判断用户要上传的文件是否已经存在,从而实现秒传功能,避免存储过多相同文件副本
哈希表的应用–SHA2算法
SHA-2包含了一系列哈希函数:SHA-224,SHA-256, SHA-384,SHA-512,其对应的哈希值长度分别为224,256,384,512 SHA-2具有和MD5类似的性质 SHA-2的应用: 比特币: 在比特币系统中,所有参与者需要共同解决如下问题: 对于一个给定的字符串U,给定的目标哈希值H,需要计算出一个字符串V, 使得U+V的哈希值与H的差小于一个给定值D.此时,只能通过暴力枚举V来 进行猜测. 首先计算出结果的人可能获得一定奖金.而某人首先计算成功的概率与其拥有 的计算量成正比,所以其获得的奖金的期望值与其拥有的计算量成正比
精彩内容
发表评论