哈希表（散列表）

• 哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
  • insert(key, value): 插入键值对(key,value)
  • get(key): 如果存在键为key的键值对则返回其value，否则返回空值
  • delete(key) : 删除键为key的键值对

直接寻址表

• 当关键字的全域U比较小时，直接寻址是一种简单而有效的方法
  按照域内可能的值来开辟一个U大小的列表T。把key当作地址，若查找key为5的value，直接寻址T[5]所保存的值就可以
  
  直接寻址技术的缺点：
• 当域U很大时，需要消耗大量内存
• 如果域U很大而实际出现的key很少，则大量空间被浪费
• 无法处理关键字不是数字(需要key为数字来表示其地址)的情况

哈希

直接寻址表：key为k的元素放到k位置上
改进直接寻址表：哈希(Hashing)

• 构建大小为m的寻址表T
• key为k的元素放到h(k)位置上
• h(k)是一个函数，其将域U映射到表T[0,1,…,m-1]

h(k)就是哈希函数
哈希表(Hash Table， 又称为散列表),是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
假设有一个长度为7的哈希表，哈希函数h(k) = k%7. 元素集合{14,22,3,5}的存储方式如下图。

哈希冲突
由于哈希表的大小是有限的，而要存储的值总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况较哈希冲突
比如h(k) = k%7, h(0)=h(7)=h(14)=…

解决哈希冲突–开放寻址法

开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。

• 线性探查：如果位置i被占用，则探查i+1,i+2,…
• 二次探查：如果位置i被占用，则探查$i+1^2,i-1^2,i+2^2,i-2^2,...$
• 二度哈希：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则阐释使用h2,h3,…

解决哈希冲突–拉链法

拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

常见的哈希函数

• 除法哈希法：h(k) = k % m
• 乘法哈希法：floor(m*(A*key%1))
• 全域哈希法：$h_{a,b}(k)$ = ((a*key +b) mod p) mod m a,b=1,2,…,p-1

哈希表的实现

拉链法

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):
	# iterable 为列表，可以传进列表进来
		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))+">>"

# 类似于集合的结构，不可重复
class HashTable:
	def __init__(self, size=101):
		self.size = size
		self.T = [LinkList() for _ in range(self.size)]	# 开辟出储存空间T，并且每个单元是空链表
	
	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 T[i].find(k)

哈希表的应用–集合与字典

字典与集合都是通过哈希表来实现的

• a = {‘name’: ‘Alex’, ‘age’:18,‘gender’:‘Man’}
• 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4,则哈希表储存结构为[None, 18, None, ‘Alex’, ‘Man’]
• 如果发生哈希冲突，则通过拉链法或开发寻址法解决

哈希表的应用–MD5算法

MD5(Message-Digest Algorithm 5)曾经是密码学中常用的哈希函数，可以把任意长度的数据映射为128位的哈希值，其曾经包含如下特征：

1. 同样的消息，其MD5值必定相同
2. 可以快速计算出人意给定消息的MD5值
3. 除非暴力枚举所有可能的消息，否则不可能从哈希值反推出消息本身
4. 两条消息之间即使只有微笑的差别，其对应的MD5值应该是完全不同，完全不相关的
5. 不能再有意义的时间内人工的构造两个不同的消息使其具有相同的MD5值

应用举例：文件的哈希值
算出文件的哈希值，若两个文件 的哈希值相同，则可以认为两个文件是相同的。因此：

• 用户可以利用它来验证下载的文件是否完整。
• 与存储服务商可以利用它来判断用户要上传的文件是否已经存在于服务器上，从而实现秒传的功能，同时避免存储过多相同的文件副本。

哈希表的应用–SHA2算法

相较与md5更加安全的算法，使用SHA-2等新的更安全的哈希函数。

最后

以上就是超帅盼望为你收集整理的数据结构和算法笔记--11哈希表哈希表（散列表）的全部内容，希望文章能够帮你解决数据结构和算法笔记--11哈希表哈希表（散列表）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。