I know how to create a hash_map and use my hash function with it, but I don't know how to handle collisions. Specifically, how would I implement a chain/buckets with a linked list... it seems like it's built in but I can't find how to do it.

#include <iostream>
#include <string>
#include <ext/hash_map>
#include "d_hashf.h"

using namespace __gnu_cxx;

int main()
	typedef hash_map<string, string, hFstring> hash_class;

	hash_class extensions;
	hash_class::iterator itr;

	extensions["Test1"] = "HAHAHA";
	extensions["Test1"] = "HoHoHo";
	extensions["Test1"] = "HeHEHe";

	for(itr = extensions.begin(); itr != extensions.end(); itr++)
		cout << (*itr).first << (*itr).second << endl;

	cout << extensions["Test1"] << endl;
	if (extensions.find("Test1") == extensions.end())
		cout << "NULL" << endl;

Here's some example code, if anyone would like to see... What I'll end up doing is creating 1373 buckets to store 25,000+ dictionary words. I'd like to know how to limit the number of buckets to 1373 and implement chaining.

8 Years
Discussion Span
Last Post by RavUn

That's what the professor wanted....

The dictionary file “dict.txt” contains 25,025 frequently used words, each on a separate line in lowercase. Read the file and insert the words into a hash table with 1373 buckets. Use chaining for your collision resolution scheme (however, see extra credit below). Prompt the user for the name of a document (which should contain plain ascii text). Read the document, and separate it into a sequence of words converted to lowercase, where a word is defined by the function getWord. Using the hash table, output a list of words that appear to be misspelled.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.