I'm working in implementing a hash table, and I'm running into a Seg Fault whenever I try to access my buckets :( Here's the code:

simple test class

//TEST HASH!! 

#include "hashTable.h"
#include <iostream>
#include <string>

using namespace std;

int main() {
  hashTable htab(101);
  htab.insert("blah");
  cout << htab.contains("blah") << endl;
  cout << htab.contains("bkldsh") << endl;

}

hashTable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <list>
#include <string>
#include <vector>

using namespace std;

class hashTable {
	public:
		hashTable(int size);
		bool contains(const string & x);
		bool insert(const string & x);
	private:
		vector<list<string> > theLists;
		int currentSize;
		int tableSize;
		int hash(const string & key);
	};
	
#endif

and hashTable.cpp

#include "hashTable.h"
#include <iostream>

#include <list>
#include <string>
#include <vector>

using namespace std;

hashTable::hashTable(int size) {
	vector<list<string> > theLists (size);
	currentSize = 0;
	tableSize = size; 
}

bool hashTable::contains(const string & x) {
	const list<string> & whichList = theLists[hash(x)];
	return find(whichList.begin(), whichList.end(), x) != whichList.end();
}
bool hashTable::insert(const string & x) {
	int hashVal = hash(x);
	cout << hashVal << endl;
	list<string> & iList = theLists[hashVal];
	if(find(iList.begin(), iList.end(), x) != iList.end())
		return false;
	iList.push_back(x);
	currentSize++;
	return true;
}

int hashTable::hash(const string & key) {
	int hashVal = 0;
	for(int i = 0; i < key.length(); i++) {
		hashVal = 37 * hashVal + key[i];
		}
		
	hashVal %= tableSize;
	
	if(hashVal < 0)
		hashVal += tableSize;
		
	return hashVal;
}

the Vector that i'm using for my hash table seems to work fine - using couts I determined that I get the segfault whenever I try to do anything with iList inside the insert function (either the if statement or my push_back() call). Anyone know why I'm getting a segfault here?

hashTable::hashTable(int size) {
// A variable local to the constructor used here,
// such vector object would be destroyed the moment
// this constructor call is finished.
//// vector<list<string> > theLists (size);

  // Instead use the member variable vector and
  // allocate the requested amount of lists ...
  theLists.resize(size);
  currentSize = 0;
  // Note that using 'tableSize' is redundant, since the
  // theLists.size() will tell you the same thing.
  tableSize = size; 
}

So the theLists vector was never allocated ( .resize() ), leading to those seg faults when trying to access the non-existent data.

This article has been dead for over six months. Start a new discussion instead.