首页 > 代码库 > 查找之---哈希法

查找之---哈希法

           查找方法有很多种,如:顺序查找,折半查找,分块查找,基于数的查找等等,但是这些查找有一个共同的特点,那就是都是通过比较的方式查找a[i]中的那个i,比如顺序查找,是通过顺序比较数组中的每个元素,最终找到i,折半查找只不过是在比较的时候用了一些技巧,使得比较的此数减少了,但是,原理还是比较,基于树的查找其实就是存储方式的不同(链表),其原理也是通过比较的方式找到i。

那有没有一种方法不通过比较,而是,直接根据所给出的关键字而求出相应的存储位置呢? 这就是哈希法所采用的核心原理!

哈希法用到的技术:散列技术

          散列技术是在关键字和其对应的存储位置之间建立一种确定的联系F,F称为哈希函数,采用散列技术将记录存储在一块连续的空间上,就是我们所说的哈希表,就如同我们人一样,我们人是关键字,并且有各种属性(性别,年龄,籍贯等),我们通过某种确定的关系用身份证号和某人联系起来。

哈希法的使用范围:

哈希法适合一个存储位置存储一个关键字的情况,就像一个人就一个独一无二的DNA;

不适合一对多的情况,如,一个班里50个同学,有一半的男生一半的女生,我们一男生或女生作为关键字,对应25种情况,用哈希法是不合适的;

不适合查找范围,如,查找这个班里20--22岁的同学;

不适合查找最大或最小值;

冲突:

冲突就是两个关键字对应同一个散列位置,对于如何处理冲突,放到下面再讲。

哈希函数的构造方法:

1.数字分析法


2.平方取中法

就是给出一个关键字,如,123,我们取123的平方,得到15129,我们可以取512作为散列地址。

3.折叠法


4.除留余数法(常用方法)



5.伪随机数法


        哈希函数构造完成,哈希表自然就可以很快得出,但我们很多时候会发现,哈希表并不是我们期望中的那样(一个值对应一个存储位置),而是有时候多个关键字对应同一个存储位置(见图8-10-6),这就是我们所说的冲突,接下来讲的就是如何解决冲突问题。

1.开放定址法



2.再散列函数法


3.链地址法



4.公共溢出区法




参考资料:《大话数据结构》程杰著。

查找之---哈希法