什么是哈希函数？哈希表（hashtable）的原理——【python 数据结构】
⽬录
⼀，什么是哈希函数？
⼆，哈希表（hash table）原理
三，为什么不是所有的 hash 函数都可以被⽤来加密？
四，哈希碰撞（hash collision）的解决⽅式
五，什么是好的哈希函数？
六，哈希函数的构造⽅法
七，为什么不能对可变的对象进⾏ hash 处理？
⼋，⼤型⽹站如何利⽤ hash 函数保护⽤户密码？
九，Python3.x 增加的随机性
⼗，其他 hash 算法
背景
哈希（hash）算法，原先是⼀种被⽤在资料编码中的技术，可以被⽤来加密要隐藏的资料，还可以被⽤来，⽐较不同⽂本的相似度。哈希算法属于信息摘要（Message Digest）算法。
区块链技术背后的底层原理之⼀，即为哈希算法。理解了哈希函数，⾃然就会理解区块链的挖矿模式。
⼀，什么是哈希函数？
哈希函数（hash function）: 也称为「散列函数」或「杂凑函数」。
h = H(M)
哈希函数将任意长度的消息 M，映射成为⼀个长度较短且长度固定的值 H（M）。H(M)即为散列值或哈希值（hash value）。
镍磷合金镀哈希算法是⼀种信息摘要（Message Digest）算法。对象的 hash 值⽐原对象拥有更低的内存复杂度。是⼀种压缩映射。
根据哈希函数所建⽴的表为哈希表。
2
鸡解剖图⼆，哈希表（hash table）原理
哈希表（hash table）|散列表，是根据关键码值进⾏访问的数据结构。属于键和值之间的⼀ ⼀对应关系。 通常提供查（search），插⼊（insert），删除（delete）等操作。跟数组⼀样都是⼀种数据结构。与字典类似，通过键值对（key-indexed）来保存数据。
⽬前⼤部分动态语⾔的实现中都使⽤了哈希表。有些语⾳将哈希表乘坐字典，但是哈希表跟字典并不完全相同。哈希表是弱类型的，⽽字典是强类型的。
哈希表查⼀个元素的时间复杂度为0（1），效率极⾼，这也是它的⼀个重要优点。
键（key）：操作数据的标识。
槽（bucket）：⽤于存放数据的单元。
创建⾃⼰的哈希表的⼀种⽅法：
class hashtable(object):
def _int_ (self,length = 4): #在这⾥length = 4，即设置哈希表的初始长度为4
self.array = [none]*length
def hash1(self,key):
length = len(self.array)
return hash(key)%length # key的哈希值除以array列表的长度取余
中国渔业政务网
def is_full(self): # 根据哈希表⾥⾯项⽬的数量来更新长度
items = 0
for item in self.array: #通过self.array将项⽬的数量增加
if items is not None:
items +=1
return items > len(self.array)/2 #判断项⽬个数是否⽐array列表总长度的1/2⼤
def double(self): #定义当容量过⼩时更新列表的⽅法
hashtable2 = hashtable(length = len(self.array)*2) #设置hashble2的长度
for i in range(len(self.array)):
if self.array[i] is None:
contune
for zep in self.array[i]:
hashble2.add(zep[0] , zep[1]) #将原hashtable2中的数据转移到hashtable2中
self.array = hashtable2.array
def add(self,key,value):
index = self.hash1(key) #index设为（key）的hash1值
if self.array[index] is not None: #如果array列表中的该位置已被占领
for zep in self.array[index]:
if zep[0] == key: #如果zep为[key,_]，则设置zep为[key，value]，
zep[1] == value #即更新该位置存储的键对值
break
else:
self.array[index].append([key,value]) #否则，在该位置添加键值对
else:
self.array[index] = []
self.array[index].append([key,value]) #该位置为None，直接添加键值对
if self.is_full():
self.double()
def get(self , key):
index = self.hash(key)
d[index] is None:
raise KeyError() #所要寻的键并不存在
else:
for zep in self.array[index]:
if zep[0] == key:
return zep[1]
raise KeyError() #并不存在
三，⼤型⽹站如何利⽤ hash 函数保护⽤户密码？簧 片
即使⼤型⽹站的数据库被攻破，也不会造成太⼤损失。为什么呢？这涉及到了哈希函数的两个主要特性：不可逆性与抗碰撞性。利⽤哈希函数对⽤户密码进⾏加密：⽤户设置完密码后，会被转换成 hash 值，并保存到数据库中。如下图。
pip3 installsimhash
被保存的只是转换后的哈希值，⽽不是原密码。
由于哈希（hash）函数是不可逆的，只能由输⼊产⽣输出，不能由输出产⽣输⼊。系统服务器⽆法根据每个 hash 值逆过来推算出原密码。因此即使是后台⼯作⼈员，也⽆法得知⽤户的原密码。
⽤户登录的时候，输⼊密码，经过 hash 操作后转换成 hash 值，再与数据库中被保存的 hash 值进⾏对⽐。hash 值完全⼀样，则密码正确。
四，为什么不是所有的 hash 函数都可以被⽤来加密？
不是所有的 hash 函数都可以被⽤来加密，这就涉及到了哈希碰撞（hash collision）。
对于 hash 算法，⼀般情况下，不同的数据会⽣成不同的哈希值。但是如果两个不同的数据，经过 Hash 函数计算后，得到的 Hash 值⼀样，则为哈希碰撞（collision）。
即 f (key1) = f(key2)
哈希碰撞⽆法被完全避免。只能降低其发⽣概率。
碰撞攻击则是到另⼀个跟原密码具有相同 hash 值的字符串。
为了提⾼安全性，只有加密哈希函数（cryptgraphic hash functions）可以被⽤来加密。如 SHA256, SHA512, Ripemd，WHIRLPOOL 等 。这类函数的 hash 破解异常困难，⼏乎不太可能出现 hash 碰撞。
五，哈希碰撞（hash collision）的解决⽅式
⼀，开放寻址法（open addressing)
⼆，拉链法
开放寻址法的总体设计原理为：出现哈希碰撞时，重新检测⼀个空闲位置，并插⼊。
日本空间
但是这样会产⽣⼀个问题，即占⽤其他槽位的空间，以致于后续的插⼊操作更容易出现冲突。因此在利⽤开放寻址法的时候，装载因⼦最好保持在0.5以下。 装载因⼦ =
开放寻址法有：
线性探测器（Linear Probing）
⼆次探测法（Quadratic Probing）
随机探测法
双散列（Double hashing）
再哈希法
建⽴⼀个公共溢出区
线性探测法介绍：
线性探测法为开放寻址法最简单的⼀种实现。
线性探测法⽤来解决哈希碰撞的原理是：当某个被给定键在散列表中的对应单元已被占⽤时（即我们向当前哈希表写⼊数据时发⽣了冲突），会检测散列表中离冲突单元最近的空闲单元。并把该键值对写⼊到下⼀个不为空的位置。
只要哈希表未被填满，总能到⼀个不发⽣冲突的单元。
再哈希法：
再哈希法⽤来解决哈希碰撞的原理是：两个值产⽣冲突时，通过下⾯算式，计算另⼀地址，直到不再冲突。
遇见波莉Hi = R * Hi(key) [i = 1,2,...k]
同样的关键字，同样的哈希函数，⽤不同的处理哈希碰撞的⽅法，得到的哈希函数值也不同。
6
六，什么是好的哈希函数？
哈希表的关键点就在于哈希函数的选择。
若对于关键字集合中的，任意⼀个关键字，经过哈希函数，映像到地址集合中，任何⼀个地址的概率是相等的，则为均匀散列函数（uniform hash function）。也即好的哈希函数。
这种⽅法通过将关键字映射到“均匀分布的随机地址”来减少冲突。
⽬前的哈希算法都能良好的将key进⾏⽐较均匀的分布。
6
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议