前言
数据结构中的计算式查找法，特别是哈希法（又称散列法、杂凑法、关键字地址计算法），是一种高效的查找技术。
一、哈希法的基本概念
哈希法是通过一个哈希函数将关键字映射到哈希表中的某个位置，从而实现快速查找的技术。哈希表是一种基于数组的数据结构，其中每个元素都与一个唯一的键值相关联。哈希函数根据关键字计算出在数组中的位置，这个位置称为哈希地址。
二、哈希函数的构造原则与方法
构造原则：
- 函数本身便于计算。
- 计算出来的地址分布均匀，以减少冲突。
构造方法：
- 数字分析法：从关键字中选出分布均匀的若干位构成哈希地址。适用于关键字位数比哈希表地址位数多的情况。
- 平方取中法：先求出关键字的平方值，然后取平方值中间的几位作为哈希地址。适用于无法确定关键字中哪几位分布较均匀的情况。
- 分段叠加法：将关键字分成位数相等的几部分，然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
- 除留余数法：假设哈希表的长度为m，p为小于等于m的最大素数，则哈希函数为H(key) = key mod p。其中，mod表示取余运算。这是最简单且常用的哈希函数构造方法。
- 伪随机数法：采用一个随机函数作为哈希函数，即H(key) = random(key)。这种方法适用于需要较高随机性的场景。
三、哈希表的查找过程
- 计算哈希地址：根据哈希函数和关键字计算出哈希地址。
- 访问哈希表：直接访问哈希表中对应哈希地址的元素。
- 处理冲突：如果哈希地址上已有元素（即发生冲突），则采用适当的冲突解决方法进行处理。
四、冲突解决方法
- 开放定址法：当关键字key的初始哈希地址出现冲突时，以该地址为基础产生另一个地址，如果仍然冲突，则再以该新地址为基础产生下一个地址，直到找到一个不冲突的地址为止。这种方法包括线性探测再散列、二次探测再散列和伪随机数探测再散列等。
- 再哈希法：同时构造多个不同的哈希函数。当哈希地址冲突时，依次使用这些哈希函数进行计算，直到找到一个不冲突的地址为止。这种方法不易产生聚集，但增加了计算时间。
- 链地址法：将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。查找、插入和删除操作主要在同义词链中进行。这种方法适用于哈希表较大且元素分布不均匀的情况。
- 建立公共溢出区：将哈希表分为基本表和溢出表两部分。凡是和基本表发生冲突的元素一律填入溢出表。这种方法简单易懂，但可能增加查找时间。
五、哈希法的优缺点
优点：
- 查找效率高：哈希查找的时间复杂度为O(1)，即常数时间。这使得哈希查找在大规模数据集合中具有很高的效率。
- 空间利用率高：哈希查找只需要存储关键字和对应的值，不需要额外的空间来存储指针等信息。
- 可扩展性强：哈希查找可以通过调整哈希函数和哈希表的大小来适应不同的数据集合。
缺点：
- 哈希冲突：当两个不同的关键字映射到同一个位置时，会发生哈希冲突。冲突会导致查找效率降低，需要额外的时间来解决。
- 哈希函数设计困难：设计一个好的哈希函数并不容易。一个好的哈希函数应该能够将关键字均匀地映射到哈希表中，以减少冲突的发生。然而，在实际应用中，很难找到一个完美的哈希函数来满足所有需求。
- 不支持范围查找：哈希查找只能支持精确查找，无法支持范围查找。如果需要查找某个范围内的元素，就需要使用其他数据结构或算法。
- 删除操作困难：在哈希表中删除元素时，需要确保删除后不会破坏哈希表的性质（如保持链表的完整性或重新计算哈希地址等）。这可能导致删除操作的时间复杂度变高。
总结
综上所述，哈希法是一种高效的查找技术，具有查找效率高、空间利用率高和可扩展性强等优点。然而，它也存在哈希冲突、哈希函数设计困难、不支持范围查找和删除操作困难等缺点。在实际应用中，需要根据具体需求选择合适的哈希函数和解决冲突的方法来实现哈希查找。
结语
清醒是知足常乐
而非奢望过多
！！！
