数据结构 查找

哈希表

哈希表查找：通过关键字值进行某种运算，直接求出记录文件的地址，是关键字到地址的直接转换方法，不需反复比较。

两个问题：

• 如何构造哈希（或散列）函数？
• 如何解决冲突？

哈希函数是一个映像，使得： Addr(\(R_i\))=H(\(key_i\)) 其中：

• \(key_i\)为记录\(R_i\)的关键字；
• H(\(key_i\))为哈希函数；
• Addr(\(R_i\))为记录\(R_i\)的存储地址
• 冲突：对不同的关键字可能得到同一哈希地址。

哈希函数的构造方法

目标：使关键字经过哈希函数得到一个“随机地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，减少冲突。

直接定址法

H(key)=a.key+b 其中：a,b为常数

不同的关键字不会发生冲突，但在记录长度不等的情况下浪费一些存储空间。

数字分析法

假设有一组关键字，每个关键字由n位数字组成，如：k1k2…kn, 从中提取数字分布比较均匀的若干位作为哈希地址。

平方取中法：取关键字平方后的中间几位哈希地址例：