《编程珠玑》代码之路21：设计一个比C++库函数快一个数量级的《圣经》单词统计功能

给出这么一个问题，统计《圣经》出现的所有单词以及其出现次数，单词定义为两个空格之间的词语，当然开头结尾这种自然也是单词。

容易想到的是用C++库函数的map，但这其实并不是最优的选择，根据实际情况选择最优的数据结构，比直接调库，要好玩的多。

怎么办呢，《圣经》中有29131个不同的单词，我们可以做一个散列，大小用最接近单词数量的质数，乘数定义为31，这也是散列技术比较传统的办法。

如果冲突的话，就把冲突的词放在一个链表上。下面给出的代码，会比简单调用库函数快十倍不止：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

struct Node{
	char *word;
	int count;
	Node *next;
}node;

const int NHASH = 29989;
const int MULT = 31;
Node *bin[NHASH + 10];

unsigned int hash(char *p);
void incWord(char *str);

int main(){

	freopen("in.txt", "r", stdin);
	for (int i = 0; i < NHASH; ++i){
		bin[i] = NULL;
	}

	char str[10000];
	while (cin >> str){
		incWord(str);
	}

	for (int i = 0; i < NHASH; ++i){
		for (Node *p = bin[i]; p != NULL; p = p->next){
			cout << p->word << "  " << p->count << endl;
		}
	}


	return 0;
}

unsigned int hash(char *p){

	unsigned int h = 0;
	for (; *p; ++p){
		h = MULT * h + *p;
	}
	return h % NHASH;
}

void incWord(char *str){
	unsigned int h = hash(str);

	Node *p = NULL;
	for (p = bin[h]; p != NULL; p = p->next){
		if (strcmp(str, p->word) == 0){
			(p->count)++;
			return;
		}
	}

	p = new Node();
	p->count = 1;
	p->word = new char(strlen(str) + 1);
	strcpy(p->word, str);
	p->next = bin[h];
	bin[h] = p;
}