Code:
int len=0;
len = word.length();
return (300%len);
This returns an integer in [0..len-1].
You could modify this code
Code:
#include <algorithm>
#include <list>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int N = 7691;
struct Hash_table {
list<string> bucket[N];
};
Hash_table hash_table;
static unsigned int hash_str(const char* name, int n)
{
unsigned int h = 0;
unsigned int t;
while(*name)
{
h ^= (h << 4) + *name;
t = h & 0xf0000000;
if (t)
{
h ^= (t >> 24);
h ^= t;
}
name++;
}
return h % n;
}
void insert(Hash_table* hash_table, const string& s)
{
// returns a number in [0..N-1]
int h = hash_str(s.c_str(), N);
// since a dictionaries words should be unique and
// doesn't matter too much if we have duplicates
// all that's neccessary is to insert them into the list
// of words that hash to h
hash_table->bucket[h].push_back(s);
}
bool lookup(const Hash_table* hash_table, const string& name)
{
int h = hash_str(name.c_str(), N);
const list<string>& bucket = hash_table->bucket[h];
return find(bucket.begin(), bucket.end(), name) != bucket.end();
}
void init_map()
{
ifstream dict("/usr/dict/words");
string word;
int key=0;
int garbage = 0;
if (!dict)
{
cout<<"dictionary file could not be opened."<< endl;
exit(0);
}
while(dict)
{
getline(dict, word);
insert(&hash_table, word);
}
dict.close();
}
int main(void)
{
init_map();
cout << lookup(&hash_table, "hello") << endl;
cout << lookup(&hash_table, "foo") << endl;
return 0;
}
This will run pretty fast. If you need it faster you could
try increasing the size of the table or trying a different hash
function.