哈希算法介绍

《哈希算法介绍》由会员分享，可在线阅读，更多相关《哈希算法介绍（9页珍藏版）》请在装配图网上搜索。

1、哈希算法简介一哈希算法简介目录1哈希算法概念22哈希函数33冲突的解决方法34哈希算法应用4关键词：算法、哈希、C语言摘要：哈希算法在软件开发和Linux内核中多次被使用，由此可以见哈希算法的实用性和重要性。本 文介绍了哈希算法的原理和应用，并给出了简略的代码实现，以便读者理解。1哈希算法概念哈希（hash散列，音译为哈希）算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二 进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字 母，随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所

2、以数据的哈希值可以检验数据的完整性。哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以 关键字在地址区间中的项作为记录在表中的存储位置，这种表称为哈希表，所得存储位置称为哈希地址。作 为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。查找一般是对项的摸个部分（及数据成员）进行，这部分称为键key）。例如，项可以由字符串作为键, 附带一些数据成员。理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数组。6 |davt 27500 17 mary 2H2OO-通常的习惯是让项从0到TableSize-1之间变化。将每个键映射到

3、0到TableSize-1这个范围中的某个数， 并且将其放到适当的单元中，这个映射就称为散列函数（hash funciton）。如右图，john被散列到3, phil被散列到4, dave被散列到6, mary被散列到7.这是哈希的基本思想。剩下的问题则是要选择一个函数，决 定当两个键散列到同一个值的时候（称为冲突），应该做什么。圈5】-个理想的敬列授2哈希函数通常，键是字符串，一种选择方法是把字符串中字符ASCII码值加起来。unsigned int hash( const char * key, int tableSize)unsigned int hastVal = 0;for( int

4、 i = 0; i namej namej IFNAMSIZ) return dev;return NULL;#define NETDEV_HASHBITS Sstatic struct hlist_head dev_name_headlNETDEV_HASHBITS;static struct hlist_head dev_indeH_headlNETDEV_HASHBITS;static inline struct hlist_head *d6V_Fl出Tie.hSl合h(ucinst char *name) unsigned hash = full-name-hashtname strn

5、len(namej IFNAMSIZ); return &jt/eu_name_hc&d_hash & (1NETDEV_HASHBITS)-1);static inline struct hlist_head * dev_index_hash(int ifindew)returnu_index_head_ifindeh 8； (1NETDEV_HASHBITS)-1);卜严 Compute the hash for a name string. */static inline unsigned intfull_naiTl6_hSlSh(const unsigned char namej un

6、signed int len) _ _ unsigned long hash = init_name_hash();while (len-)hash = partial_name_ha5h(：+：name+J hash);return end_name_hash(ha5h);第4页共7页严 partial hash update function. Assume roughly 4 bits per characterstatic inline unsigned long partial_name_hash(unsigned long c, unsigned long prevhash) return (prevhash + (c 4) * 11;dev_name_head为哈希表，保存了所有项的链表头。1 NETDEV_HASHBITS 为表的大小。full_name_hash为哈希函数，其主要目的是为了分布均匀避免冲突，这样可以提高查找效率。 这个应用比较简单，但是清晰的展现哈希算法的架构，而且容易理解。哈希算法应用很多场景，比如管理组播MAC地址，文件系统，数据库，数据校验等等。有兴趣可以深入研究，可以拓宽编程思路。