哈希算法简介目录1哈希算法概念 12哈希函数 33冲突的解决方法 34哈希算法应用 4算法、哈希、C语言摘 要：哈希算法在软件开发和 Linux 内核中多次被使用，由此可以见哈希算 法的实用性和重要性本文介绍了哈希算法的原理和应用，并给出了简略 的代码实现，以便读者理解1哈希算法概念哈希(hash散列，音译为哈希)算法将任意长度的二进制值映射为固定 长度的较小二进制值，这个小的二进制值称为哈希值哈希值是一段数据唯一且极其紧凑的数值表示形式如果散列一段明 文而且哪怕只更改该段落的一个字母，随后的哈希算法都将产生不同的值 要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数 据的哈希值可以检验数据的完整性哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字 映象到一个有限的地址区间上，并以关键字在地址区间中的项作为记录在 表中的存储位置，这种表称为哈希表，所得存储位置称为哈希地址作为 线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种查找一般是对项的摸个部分(与数据成员)进行，这部分称为键(key) 例如，项可以由字符串作为键，附带一些数据成员。
理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数-个理想的敬列麦如右图，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); i++)hashVal += key[ i ];return hashVal % tableSize;}通过对ASCII码总和取tableSize的余数，来确定哈希值这是个简单的示例，实现起来很简单而且能够很快地算出答案不过， 如果表很大，则函数不会很好地分配键由于ASCII字符的值最多为127, 如果输入的key，都是长度比较小的字符串，那么返回的键值(哈希值)就 会集中在哈希表的头部，这样就会分配不均匀好的哈希算法这部分会非 常复杂，这里仅仅做个介绍。
在下面的哈希算法应用中会介绍linux内核 如何使用哈希算法管理网络设备结构3冲突的解决方法在使用哈希算法时，除了哈希函数之外，还需要注意的是冲突(两个 键散列到同一个值的时候)的处理常用的处理方式有分离链接法、线性探测、平方探测由于线性探测 和平方探测涉与到一些数学问题，本文就介绍分离链接法如上图所示，所有哈希表项对应一个链表，这样只要将冲突项放入链 表就行，当查找时先找到链表，然后在比较链表上项的键，得到想要的项, 这个方法比较容易实现，但是会增加查找的耗时，原来只需计算哈希值， 现在增加了对链表项的比较功能到一个链表中4哈希算法应用下面看看linux内核中网络设备，是怎么样通过设备名获取相应设备 的net_device结构体在这个过程中，使用了哈希算法，并且使用了分离 链接法解决冲突的问题使用哈希算法可以提高查询速度，如果使用链表, 查询时需要逐一比较，效率低下dev_name_head为哈希表，保存了所有项的链表头1 << NETDEV_HASHBITS 为表的大小full_name_hash为哈希函数，其主要目的是为了分布均匀避免冲突，这样可以提高查找效率这个应用比较简单，但是清晰的展现哈希算法的架构，而且容易理解。
哈希算法应用很多场景，比如管理组播MAC地址，文件系统，数据库, 数据校验等等有兴趣可以深入研究，可以拓宽编程思路。