哈希算法介绍

哈希算法简介目录1哈希算法概念22哈希函数33解决冲突34应用的哈希算法4关键词：算法，哈希，C语言摘要：哈希算法在软件开发和Linux内核中已经被多次使用，由此可见哈希算法的实用性和重要性。本文介绍了哈希算法的原理和应用，并给出了一个简单的代码实现，供读者理解。1哈希算法概念哈希算法将任意长度的二进制值映射到固定长度的较小二进制值，这称为哈希值。哈希值是一段数据的独特且极其紧凑的数字表示。如果对一段明文进行哈希处理，即使该段中只有一个字母被更改，后续的哈希算法也会产生不同的值。在计算上不可能找到散列到相同值的两个不同输入，因此数据的散列值可以验证数据的完整性。哈希表根据设定的哈希函数H(key)和冲突处理方法，将一组关键字映射到有限的地址区间，并将地址区间中的关键字项作为表中记录的存储位置。该表称为哈希表，结果存储位置称为哈希地址。哈希表作为一种线性数据结构，与表和队列相比，无疑是一种快速查找。搜索通常在项目的接触部分(和数据成员)进行，这被称为键。例如，一个项目可以用一个字符串作为键，并带有一些数据成员。理想的哈希表数据结构只是一个包含某些项的固定大小的数组。通常的习惯是将项目从0更改为TableSize-1。每个键被映射到0到TableSize-1范围内的某个数字，并放入适当的单位。这种映射称为哈希函数。如图所示，约翰被散列到3，菲尔被散列到4，戴夫被散列到6，玛丽被散列到7。这是哈希的基本思想。剩下的问题是选择一个函数来决定当两个键散列到同一个值时该做什么(称为冲突)。2哈希函数通常，关键字是字符串，一个选项是将字符串中字符的ASCII值相加。无符号整型哈希(常量char *键，整型tableSize)无符号int HasVal=0；对于(int I=0；i strlen(密钥)；(I)哈斯瓦尔=基一世；返回哈希值% tableSize哈希值是通过将表大小的余数作为ASCII码的总和来确定的。这是一个简单的例子，实现起来很简单，并且可以快速计算出答案。但是，如果表很大，函数就不能很好地分配键。由于ASCII字符的最大值为127，如果输入的密钥是长度相对较小的字符串，那么返回的密钥值(哈希值)将集中在哈希表的头部，这将导致分布不均匀。一个好的散列算法在本章中非常复杂，所以这里只是一个介绍。下面的哈希算法应用程序将介绍linux内核如何使用哈希算法来管理网络设备结构。解决冲突当使用散列算法时，除了散列函数之外，还应该注意冲突的处理(当两个键散列到相同的值时)。常用的处理方法包括分离链接法、线性检测和平方检测。由于线性检测和平方检测涉及一些数学问题，本文介绍了分离连接法。拆分链接方法也相对简单，所有散列到相同值的元素都保存在一个链表中。如上图所示，所有哈希表项都对应于一个链表，因此只需要将冲突项放入链表中。当搜索时，首先找到链表，然后比较链表上项目的关键字以获得所需的项目。这种方法相对容易实现，但会增加搜索时间。最初，只需要计算哈希值，现在添加了链表项的比较函数。4哈希算法应用让我们来看看linux内核中的网络设备，如何通过设备名获得相应设备的网络设备结构。在这个过程中，使用了哈希算法，并使用了单独的链接方法来解决冲突。哈希算法可以提高查询速度。如果使用链表，查询需要一个接一个地比较，这是低效的。Dev_name_head是一个哈希表，保存所有项目的列表头。1 NETDEV_HASHBITS是表的大小。全名哈希是一个哈希函数。其主要目的是均匀分布和避免冲突，从而提高搜索效率。这个应用程序相对简单，但它清楚地显示了哈