题目要求

验证好的散列函数能将关键字均匀地散布在0~M-1之间：

  1. 编写程序将《双城记》中的10000+个单词，散列到 0~M-1之间。
  2. 统计每个单词的散列值的出现频率，并按条形图的格式输出。
  3. 分别取不同的M，直观看看哪个M比较合适。例如， M 可以取97，997，1997等。
  4. 查找某单词是否在《双城记》中出现？随机查找100个单词，估算一次查找的平均比较次数。

实现的功能

  1. 将《双城记》中的10000+个单词，散列到 0~M-1之间，并统计每个单词的散列值的出现频率，按条形图的格式输出。
  2. 查找用户指定的单词是否在《双城记》中出现
  3. 一键导入用户给定文本中的单词，查询其中每个单词是否出现，并计算一次查找的平均比较次数
  4. 以上功能均可以自定义M的值以实现最佳效果

方法

构造哈希函数

使用BKDRHash

1
2
3
4
5
6
7
unsigned int BKDRHash(const char *str, int M) {
    unsigned int hash = 0;
    while (*str) {
        hash = (hash * 131) + (*str++);
    }
    return hash % M;
}

预处理文本

去除《双城记》中的重复单词，存到指定文件output.txt中

散列处理

对output.txt中每个单词，计算hash值，统计频率

绘制频率分布图

使用QtCharts库进行绘图

查找单词

计算所查单词的hash值，在该hash值下的vector里逐一比较，输出查询结果和比较次数

查找多个单词同理，再在最后输出平均比较次数

效果

image-20231101163906549