首页 > 编程语言 >算法与数据结构——哈希算法

算法与数据结构——哈希算法

时间:2024-08-28 17:25:58浏览次数:13  
标签:hash 哈希 int 质数 算法 key 数据结构

哈希算法

前面介绍了哈希表的工作原理和哈希冲突的处理方法。然而无论是开放寻址还是链式地址,它们只能保证可以在发生冲突时正常工作,而无法减少哈希冲突的发生

如果哈希冲突过于频繁,哈希表的性能则会急剧劣化。如下图所示,对于链式哈希表,理想情况下键值对均匀分布在各个桶中,达到最佳查询效率;最差情况所有键值对都存储到同一个桶中,时间复杂度退化至 O(n)

键值对的分布情况由哈希函数决定。在前面的哈希表实现中,哈希函数是直接对键取数组长度的模:

        /*哈希函数*/
	int hashFunc(int key){
		int index = key % capacity;
		return index;
	}

index = hash(key) % capacity
观察以上公式,当哈希表容量capacity固定时,哈希算法hash()决定了输出值,进而决定了键值对在哈希表中的分布情况。

为降低哈希冲突发生的概率,我们应当将注意力集中在哈希算法hash()的设计上 。

哈希算法的目标

为了实现“既快又稳”的哈希表数据结构,哈希算法应该具备以下特点:

  • 确定性: 对于相同的输入,哈希算法应始终产生相同的输出。这样才能确保哈希表时可靠的。
  • 效率高: 计算哈希值的过程应该足够快。计算开销越小,哈希表的实用性越高。
  • 均匀分布: 哈希算法应使得键值对均匀分布在哈希表中。分布越均匀,哈希冲突的概率就越低。

实际上哈希算法除了可以用于实现哈希表,还广泛应用于其他领域中。

  • 密码存储:为了保护用户密码的安全,系统通常不会直接存储用户的明文密码,而是存储密码的哈希值。当用户输入密码时,系统会对输入的密码计算哈希值,然后与存储的哈希值进行比较。如果两者匹配,那么密码就被视为正确。
  • 数据完整性检查:数据发送方可以计算数据的哈希值并将其一同发送;接收方可以重新计算接收到的数据的哈希值,并与接收到的哈希值进行比较。如果两者匹配,那么数据就被视为完整。

对于密码学的相关应用,为了防止从哈希值推导出原始密码登逆向工程,哈希算法需要具备更高等级的安全特性。

  • 单向性:无法通过哈希值反推出关于输入数据的任何信息。
  • 抗碰撞性:应当极难找到两个不同的输入,使得它们的哈希值相同。
  • 雪崩效应:输入的微小变化应当导致输出的显著且不可预测的变化。

注意:“均匀分布”与“抗碰撞性”是两个独立的概念,满足均匀分布不一定满足抗碰撞性。例如,在随机输入key下,哈希函数key % 100可以产生均匀分布的输出,但该哈希算法过于简单,所有后两位相等的key的输出都相同,因此我们可以很容易地从哈希值反推出可用的key,从而破解密码。

哈希算法的设计

哈希算法的设计是需要考虑多项因素的复杂问题。然而对于某些要求不高的场景,我们也能设计一些简单的哈希算法。

  • 加法哈希:对输入的每个字符的ASCII码进行相加,将得到的总和作为哈希值。
  • 乘法哈希:利用乘法的不相关性,每轮乘一个常数,将各字符的ASCII码积累到哈希值中。
  • 异或哈希:将输入的每个元素通过异或操作累积到一个哈希值中。
  • 旋转哈希:将每个字符的ASCII码累积到一个哈希值中,每次累积之前都会对哈希值进行旋转操作。
/*加法哈希*/
int addHash(string key){
	long long hash = 0;
	/*1000000007 是一个质数,使用质数作为模数可以减少哈希冲突的概率*/
	/*避免内存溢出,保证结果在int整数范围内*/
	const int MODULE = 1000000007;
	/*使用unsigned char保证字符转换后都为正数,避免了减法的发生*/
	for (unsigned char ch : key){
		hash = (hash + (int)ch) % MODULE;
	}
	return (int)hash;
}
/*乘法哈希*/
int mulHash(string key){
	long long hash = 0;
	const int MODULE = 1000000007;
	for (unsigned char ch : key){
		hash = (31 * hash + (int)ch) % MODULE;
	}
	return (int)hash;
}
/*异或哈希*/
int xorHash(string key){
	long long hash = 0;
	const int MODULE = 1000000007;
	for (unsigned char ch : key){
		hash ^= (int)ch;
	}
	return (int)hash;
}
/*旋转哈希*/
int rotHash(string key){
	long long hash = 0;
	const int MODULE = 1000000007;
	for (unsigned char ch : key){
		hash = ((hash << 4)^(hash >> 28) ^ (int)ch) % MODULE;
	}
	return (int)hash;
}

观察发现每一种哈希算法的最后一步都是对大质数1000000007取模,以确保哈希值在合适的范围内。

原因:使用大质数作为模数,可以最大化地保证哈希值均匀分布。因为质数不与其他数字存在公约数,可以减少因取模操作而产生的周期性模式,从而避免哈希冲突。
举个例子,假设我们选择合数9作为模数,它可以被3整除,那么所有可以被3整除的key都会被映射到0、3、6这三个哈希值。

如果输入key恰好满足这种等差数列的数据分布,那么哈希值就会出现聚堆,从而加重哈希冲突。现在,假设将module替换为质数13,由于keymodule之间不存在公约数,因此输出的哈希值的均匀性会明显提升。

说明:如果能保证key是随机均匀分布的,那么选择质数或者合数作为模数都是可以的,它们都能输出均匀分布的哈希值。而当key的分布存在某种周期性时,对合数取模更容易出现聚集现象。

总而言之,我们通常选取质数作为模数,并且这个质数最好足够大,以尽可能消除周期模式,提升哈希算法的稳健性。

标签:hash,哈希,int,质数,算法,key,数据结构
From: https://www.cnblogs.com/1873cy/p/18384976

相关文章

  • Python基本数据结构
    本篇是Python系列教程第8篇,更多内容敬请访问我的Python合集Python提供了几种内置的数据结构,这些数据结构可以帮助我们有效地组织和管理数据。下面是一些基本的数据结构及其介绍和示例:1列表(list)列表是一种有序的、可变的数据结构,可以包含任何类型的项。特点:有......
  • 安全算法
    统一认证:SSO参考:https://cloud.tencent.com/developer/article/2353704  单点登录英文全称SingleSignOn,简称SSO。它的定义是:在多个应用系统中,用户只需要登录一次,即可访问所有相互信任的应用系统。SSO服务用于解决同一公司不同业务应用之间的身份认证问题,只需要登录一次,......
  • 代码随想录算法day1-数组1
    题目1704.二分查找题目描述:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例2:......
  • Redis几种常用数据类型的数据结构
    以下是redis-7版本以下适用stringint编码:当字符串长度小于等于12字节并且字符串可以表示为整数时,Redis会使用int编码。这样可以节省内存,并且在执行一些命令时可以直接进行数值计算。embstr编码:当字符串长度小于等于39字节时,Redis会使用embstr编码。这种编码方式会将......
  • 浮点数算法的内部实现
     科学计算当中会用到不少浮点数的操作,这些浮点数可能是16位,32位,64位,80位甚至是128位。开源项目SoftFloat提供了一个高效的浮点运算实现,可以在没有硬件支持的情况下,高效模拟浮点数的各种操作。 那么,浮点数之间的比较,基本运算这些究竟是怎么实现的呢,可以拿32位浮点数作为例子。......
  • 代码随想录算法训练营第一天 | 数组part01:数组理论基础,704. 二分查找,27. 移除元素 97
    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合数组徐璈注意的是:数组的下标都是从0开始的数组内存空间是的地址是连续的正因为舒适的内存空间是连续的,所以在删除和增添元素的时候,需要移动其他元素的地址。在c++中,vector的底层实现是array,严格来说,vector是容......
  • postman 发送json数据时,数据为随机数(雪花算法生成)
    要在Postman中发送由雪花算法计算出的随机数,您可以通过在预请求脚本中使用JavaScript代码来实现。首先,您需要添加一个script部分模拟雪花算法生成随机数的函数。可以在请求的"Pre-requestScript"选项卡中添加以下代码:functiongenerateRandomNumber(){constepoch=16094......
  • 使用统计方法在AMD GPU上使用JAX Profiler可靠地比较大型生成AI模型中的算法性能
    UsingstatisticalmethodstoreliablycomparealgorithmperformanceinlargegenerativeAImodelswithJAXProfileronAMDGPUs—ROCmBlogs摘要本文提供了一份详细的指南,介绍如何在JAX实现的生成AI模型中测量和比较各种算法的性能。利用JAXProfiler和统计分析......
  • 《机器学习》—— K-means 聚类算法
    文章目录一、什么是K-means聚类算法?二、聚类效果评价方式——轮廓系数三、示例:代码实现四、聚类算法的优缺点一、什么是K-means聚类算法?K-Means是Python中非常流行的一个聚类算法,它属于无监督学习算法的一种。在scikit-learn(一个广泛使用的机器学习库)中,KMeans......
  • 亦菲喊你来学机器学习(14) --贝叶斯算法
    文章目录贝叶斯一、贝叶斯定理二、贝叶斯算法的核心概念三、贝叶斯算法的优点与局限优点:局限:四、构建模型训练模型测试模型总结贝叶斯贝叶斯算法(Bayesianalgorithm)是一种基于贝叶斯定理的机器学习方法,主要用于估计模型参数和进行概率推断。以下是对贝叶斯算法的......