Okay, a hash table is essentially an efficient way to store data in an array according to a unique identifier number. The efficient part about it is that searching a hash table is incredibly fast. Ready to have some fun? I prefer to use a dynamic array template for the table:
Code:
template <class T>
class HashTable{
public:
HashTable(int n) : size(n) {
array = new T[n];
for( int i = 0; i < n; ++i)
array[i] = T();
int size(){return size;}
T& operator[](int x){return array[x];}
protected:
T *array;
int size;
};
Let's say that the table will consist of the first and last names of people, just to keep it simple. You would use a struct similar to this:
Code:
struct Person{
bool isNull(){return bool(last.length() == 0);}
string last;
string first;
};
Then there's the part of the main program that actually creates the hash table and puts stuff in it.
Code:
int main(void){
ifstream IN("people.txt");
Person person;
HashTable<Person> table(SIZE);
while(get(person, IN)){
int i = hash(person.last + person.first);
while(!table[i].isNull())
i = (i+1) % SIZE;
table[i] = person;
}
print(table);
}
Then you define the actual hash function that turns the two concatenated names into a number.
Code:
int hash(string s){
int h = 0;
for(int i = 0; i < s.length(); ++i)
h += int(s[i]);
return h % SIZE;
}
And then of course you need the rest of the functions for the program
Code:
bool get(Person& person, ifstream IN){
char buffer[BUFSIZE], temp[BUFSIZE];
IN.getline(buffer, BUFSIZE);
if(IN.fail()) return false;
istrstream s(buffer);
s.getline(temp, BUFSIZE, '\t'); //names separated by tab
person.last = temp;
s.getline(temp, BUFSIZE, '\t');
person.first = temp;
s.getline(temp, BUFSIZE, '\t'); //eat the tab :)
return true;
}
void print(Person& person){
cout<<person.last<<", "<<person.first<<endl;
}
template <class T>
void print(HashTable<T>& t){
for(int i = 0; i < t.size(); ++i){
cout<<setiosflags(ios::right)<<setw(4)<<i<<". "; //print index #
if(!t[i].isNull()) printf(t[i]);
else cout<<endl;
}
}
Having fun yet? Be sure to run it and toy with it, I'm not sure if there are errors because I wrote this off the top of my head, so be ready for debugging and please accept my appologies. You'll need to include <fstream>, <iomanip>, <iostream>, and <sstream>.
-Prelude