还是上学期数据结构课的练习，这里的代码写得还不是很好，不过可以作为理解哈希表的参考(๑•̀ㅂ•́)و✧

实现功能

1.文件输入输出

1)将文件按单词输入
2)将单词及统计结果保存到文件

2.单词的处理

1)将大小写不同的相同单词合并
2)删除多余的标点符号

3.单词词频统计

算法简述

算法流程图

1.流程图说明说明：

1)算法中采用一个结构体存储单词和词频，结构体包含一个string用于存储单词，一个int用于存储词频，以及一个指向下一节点的指针用于构建链表。

struct hashNode
{
    string word;
    int count;
    hashNode *next;
};

2)哈希地址表是一个数组，下标范围覆盖了哈希函数的整个值域。数组中存储的是指向链表节点（存储单词和词频的结构体）的指针。地址表被声明时初始化为空。

hashNode *index[range] = { NULL };

3)所有单词统计完成后哈希表即失去作用，从链表把数据转入vector后输出。

2.流程图

各部分算法

1.字符串处理

从文本中读取的字符串有可能包含空格以及标点符号，还会存在首字母大写的问题。空格已经在输入输出中由ifstream自动忽略，而标点符号和大小写问题则可以通过ASCII码范围过滤解决。

string handleString(string inputWord)
{
    string word;
    for (int i = 0; i < inputWord.size(); i++)
    {
        if (inputWord[i] >= 65 && inputWord[i] <= 90)
        {
            char tmp = inputWord[i] + 32;
            word.push_back(tmp);
        }
        else if (inputWord[i] >= 97 && inputWord[i] <= 122)
        {
            word.push_back(inputWord[i]);
        }
        else if (inputWord[i] == 45 || inputWord[i] == 39)
        {
            word.push_back(inputWord[i]);
        }
    }
    return word;
}

2.计算哈希值

为了使哈希表尽可能达到最优性能，要使得碰撞概率尽可能小，也就是哈希函数值域和随机性足够大；但是又因为分配过大的内存也会对性能造成影响，故要选择合理的范围。

在本程序实现中，我考虑使用0到9972作为哈希函数值域范围，因为9973是10000内最大的素数，在取模运算中同模概率低；同时它也足够小，因为一个包含9973个元素的指针数组不至于影响计算机性能。

算法上，本实现中使用字符串（单词）各个字母的ASCII码进行迭代运算。ASCII码是将char与int建立对应关系的最简便映射，虽然其随机性远不如SHA1和MD5等高强度哈希算法所采用的对二进制进行操作，但毕竟词频统计的实际应用场景中ASCII码足以保证足够低的碰撞率。

每一位（每一个字母ASCII码）参与计算后的结果将继续参与运算。这种思路是参考了大多数伪随机数算法，通常以系统时间等变量取得第一个随机种子后，之后的随机种子会用第一个随机数运算结果。在计算哈希值中采用这种方法，理论上可以提高哈希值离散度。

int Hash::calculateHash(string word)
{
    int h = 0;
    for (int i = 0; i < word.size(); i++)
    {
        h = 31 * h + word[i];
        h %= 65536;
    }
    int key = h%range;
    return key;
}

在循环中会对65536取模，这是考虑到当单词较长时可能发生计算结果过大影响性能甚至超出int能表示的范围的问题。通过这步取模，可以保证结果不太大，不影响性能。

最后对数组大小9973（已定义为range）取模，保证哈希值值域在数组下标范围内。

3.碰撞检测和计数

当哈希值对应的哈希地址表地址为空时，就表示该单词此前未出现，可以直接添加链表节点开始统计。当该地址非空时，要先判断是发生了碰撞还是找到单词，如果找到单词则计数自增，如果发生碰撞则向后遍历各节点并循环进行判断直到找到单词或地址为空。这种遍历避免冲撞的方法是最简单也是执行效率最低的，但是考虑到哈希函数冲撞率本身很低，发生的冲撞不至于影响整体性能，所以在这一实现中我才用最简单的遍历算法解决冲撞。

void Hash::hashWord(string word)
{
    int key = calculateHash(word);
    hashNode *tmp = index[key];
    while (tmp != NULL)
    {
        if (tmp->word == word)
        {
            tmp->count++;
            return;
        }
        tmp = tmp->next;
        collision += 1;
    }
    hashNode *newNode = new hashNode;
    newNode->count = 1;
    newNode->word = word;
    newNode->next = index[key];
    index[key] = newNode;
}

当发生冲撞时，对冲撞计数的变量自增，便于运行结束时输出。

代码

1.main.cpp

#include <string>
#include <fstream>
#include <iostream>
#include <iomanip>
#include "Hash.h"
#include "Globle.h"

using namespace std;

int main()
{
    string input, inputFileName, outputFileName;
    cout << "请输入运算命令的完整文件名（包含路径和扩展名）：";
    cin >> inputFileName;
    cout << "请输入希望保存运算结果的文件名（包含路径和扩展名）：";
    cin >> outputFileName;
    ifstream inputFile;
    ofstream outputFile;
    inputFile.open(inputFileName);
    outputFile.open(outputFileName);
    string inputWord;
    Hash hashTable;
    clock_t start, end;
    double time;
    start = clock();
    while (inputFile >> inputWord)
    {
        hashTable.hashWord(handleString(inputWord));
    }
    inputFile.close();
    hashTable.writeOutTable();
    end = clock();
    for (int i = 0; i < hashTable.outTable.size(); i++)
    {
        outputFile << setw(30) << setiosflags(ios::left) << hashTable.outTable[i].word << ' ' << hashTable.outTable[i].count << endl;
    }
    time = (double)(end - start);
    outputFile << "程序主体部分执行时间（毫秒）：" << time;
    outputFile.close();
    return 0;
}

2.Hash.h

#pragma once
#include <vector>
#include <string>
#include "Globle.h"

class Hash
{
    hashNode *index[range] = { NULL }; 
    int collision = 0;
public:
    Hash();
    ~Hash();
    void hashWord(string word);
    void writeOutTable();
    int calculateHash(string word);
    vector <hashNode> outTable;
};

3.Hash.cpp

#include "Hash.h"
#include "Globle.h"
#include <string>

Hash::Hash()
{
}

Hash::~Hash()
{
}

void Hash::hashWord(string word)
{
    int key = calculateHash(word);
    hashNode *tmp = index[key];
    while (tmp != NULL)
    {
        if (tmp->word == word)
        {
            tmp->count++;
            return;
        }
        tmp = tmp->next;
        collision += 1;
    }
    hashNode *newNode = new hashNode;
    newNode->count = 1;
    newNode->word = word;
    newNode->next = index[key];
    index[key] = newNode;
}

int Hash::calculateHash(string word)
{
    int h = 0;
    for (int i = 0; i < word.size(); i++)
    {
        h = 31 * h + word[i];
        h %= 65536;
    }
    int key = h%range;
    return key;
}

void Hash::writeOutTable()
{
    for (int i = 0; i < range; i++)
    {
        for (hashNode *tmp = index[i]; tmp != NULL; tmp = tmp->next)
        {
            hashNode outTemp;
            outTemp.count = tmp->count;
            outTemp.word = tmp->word;
            outTemp.next = NULL;
            outTable.push_back(outTemp);
        }
    }
}

4.Globle.h

#pragma once
#include <string>
#include <vector>

#define range 9973//¹þÏ£±í´óС
#define multiply 23//¶¨Òå³Ë·¨ÒòÊý

using namespace std;

string handleString(string inputWord);

struct hashNode
{
    string word;
    int count;
    hashNode *next;
};

5.Globle.cpp

#include "Globle.h"

string handleString(string inputWord)
{
    string word;
    for (int i = 0; i < inputWord.size(); i++)
    {
        if (inputWord[i] >= 65 && inputWord[i] <= 90)
        {
            char tmp = inputWord[i] + 32;
            word.push_back(tmp);
        }
        else if (inputWord[i] >= 97 && inputWord[i] <= 122)
        {
            word.push_back(inputWord[i]);
        }
        else if (inputWord[i] == 45 || inputWord[i] == 39)
        {
            word.push_back(inputWord[i]);
        }
    }
    return word;
}