elfhash.cpp

1.B树的实现 2.ElfHash的实现 3.三种排序方式(插入

#include<fstream>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int M = 86423;

string infile[] = {"en-only.dic", "en_US-only.dic", "en_GB-only.dic", "en_CA-only.dic"};

inline int elfhash(const char *key){
	unsigned long h=0;
	
	while (*key){
		h=(h<<4) + *key++;
		unsigned long g=h & 0Xf0000000L;
		if (g) h^= g>>24;
		h &= ~g;
	}

	return h % M;
}

int n, count;

vector<string> hash[M+1];

void update(const string &s, int key){
	
	vector<string> &slot = hash[key];
	int size = slot.size();

	for (int i=0;i<size;++i){
		count++;
		if (slot[i] == s) return;
	}

	slot.push_back(s);
}

int main(){
	string s;
	for (int i=0;i<1;++i){
		ifstream fin(infile[i].c_str());
		while (fin>>s) {
			n++;
			update(s, elfhash(s.c_str()));
		}
	}
	printf("%.4lf\n", double(count)/n);

	int cover =0;
	for (int i = 0;i< M;++i)
		cover += (!hash[i].empty());
	cout<<cover<<endl;
	return 0;
}