哈希表与哈希函数详解

在计算机科学中,哈希表是一种通过哈希函数将键和值映射到数组中的数据结构,它极大地提高了数据的访问速度。哈希函数的效率决定了映射处理的好坏。当有一个包含20000个数字的列表,并且需要从中搜索一个特定的数字时,传统的线性搜索会非常耗时且效率低下。而哈希表通过哈希函数减少了搜索时间,使得查找可以在几秒钟内完成。

哈希的关键术语

映射是将两个不同事物联系在一起的过程,通常以键和值的形式出现。键是一个唯一标识数据(实体)的标识符,而值则是存储的数据实体及其相关信息。哈希工作分为两个步骤:算法接受任何实体(作为键)作为输入,如果该键不是整数,需要提供一种方法从实体中获得整数值。不能直接使用这个整数值作为内存地址来放置这个键值对,但哈希函数可以将这个整数值转换成另一个可以用于存储键值对的整数值。

哈希是什么?

哈希算法旨在解决在数组中高效查找和存储数据的问题。例如,学生是一个实体,每个学生都有名字、地址、电话号码和唯一ID(学号)。可以将学号作为键,其余属性如地址、名字、电话号码等作为值,这样就创建了一个以学号为键、基本信息为值的学生映射。如果想要了解一个学生的信息,只需要知道他/她的学号即可。

要存储的数据是什么?

可以将其视为面向对象编程中的对象,或者是属于特定事物的一组属性。如上所述,学生数据可以包括学号、名字、地址等信息。所有这些细节都可以被视为想要存储的“数据”。学号是键,因为它对每个学生都是唯一的。

数据结构中,键值对是通过哈希存储在哈希表中的。只要有一个唯一的键,就可以使用哈希表来存储数据。哈希函数是一个数学公式,它将为某些大键返回一个较小的整数值(在数组大小范围内)。以下是哈希函数内部工作的三种方法:

在所有方法中,这是最容易理解的。假设数组中只有10个单元格,键是15或大于10。如果没有一种方法将15转换为10,需要一种方法返回一个小于10的索引。这可以通过模运算符轻松实现。

HashFunction = Key % size

如果键除以大小,模运算符将返回余数。例如,如果键是15,可以将其插入到大小为10的数组的第5个索引中。例如,15%10=5,因此如果键是15,将其插入到大小为10的数组的第5个位置。

类似于除法,使用以下函数:

h(k) = floor(n * (kA mod 1))

键k将是0到1之间的常数值,A将是0到1之间的任何常数值。k和A相乘,使用模运算符分离它们的小数部分。然后乘以n以获得哈希值。

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485