《Get清风哈希算法介绍》由会员分享，可在线阅读，更多相关《Get清风哈希算法介绍（6页珍藏版）》请在金锄头文库上搜索。
1、哈希算法介绍1 哈希算法概念 02 哈希函数 1哈希算法简介名目3 冲突的解决方法 24 哈希算法应用 2关键词：算法、哈希、c语言摘 要：哈希算法在软件开发和 Linux 内核中屡次被使用，由此可以见哈希算法的有用性和重要性。本文介 绍了哈希算法的原理和应用，并给出了简单的代码实 现，以便读者理解。1 哈希算法概念哈希(hash 散列，音译为哈希)算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。假设散列一段明文而且哪怕只更改该段落的一个字 母，随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入，
2、在计算上是不行能的，所以数据的哈希值可以检验数据的完整性。哈希函数哈希表是依据设定的H(key)和处理冲突方法将一组关键字映象到一个有限的地址区哈希表间上，并以关键字在地址区间中的项作为记录在表中的存储位置，这种表称为，所得存储位置称为哈希地址。作为线性数据构造与表格和队列等相比，哈希表无疑是查找速度比较快的一种。查找一般是对项的摸个局部及数据成员进展，这局部称为键 key。例如，项可以由字符串作为键，附带一些数据成员。抱负的哈希表数据构造只不过是一个包含一些项的具有固定大小的数组。 通常的习惯是让项从 0 到TableSize-1 之间变化。将每个键映射到 0 到TableSize-1 这个
3、范围中的某个数 ，并且将其放到适当的单元中，这个映射就称为散列函数hash funciton。如右图，john 被散列到 3，phil 被散列到 4，dave 被散列到 6，mary 被散列到 7.这是哈希的根本思想。剩下的问题那么是要选择一个函数，打算当两个键散列到同一个值的时候称为冲突，应当做什么。2 哈希函数通常，键是字符串，一种选择方法是把字符串中 字符 ASCII 码值加起来。unsigned int hash( const char * key, int tableSize)unsigned int hastVal = 0;for( int i = 0; i strlen(key)
4、; i+) hashVal += key i ;return hashVal % tableSize;通过对 ASCII 码总和取 tableSize 的余数，来确定哈希值。这是个简洁的例如，实现起来很简洁而且能够很快地算出答案。不过，假设表很大，那么函数不会很好地安排键。由于 ASCII 字符的值最多为 127，假设输入的 key，都是长度比较小的字符串，那么返回的键值哈希值就会集中在哈希表的头部，这样就会安排不均匀。好的哈希算法这局部会格外简单，这里仅仅做个介绍。在下面的哈希算法应用中会介绍linux 内核如何使用哈希算法治理网络设备构造。3 冲突的解决方法在使用哈希算法时，除了哈希函数之
5、外，还需要 留意的是冲突两个键散列到同一个值的时候的处 理。常用的处理方式有别离链接法、线性探测、平方 探测。由于线性探测和平方探测涉及到一些数学问题，本文就介绍别离链接法。别离链接法也比较简洁，其做法为将散列到同一 个值的全部元素保存到一个链表中。如上图所示，全部哈希表项对应一个链表，这样只要将冲突项放入链表就行，当查找时先找到链表， 然后在比较链表上项的键，得到想要的项，这个方法比较简洁实现，但是会增加查找的耗时，原来只需计算哈希值，现在增加了对链表项的比较功能。4 哈希算法应用下面看看 linux 内核中网络设备，是怎么样通过设备名猎取相应设备的 net_device 构造体。在这个过程中，使用了哈希算法，并且使用了别离链接法解决 冲突的问题。使用哈希算法可以提高查询速度，假设 使用链表，查询时需要逐一比较，效率低下。dev_name_head 为哈希表，保存了全部项的链表头。1 NETDEV_HASHBITS 为表的大小。full_name_hash 为哈希函数，其主要目的是为了分布均匀防止冲突，这样可以提高查找效率。这个应用比较简洁，但是清楚的呈现哈希算法的 架构，而且简洁理解。哈希算法应用很多场景，比方治理组播 MAC 地址，文件系统，数据库，数据校验等等。有爱好可以 深化争辩，可以拓宽编程思路。
