哈希表查找详解

哈希表查找

• 定义
• 基本概念

1、定义

哈希表查找又称散列表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记录的存储位置和它的关键字之间建立的一个确定的关系f，使得每个关键字key对应一个存储位置f（key）。即：
–存储位置=f（关键字），其中f为哈希函数。

1. 哈希表最适合的求解问题是查找与给定值相等的记录。
2. 哈希查找不适合同样的关键字对应多条记录的情况，如使用关键字"男"去找找某个同学。
3. 不适合范围查找，比如查找班级18~22岁的同学。

2、基本概念

• 1、哈希函数的构造方法

怎么样的才算是好的哈希函数？
1、计算简单。哈希函数的计算时间（指的是产生地址的时间），不应该超过其他查找技术与关键字比较的时间。
2、地址分布均匀。尽量让哈希地址均匀分布在存储空间中，这样可以使空间有效的利用。

（1）直接定址法
我们可以去关键字的某个线性函数的值作为哈希地址，如下图所示

这种哈希函数优点是比较简单、匀称，也不会产生冲突，但是需要实现知道关键字的分布情况，适合查找表比较小且连续的情况。在实际中不常用。

（2）数字分析法


通常适用于处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布均匀，就可以考虑用这种方法。

（3）除留余数法
这是最为常用的构造哈希函数的方法，对于哈希表长度为m的哈希表函数为：

mod是取模（求余数）的意思。事实上，如果p选得不好，就很多容易出现同义冲突的情况：

如上图所示，选择p = 11，就会出现key = 12、144的冲突。

根据经验，若哈希表表长为m，
通常p为小于或者等于表长的最小质数或不包含小于20质因子的合数。
(质数又称素数。是一个大于1的自然数，并且因数只有1和它自身，
不能整除其他自然数。合数则因数除了1和本身还有其他因数的数。)

• 2、哈希函数的构造方法

从刚才的除留余数法可以看出，设计再好的哈希函数也不可能完全避免冲突（key1！=key2，但是f（key1 = f（key2））），下面介绍几种常用的避免冲突方法。

（1）开放定址法
该方法是一旦发生冲突，就去寻找下一个空的哈希表地址，只要哈希表足够大，空的哈希地址总能找到，并将其记录存入。

二次探测法：

增加平方项，主要是为了不让关键字都集中在某一块区域，避免不同的关键字争夺一个地址的情况。

随机探测法：

di使用随机函数计算而来，是前面方法的改进。

（2）链地址法


如上图所示，取12位除数，进行除留余数法，无论存在多少冲突，都只是在当前位置给单链表增加节点而已。

如上图所示，取12为除数，进行除留余数法，无论存在多少冲突，都只是在当前位置给单链表增加节点而已。