《哈希算法介绍.doc》由会员分享，可在线阅读，更多相关《哈希算法介绍.doc（8页珍藏版）》请在三一文库上搜索。
1、哈希算法简介目录1哈希算法概念12哈希函数23冲突的解决方法 24哈希算法应用 3关键词：算法、哈希、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.这是哈希的基本思想。剩下的问题则是要选择一个函数，决 定当两个键散列到同一个值的时候（称为冲突），应该做什么。图5】个理想的腋列蠢第1页共7页2哈希函数通常，键是字符串，一种选择方法是把字符串中字符ASCII码值加起来。un sig ned int hash( const char * key, int tableSize)un sig ned int hastVal = 0;for( int i = 0; i 5t char *nome
4、)struct hlict_node 1 p；h I i s t_f d r_ e a 匚 h(pj dev_name_h ash (name) i struct net_device dev=hlist-entryfp, struct net-devieCj name_hh5t); tf (!strncmp(cleY- namej name, imAMSIZ) return devjreturn NULL；define hlETDEV HASHBITS 8static struct hlist_he3d dev_name_headL-NETDEy_HAHBlTS; static struct
5、 hlist_head dev_indeH_headl _ static inline struct hli5t_head *deV_indeX_hash(int IfindeK：return Sx?ev_tndex_hedifinde (1 ：NETOE7_HASH &ITS)- 1)/* Carripute the hash for string V壮atic inline nsigned intfull_name_hash(con5t nfigri&d chrunsigned intien) unnqned long hah = init_name_hsh()jwhile (len-)h
6、ash = partial_name_hash(1|!name+ + j hash)； return end_name_hjsh(hasih);/中 partial hsh update function, Assume roughly 4 bits per character static iriline un signed I on .3p3rfi3l_naIYl_hQSh(unsigned long c? unsigned long prevhash) .retdPn (pr&vhash + (c J 4)4- (e、亠 4j) * 丄丄；dev_ name_head为哈希表，保存了所有项的链表头。1 NETDEV_HASHBITS 为表的大小。full_ name_hash为哈希函数，其主要目的是为了分布均匀避免冲突，这样可以提高查找效率。这个应用比较简单，但是清晰的展现哈希算法的架构，而且容易理解。哈希算法应用很多场景，比如管理组播MAC地址，文件系统，数据库，数据校验等等。有兴趣可以深入研究，可以拓宽编程思路。