【数据结构与算法】哈希函数 详解

哈希函数的构造方法有哪些？

1. 直接定址法：直接使用关键字或者关键字的某个线性函数值作为哈希地址。

2. 数字分析法：对关键字进行分析，选择关键字中的某几位或者进行某种运算得到的结果作为哈希地址。

3. 平方取中法：先计算关键字的平方，然后取平方结果的中间几位作为哈希地址。

4. 折叠法：将关键字分割成若干部分，然后将这些部分的叠加和作为哈希地址。

5. 除留余数法：使用关键字被某个不大于哈希表长度的数p除后所得的余数作为哈希地址。
   

6. 随机数法：选择一个随机函数，将关键字输入到随机函数中，得到的结果作为哈希地址。
   

7. 基数转换法：先把关键字看成基数为r1的数，然后将它转换成基数为r2的数，再选取其中几位作为哈希地址。

选取哈希函数应考虑哪些因素？

1. 计算哈希函数所需时间：理想的哈希函数应该能够快速地计算出哈希值。如果计算哈希值的时间过长，那么即使哈希函数能够很好地减少冲突，也可能无法满足性能要求。

2. 关键字长度：关键字的长度可能会影响哈希函数的选择。例如，对于长字符串，可能需要选择一种能够处理长输入的哈希函数。

3. 哈希表的大小（哈希地址范围）：哈希表的大小直接决定了哈希地址的范围。理想的哈希函数应该能够将输入均匀地映射到整个哈希地址范围。

4. 关键字分布情况：如果关键字的分布情况已知，那么可以选择一种能够适应这种分布的哈希函数，以减少冲突。

5. 记录的查找频率：如果某些记录的查找频率较高，那么可以考虑使用一种能够将这些记录映射到不同哈希地址的哈希函数，以提高查找效率。